The torus grid graph 
is the graph formed from the graph Cartesian
product 
of the cycle graphs 
and 
. By analogy with the KC graph
and KP graph, the 
trous grid graph could also be called a "CC graph."
is isomorphic to 
.
can be formed starting
with an 
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 
and 
are illustrated above.
The torus grid graphs are quartic and Hamiltonian and have vertex count
 |
(1)
|
Torus grid graphs are circulant graphs iff 
and 
are relatively prime,
i.e., 
.
In such cases, 
is isomorphic to 
.
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
 |
(2)
|
for all 
satisfying 
(Clancy et al. 2020). The conjecture is now known to hold for 
(Adamsson and Richter 2004 and earlier work
cited therein). An asymptotic lower bound of
 |
(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 
with 
for 
, 4, 5, 6 are 1, 2, 4, and 6, respectively.
The torus grid graph 
is unit-distance since it is isomorphic to
the graph Cartesian product 
, where 
is the 
-prism graph (which is itself
unit-distance).
Mertens (2024) computed the domination polynomial and numbers of dominating sets for 
torus grid graphs up to 
.
." 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. 
: A Self-Contained Proof Using Mostly Combinatorial
Arguments." Graphs Combin. 20, 247-253, 2004.Stewart,
I. Fig. 41 in