# DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

# IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

# Discussiones Mathematicae Graph Theory

Article in press

Authors:

Title:

Minimal graphs with respect to geometric distance realizability

Source:

Discussiones Mathematicae Graph Theory

Received: 2018-04-09, Revised: 2018-08-06, Accepted: 2018-08-06, https://doi.org/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