A Dimension 6 Graph with Minimum Edge-set

Chaffee, Joe; Noble, Matt
November 2017
Graphs & Combinatorics;Nov2017, Vol. 33 Issue 6, p1565
Academic Journal
The dimension of a graph G is defined to be the minimum n such that G has a representation as a unit-distance graph in $${{\mathbb {R}}}^n$$ . In this article, we show that a dimension 6 graph with minimum edge-set has exactly 21 edges, with this minimum realized only in the case of the complete graph $$K_7$$ . This result answers a higher-dimensional analogue of a question posed by Paul Erdős and presented by Alexander Soifer in The Mathematical Coloring Book.


Related Articles

  • From the President. Soifer, Alexander // Mathematics Competitions;2013, Vol. 26 Issue 1, p4 

    A letter is presented from Alexander Soifer, president of the World Federation of National Mathematics Competitions (WFNMC) to his fellow federalists, about the 7th Congress of the World Federation of National Mathematics Competitions that will be held at the Hotel El Prado in Barranquilla,...

  • Cycle decompositions V: Complete graphs into cycles of arbitrary lengths. Bryant, Darryn; Horsley, Daniel; Pettersson, William // Proceedings of the London Mathematical Society;May2014, Vol. 108 Issue 5, p1153 

    We show that the complete graph on n vertices can be decomposed into t cycles of specified lengths m1, …, mt if and only if n is odd, 3≤mi≤n for i=1, …, t, and . We also show that the complete graph on n vertices can be decomposed into a perfect matching and t cycles of...

  • Triviality of the Conway-Gordon Function ω for Spatial Complete Graphs. Kazakov, A.; Korablev, Ph. // Journal of Mathematical Sciences;Dec2014, Vol. 203 Issue 4, p490 

    We prove that ω( G) = 0 for any spatial complete graph G with n ≥ 7 vertices, where ω is the function introduced by J.Y. Conway and C. McA. Gordon in 1983.

  • Edge-disjoint Open Trails in Complete Bipartite Multigraphs. Cichacz, Sylwia; G�rlich, Agnieszka // Graphs & Combinatorics;Mar2010, Vol. 26 Issue 2, p207 

    Let r Ka,b be a complete bipartite multigraph. We show a necessary and sufficient condition for a multigraph r Ka,b to be arbitrarily decomposable into open trails. We extend the results obtained by Balister for complete graphs (Balister in Probab Comput 10:463-499, 2001). Moreover we show that...

  • On the Decomposition of Graphs into Complete Bipartite Graphs. Jinquan Dong; Yanpei Liu // Graphs & Combinatorics;Sep2007, Vol. 23 Issue 3, p255 

    In a complete bipartite decomposition π of a graph, we consider the number ϑ( v;π) of complete bipartite subgraphs incident with a vertex v. Let ϑ( G)= $$\min \limits_{\pi } \max \limits_{v\in V(G)}$$ ϑ( v;π). In this paper the exact values of ϑ( G) for complete...

  • All totally symmetric colored graphs. Grech, Mariusz; Kisielewicz, Andrzej // Discrete Mathematics & Theoretical Computer Science (DMTCS);2013, Vol. 15 Issue 1, p133 

    In this paper we describe all edge-colored graphs that are fully symmetric with respect to colors and transitive on every set of edges of the same color. They correspond to fully symmetric homogeneous factorizations of complete graphs. Our description completes the work done in our previous...

  • Difference Cordial Labeling of Graphs Obtained from Triangular Snakes. Ponraj, R.; Narayanan, S. Sathish // Applications & Applied Mathematics;Dec2014, Vol. 9 Issue 2, p811 

    In this paper, we investigate the difference cordial labeling behavior of corona of triangular snake with the graphs of order one and order two and also corona of alternative triangular snake with the graphs of order one and order two.

  • Traversability and Covering Invariants of Token Graphs. Mirajkar, Keerthi G.; Y. B., Priyanka // International Journal of Mathematical Combinatorics;2016, Vol. 2, p132 

    Let Fk(G),k ≥ 1, G be the token graph of a connected graph G. In this paper, we investigate the Eulerian and Hamiltonian property of token graphs and obtain the covering invariants for complete graph of token graph.

  • Colorful Isomorphic Spanning Trees in Complete Graphs. Constantine, Gregory // Annals of Combinatorics;2005, Vol. 9 Issue 2, p163 

    Can a complete graph on an even number n (> 4) of vertices be properly edge-colored with n - 1 colors in such a way that the edges can be partitioned into edge-disjoint colorful isomorphic spanning trees? A spanning treee is colorful if all n - 1 colors occur among its edges. It is proved that...

  • PRODUCT ROSY LABELING OF GRAPHS. Froncek, Dalibor // Discussiones Mathematicae: Graph Theory;2008, Vol. 28 Issue 3, p431 

    In this paper we describe a natural extension of the well-known ?-labeling of graphs (also known as rosy labeling). The labeling, called product rosy labeling, labels vertices with elements of products of additive groups. We illustrate the usefulness of this labeling by presenting a recursive...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics