×

On the Euclidean dimension of a wheel. (English) Zbl 0642.05018

The Euclidean dimension e(G) of a graph G is defined to be the minimum n so that G can be immersed in Euclidean n-space \(R^ n\) so that two distinct vertices of G are adjacent if and only if they are distance 1 apart. (The immersion need not be one-to-one on open arcs.) Constructive proofs are given to calculate e(G), for G a wheel \(W_{1,n}=K_ 1+C_ n,\) a complete tripartite graph, or a generalized wheel \(W_{m,n}=\bar K_ m+C_ n.\) For example: \(e(W_{1,6})=2\), \(e(W_{1,n})=3\) if \(n\neq 6\).
Reviewer: A.T.White

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: DOI

References:

[1] Erdös, P.: On sets of distances ofn points in Euclidean space. Publ. Math. Inst. Hungar. Acad. Sci.5, 165–169 (1960) · Zbl 0094.16804
[2] Erdös, P., Harary, F., Tutte, W.T.: On the dimension of a graph. Mathematika12, 118–122 (1965) · Zbl 0151.33204 · doi:10.1112/S0025579300005222
[3] Harary, F.: Graph Theory. Reading: Addison-Wesley 1969 · Zbl 0182.57702
[4] Harary, F., Melter, R.: The graphs with no equilateral triangles. Gaz. Mat., Bucur.3, 182–183 (1982) · Zbl 0606.05060
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.