On minimal forbidden subgraphs for the class of EDM-graphs

Gašper Jaklič, Jolanda Modic

Abstract


In this paper, a relation between graph distance matrices and Euclidean distance matrices (EDM) is considered. Graphs, for which the distance matrix is not an EDM (NEDM-graphs), are studied. All simple connected non-isomorphic graphs on n <= 8 nodes are analysed and a characterization of the smallest NEDM-graphs, i.e., the minimal forbidden subgraphs, is given. It is proven that bipartite graphs and some subdivisions of the smallest NEDM-graphs are NEDM-graphs, too.

Keywords


Graph, Euclidean distance matrix, distance, eigenvalue.

Full Text:

PDF ABSTRACTS (EN/SI)


DOI: https://doi.org/10.26493/1855-3974.467.98f

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications