Article in volume
Authors:
Title:
The crossing number of hexagonal graph $H_{3,n}$ in the projective plane
PDFSource:
Discussiones Mathematicae Graph Theory 42(1) (2022) 197-218
Received: 2019-03-12 , Revised: 2019-08-18 , Accepted: 2019-09-10 , Available online: 2019-11-05 , https://doi.org/10.7151/dmgt.2251
Abstract:
Thomassen described all (except finitely many) regular tilings of the torus
$S_1$ and the Klein bottle $N_2$ into (3,6)-tilings, (4,4)-tilings and
(6,3)-tilings. Many researchers made great efforts to investigate the crossing
number of the Cartesian product of an $m$-cycle and an $n$-cycle, which is a
special kind of (4,4)-tilings, either in the plane or in the projective plane.
In this paper we study the crossing number of the hexagonal graph $H_{3,n}$
$(n\ge 2)$, which is a special kind of (3,6)-tilings, in the projective plane,
and prove that
$$
cr_{N_1}(H_{3,n})= \left\{
\begin{array}{ll}
0, \quad & n=2, \\
n-1, \quad & n\ge 3.
\end{array}\right.
$$
Keywords:
projective plane, crossing number, hexagonal graph, drawing
References:
- J. Adamsson and R.B. Richter, Arrangements, circular arrangements and the crossing number of $C_7\square C_n$, J. Combin. Theory Ser. B 90 (2004) 21–39.
https://doi.org/10.1016/j.jctb.2003.05.001 - L.W. Beineke and R.D. Ringeisen, On the crossing numbers of products of cycles and graphs of order four, J. Graph Theory 4 (1980) 145–155.
https://doi.org/10.1002/jgt.3190040203 - M.R. Garey and D.S. Johnson, Crossing number is NP-complete, SIAM J. Algebraic Discrete Methods 4 (1983) 312–316.
https://doi.org/10.1137/0604033 - L.Y. Glebsky and G. Salazar, The crossing number of $C_m\square C_n$ is as conjectured for $n\ge m(m+1)$, J. Graph Theory 47 (2004) 53–72.
https://doi.org/10.1002/jgt.20016 - P.T. Ho, The crossing number of $K_{4,n}$ on the real projective plane, Discrete Math. 304 (2005) 23–34.
https://doi.org/10.1016/j.disc.2005.09.010 - P.T. Ho, A proof of the crossing number of $K_{3,n}$ in a surface, Discuss. Math. Graph Theory 27 (2007) 549–551.
https://doi.org/10.7151/dmgt.1379 - P.T. Ho, The toroidal crossing number of $K_{4,n}$, Discrete Math. 309 (2009) 3238–3248.
https://doi.org/10.1016/j.disc.2008.09.029 - P.T. Ho, The projective plane crossing number of the circulant graph $C(3k;\{1,k\})$, Discuss. Math. Graph Theory 32 (2012) 91–108.
https://doi.org/10.7151/dmgt.1588 - M. Klešč, R.B. Ritcher, I. Stobert, The crossing number of $C_5× C_n$, J. Graph Theory 22 (1996) 239–243.
https://doi.org/10.1002/(SICI)1097-0118(199607)22:3<239::AID-JGT4>3.0.CO;2-N - B. Mohar and C. Thomassen, Graphs on Surfaces (Johns Hopkins Univ. Press, Baltimore, 2001).
- R.B. Richter, G. Salazar, The crossing number of $C_6× C_n$, Australas. J. Combin. 23 (2001) 135–143.
- R.B. Richter and J. Širáň, The crossing number of $K_{3,n}$ in a surface, J. Graph Theory 21 (1996) 51–54.
https://doi.org/10.1002/(SICI)1097-0118(199601)21:1<51::AID-JGT7>3.3.CO;2-6 - R.D. Ringeisen and L.W. Beineke, The crossing number of $C_3× C_n$, J. Combin. Theory Ser. B 24 (1978) 134–136.
https://doi.org/10.1016/0095-8956(78)90014-X - A. Riskin, The projective plane crossing number of $C_3× C_n$, J. Graph Theory 17 (1993) 683–693.
https://doi.org/10.1002/jgt.3190170605 - A. Riskin, The genus $2$ crossing number of $K_9$, Discrete Math. 145 (1995) 211–227.
https://doi.org/10.1016/0012-365X(94)00037-J - C. Thomassen, Tilings of the torus and the Klein bottle and vertex-transitive graphs on a fixed surface, Trans. Amer. Math. Soc. 323 (1991) 605–635.
https://doi.org/10.1090/S0002-9947-1991-1040045-3 - J. Wang, Z. Ouyang and Y. Huang, The crossing number of the hexagonal graph $H_{3,n}$, Discuss. Math. Graph Theory 39 (2019) 547–554.
https://doi.org/10.7151/dmgt.2092
Close