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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

The planar crossing number of some quartic circulant graphs

John Baptist Gauci, Cheryl Zerafa Xuereb
The Art of Discrete and Applied Mathematics
Computational Geometry and Mesh Generation
article

The planar crossing number of some quartic circulant graphs

John Baptist Gauci, Cheryl Zerafa Xuereb
article en

Abstract

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$.

The Art of Discrete and Applied MathematicsVol. 7(3)
University of Malta (MT)
Openalex Percentile: Top 55%
Computational Geometry and Mesh Generation
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.