Skip to main content
On Distance Between Graphs
Graphs and Combinatorics
  • Alexander Halperin, Lehigh University
  • Colton Magnant, Georgia Southern University
  • Daniel M. Martin, Universidade Federal do ABC
Document Type
Publication Date

For a collection of graphs G, the distance graph of G is defined to be the graph containing a vertex for each graph in G, and an edge if the two corresponding graphs differ by exactly one edge. In 1998, Chartrand, Kubicki and Schultz conjectured that every bipartite graph is the distance graph for some collection of graphs. In this paper, we provide methods to combine known distance graphs to generate new larger ones. As observed by Gorše Pihler and Žerovnik in 2008, an important subcase of this conjecture seems to be whether dense graphs can be distance graphs, particularly the complete bipartite graphs. Along these lines, we extend the class of known distance graphs to include K 4,4. We further introduce equivalent formulations of this conjecture and discuss related problems.

Citation Information
Alexander Halperin, Colton Magnant and Daniel M. Martin. "On Distance Between Graphs" Graphs and Combinatorics Vol. 29 Iss. 5 (2012) p. 1391 - 1402 ISSN: 1435-5914
Available at: