DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

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

Discussiones Mathematicae Graph Theory

Article in press


Authors:

T. Madaras, P. Široczki

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

PDF
Close