mathworld.wolfram.com

Torus Grid Graph -- from Wolfram MathWorld

  • ️Weisstein, Eric W.
  • ️Mon Mar 07 2016
Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology Alphabetical Index New in MathWorld

The torus grid graph T_(m,n) is the graph formed from the graph Cartesian product C_m square C_n of the cycle graphs C_m and C_n. By analogy with the KC graph and KP graph, the m×n trous grid graph could also be called a "CC graph."

C_m square C_n is isomorphic to C_n square C_m.

TorusGridGraph3DEmbeddings

C_m square C_n can be formed starting with an m×n grid graph and connecting corresponding left/right and top/bottom vertex pairs with edges. While such an embedding has overlapping edges in the plane, it can naturally be placed on the surface of a torus with no edge intersections or overlaps. Torus grid graphs are therefore toroidal graphs. The isomorphic torus grid graphs C_(10) square C_6 and C_6 square C_(10) are illustrated above.

The torus grid graphs are quartic and Hamiltonian and have vertex count

|C_m square C_n|=mn.

(1)

TorusGridGraph

Torus grid graphs are circulant graphs iff m and n are relatively prime, i.e., (m,n)=1. In such cases, T_(m,n) is isomorphic to Ci_(mn)(m,n). Special cases are summarized in the following table and illustrated above in attractive (but non-toroidal) embddings.

Harary et al. (1973) conjectured that the graph crossing number is given by

cr(C_m square C_n)=(m-2)n

(2)

for all m,n satisfying n>=m>=3 (Clancy et al. 2019). The conjecture is now known to hold for n>=7>=m>=3 (Adamsson and Richter 2004 and earlier work cited therein). An asymptotic lower bound of

cr(C_m square C_n)>=(0.8-epsilon)mn

(3)

was given by Salazar and Ugalde (2004). Clancy et al. (2019) summarize additional results and details.

Riskin (2001) showed that the Klein bottle crossing numbers of C_m square C_n with m<=n for m=3, 4, 5, 6 are 1, 2, 4, and 6, respectively.

The torus grid graph C_4 square C_n is unit-distance since it is isomorphic to the graph Cartesian product Y_n square K_2, where Y_n is the n-prism graph (which is itself unit-distance).

Mertens (2024) computed the domination polynomial and numbers of dominating sets for n×n torus grid graphs up to n=17.

See also

Graph Cartesian Product, Grid Graph, Toroidal Graph

Explore with Wolfram|Alpha

References

Adamsson, J. and Richter, R. B. "Arrangements, Circular Arrangements and the Crossing Number of C_7×C_n." J. Combin. Theory 90, 21-39, 2004.Harary, F.; Kainen, P. C.; and Schwenk, A. J. "Toroidal Graphs with Arbitrarily High Crossing Numbers." Nanta Math. 6, 58-67, 1973.Clancy, K.; Haythorpe, M.; and Newcombe, A. §3.1.1 in "A Survey of Graphs with Known or Bounded Crossing Numbers." 15 Feb 2019. https://arxiv.org/abs/1901.05155.Lawrencenko, S. and Negami, S. "Constructing the Graphs That Triangulate Both the Torus and the Klein Bottle." J. Combin. Theory Ser. B 77, 211-2218, 1999.Mertens, S. "Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph." 15 Aug 2024. https://arxiv.org/abs/2408.08053.Pach, J. and Tóth, G. "Crossing Number of Toroidal Graphs." In International Symposium on Graph Drawing (Ed. P. Healy and N. S. Nikolov). Berlin, Heidelberg: Springer-Verlag: pp. 334-342, 2005.Riskin, A. "On the Nonembeddability and Crossing Numbers of Some Toroidal Graphs on the Klein Bottle." Disc. Math. 234, 77-88, 2001.Salazar, G. and Ugalde, E. "An Improved Bound for the Crossing Number of C_m×C_n: A Self-Contained Proof Using Mostly Combinatorial Arguments." Graphs Combin. 20, 247-253, 2004.Stewart, I. Fig. 41 in How to Cut a Cake: And Other Mathematical Conundrums. Oxford, England: Oxford University Press, 2006.

Cite this as:

Weisstein, Eric W. "Torus Grid Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/TorusGridGraph.html

Subject classifications