The planar crossing number of some quartic circulant graphs
For distinct integers $n>b>a$, the quartic circulant graph $Ci(n; \{a, b\})$ is the graph on the vertices $\{x_{1}, x_{2},...,x_{n}\}$, such that $x_{i}$ is adjacent to the vertices in the set $\{x_{i+a}, x_{i-a}, x_{i+b}, x_{i-b}\}$ (where operations in the indices are taken modulo $n$, with complete residue system $\{1,...,n\}$). We prove a conjecture of Wang and Huang [2008] on the crossing number of $Ci(3k-1;\{1,k\})$ for $k\geq 3$. We also determine the crossing number of $Ci(n;\{1,2\})$ for all values of $n$, the crossing number of $Ci(2k+1;\{1,k\})$ for $k\geq 3$ and we initiate the study of the crossing number of $Ci(n;\{a,k\})$ for values of $a$ not equal to 1. In particular, we show that the crossing number of $Ci(3k;\{h,k\})$, for $k>h$, $k\neq 2h$, is equal to $k$ when $h\in \{2,3,4\}$, and conjecture that it is also $k$ for $h\geq 5$.
Authors
- John Baptist Gauci (ORCID: https://orcid.org/0000-0001-6584-8473)
- Cheryl Zerafa Xuereb
Institutions
- University of Malta (MT)
Publication Details
- Journal
- The Art of Discrete and Applied Mathematics
- Published
- 2024-11-28
- DOI
- https://doi.org/10.26493/2590-9770.1612.e36
- Primary Topic
- Computational Geometry and Mesh Generation
- Type
- article
- Field-Weighted Citation Impact
- 0.00