Geodesic
Minimal Graphs with Respect to Geometric Distance Realizability
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 1, pp. 65-73.

Voir la notice de l'article provenant de la source Library of Science

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 
@article{DMGT_2021_41_1_a3,
     author = {Madaras, Tom\'a\v{s} and \v{S}iroczki, Pavol},
     title = {Minimal {Graphs} with {Respect} to {Geometric} {Distance} {Realizability}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {65--73},
     publisher = {mathdoc},
     volume = {41},
     number = {1},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a3/}
}
TY  - JOUR
AU  - Madaras, Tomáš
AU  - Široczki, Pavol
TI  - Minimal Graphs with Respect to Geometric Distance Realizability
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 65
EP  - 73
VL  - 41
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a3/
LA  - en
ID  - DMGT_2021_41_1_a3
ER  - 
%0 Journal Article
%A Madaras, Tomáš
%A Široczki, Pavol
%T Minimal Graphs with Respect to Geometric Distance Realizability
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 65-73
%V 41
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a3/
%G en
%F DMGT_2021_41_1_a3
Madaras, Tomáš; Široczki, Pavol. Minimal Graphs with Respect to Geometric Distance Realizability. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 1, pp. 65-73. http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a3/

[1] N. Alon and A. Kupavskii, Two notions of unit distance graphs, J. Combin. Theory Ser. A 125 (2014) 1–17. doi: 10.1016/j.jcta.2014.02.006

[2] P. Erdős, F. Harary and W.T. Tutte, On the dimension of a graph, Mathematika 12 (1965) 118–122. doi: 10.1112/S0025579300005222

[3] R.L. Graham, B.L. Rotschild and E.G. Strauss, Are there n + 2 points in n with odd integral distances ?, Amer. Math. Monthly 81 (1974) 21–25. doi: 10.1080/00029890.1974.11993491

[4] B. Horvat, J. Kratochvíl and T. Pisanski, On the computational complexity of degenerate unit distance representations of graphs, Lecture Notes in Comput. Sci. 6460 (2011) 274–285. doi: 10.1007/978-3-642-19222-7_28

[5] V.P. Korzhik and B. Mohar, Minimal obstructions for 1-immersions and hardness of 1-planarity testing, J. Graph Theory 72 (2013) 30–71. doi: 10.1002/jgt.21630

[6] K. Kuratowski, Sur le problème des courbes gauches en topologie, Fund. Math. 15 (1930) 271–283. doi: 10.4064/fm-15-1-271-283

[7] L. Piepmeyer, The maximum number of odd integral distances between points in the plane, Discrete Comput. Geom. 16 (1996) 113–115. doi: 10.1007/BF02711135

[8] M. Rosenfeld and N.L. Tiên, Forbidden subgraphs of the odd-distance graph, J. Graph Theory 75 (2014) 323–330. doi: 10.1002/jgt.21738

[9] A. Soifer, The Mathematical Coloring Book (Springer-Verlag, New York, 2009). doi: 10.1007/978-0-387-74642-5

[10] M. Tikhomirov, On computational complexity of length embeddability of graphs, Discrete Math. 339 (2016) 2605–2612. doi: 10.1016/j.disc.2016.05.011

[11] D.B. West, Introduction to Graph Theory (Prentice Hall, 1996).

[12] H. Weyl, Über die Gibbs’sche Erscheinung und verwandte Konvergenzphänomene, Rend. Circ. Mat. 30 (1910) 377–407. doi: 10.1007/BF03014883