TOPICS

Honeycomb Toroidal Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
HoneycombToroidalGraph

The honeycomb toroidal graph HTG(m,2n,s) on 2nm vertices for m, n, and s positive integers satisfying n>1 and m+s is even is defined as the graph on vertex set u_(ij) for 0<=i<=m-1 and 0<=j<=2n-1. Edges are then defined as follows, where i and j adjacency are taken modulo m and 2n, respectively.

1. For each i from 0 to m-1, u_(ij) is adjacent to u_(i,j-1) and u_(i,j+1).

2. For each even i from 0 to m-2, there is an edge from u_(ij) to u_(i+1,j) for all odd j.

3. For each odd i from 1 to m-2, there is an edge from u_(ij) to u_(i+1,j) for all even j.

4. If m-1 is even, there is an edge from u_(m-1,j) to u_(0,j+s) for all odd j.

5. If m-1 is odd, there is an edge from u_(m-1,j) to u_(0,j+s) for all even j.

Honeycomb toroidal graphs are cubic, except some cases with m=1 which give cycle graphs C_(2n). They are also vertex-transitive, and a Cayley graphs (Alspach and Dean 2009).

Honeycomb toroidal graphs have also been called generalized honeycomb tori and brick products (Alspach and Dean 2009).

The following table summarizes some special cases.

honeycomb toroidal graph(m,2n,s)
n-crossed prism graph(1,2n,n-1), (1,2n,n+1), (2,2n,2), (2,2n,2n-2)
cubic vertex-transitive graph Ct20(1,18,5), (1,18,7), (1,18,11), (1,18,13), (3,6,1), (3,6,5)
cubic vertex-transitive graph Ct25(1,20,5), (1,20,7), (1,20,13), (1,20,15), (2,10,4), (2,10,6)
cubic vertex-transitive graph Ct32(1,22,5), (1,22,7), (1,22,9), (1,22,13), (1,22,15), (1,22,17)
cubic vertex-transitive graph Ct35(1,24,7), (1,24,17), (3,8,3), (3,8,5), (4,6,2), (4,6,4)
cubic vertex-transitive graph Ct36(1,24,5), (1,24,19), (2,12,4), (2,12,8), (3,8,1), (3,8,7)
cubic vertex-transitive graph Ct38(1,24,9), (1,24,15), (4,6,6)
cubic vertex-transitive graph Ct47(1,26,5), (1,26,9), (1,26,11), (1,26,15), (1,26,17)
cubic vertex-transitive graph Ct51(1,28,7), (1,28,11), (1,28,17), (2,14,6), (2,14,8)
cubic vertex-transitive graph Ct52(1,28,5), (1,28,9), (1,28,19), (2,14,4), (2,14,10)
cubic vertex-transitive graph Ct58(1,30,11), (1,30,19), (3,10,3), (3,10,7), (5,6,1), (5,6,5)
cubic vertex-transitive graph Ct59(1,30,5), (1,30,13), (1,30,17), (3,10,1), (3,10,9)
cubic vertex-transitive graph Ct60(1,30,7), (3,10,5)
cubic vertex-transitive graph Ct62(1,30,9), (5,6,3)
cubic vertex-transitive graph Ct67(1,32,7), (1,32,9), (4,8,2), (4,8,6)
cubic vertex-transitive graph Ct68(1,32,5), (1,32,11), (2,16,4), (2,16,12)
cubic vertex-transitive graph Ct69(2,16,6), (2,16,10), (4,8,8)
cubic vertex-transitive graph Ct77(1,34,7), (1,34,9), (1,34,13)
cubic vertex-transitive graph Ct78(1,34,5), (1,34,11), (1,34,15), (1,34,19)
cubical graph Q_3(1,8,3), (1,8,5), (2,4,2), (2,4,4)
cycle graph C_(2n)(1,2n,1), (1,2n,2n-1)
Dyck graph(4,8,4)
Foster graph F_(026)A(1,26,7), (1,26,19)
Foster graph F_(038)A(1,38,15)
Foster graph F_(042)A(1,42,9)
Foster graph F_(050)A(5,10,5)
Foster graph F_(054)A(3,18,9)
Foster graph F_(056)A(2,28,10), (2,28,18)
Foster graph F_(062)A(1,62,11)
Foster graph F_(072)A(6,12,6)
Foster graph F_(086)A(1,86,13)
Foster graph F_(096)A(4,24,12)
Foster graph F_(098)B(7,14,7)
Foster graph F_(104)A(2,52,14)
Foster graph F_(114)A(1,114,15)
Foster graph F_(126)A(3,42,15)
Foster graph F_(128)A(8,16,8)
Foster graph F_(146)A(1,146,17)
Foster graph F_(150)A(5,30,15)
Foster graph F_(162)A(9,18,9)
Foster graph F_(168)A(2,84,18)
Foster graph F_(182)B(1,182,19)
Foster graph F_(200)A(10,20,10)
Foster graph F_(216)A(6,36,18)
Foster graph F_(224)A(4,56,20)
Foster graph F_(242)A(11,22,11)
Foster graph F_(288)A(12,24,12)
Foster graph F_(338)B(13,26,13)
Foster graph F_(392)B(14,28,14)
Foster graph F_(450)A(15,30,15)
Foster graph F_(512)A(16,32,16)
Foster graph F_(578)A(17,34,17)
Foster graph F_(648)A(18,36,18)
Foster graph F_(722)B(19,38,19)
Foster graph F_(800)A(20,40,20)
Franklin graph(1,12,5), (1,12,7), (2,6,2), (2,6,4), (3,4,1), (3,4,3)
Haar graph H(2^(n+1)+2^(n/2)+1)(1,2n,n-1)
Heawood graph(1,14,5), (1,14,9)
Möbius-Kantor graph(1,16,5), (1,16,11), (2,8,4)
Möbius Ladder M_n(1,2n,3), (1,2n,n), (1,2n,2n-3) for n odd
Nauru graph(2,12,6)
prism graph P_2 square C_n(1,2n,3), (1,2n,n-3), (2,n,n) for n even
utility graph K_(3,3)(1,6,3)

See also

Crossed Prism Graph, Foster Graph, I Graph, Knödel Graph

Explore with Wolfram|Alpha

References

Alspach, B. and Dean, M. "Honeycomb Toroidal Graphs Are Cayley Graphs." Inf. Proc. Lett. 109, 705-708, 2009.Altshuler, A. "Hamiltonian Circuits in Some Maps on the Torus." Disc. Math. 1, 299-314, 1972.Marušič, D. and Pisanski, T. "Symmetries of Hexagonal Molecular Graphs on the Torus." Croatica Chem., 73, 969-981, 2000.

Referenced on Wolfram|Alpha

Honeycomb Toroidal Graph

Cite this as:

Weisstein, Eric W. "Honeycomb Toroidal Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/HoneycombToroidalGraph.html

Subject classifications