On minimal forbidden subgraphs for the class of EDM-graphs

Authors

  • Gašper Jaklič FMF and IMFM, University of Ljubljana, Jadranska 19, 1000 Ljubljana, Slovenia, IAM, University of Primorska, Slovenia
  • Jolanda Modic XLAB d.o.o., Pot za Brdom 100, 1000 Ljubljana, Slovenia, FMF, University of Ljubljana, Slovenia

DOI:

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

Keywords:

Graph, Euclidean distance matrix, distance, eigenvalue.

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.

Downloads

Published

2014-11-16

Issue

Vol. 9 No. 2 (2015)

Section

Articles

License

Articles in this journal are published under Creative Commons Attribution 4.0 International License
https://creativecommons.org/licenses/by/4.0/