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: |