Authors:
T. Madaras, P. ©iroczki
Title:
Minimal graphs with respect to geometric distance realizability
Source:
Discussiones Mathematicae Graph Theory
Received 09.04.2018, Revised 06.08.2018, Accepted 06.08.2018, doi: 10.7151/dmgt.2176

Abstract:
A graph G is minimal non-unit-distance graph if there is no drawing of G in Euclidean plane having all edges of unit length, but, for each edge e of G, G - e has such a drawing. We prove that, for infinitely many n, the number of non-isomorphic n-vertex minimal non-unit-distance graphs is at least exponential in n.
Keywords:
unit-distance graph, odd-distance graph, Euclidean plane

Links:
PDF