On the skewness of the cartesian product of stars and cycles

• Gabriel Couto UERJ
• Mauro Nigro UERJ

DOI: https://doi.org/10.5753/etc.2025.8286

Abstract

A graph G is planar when it can be represented on a plane without its edges crossing. The skewness of a graph G, denoted by sk(G), is the minimum number of edges that need to be removed from G so that the resulting graph is planar. The cartesian product of the simple graphs G = (V(G), E(G)) and H = (V(H), E(H)) is the graph G□H whose vertex set is V(G) × V(H) and whose edge set is the set of all pairs (u₁, v₁)(u₂, v₂) such that either u₁u₂ ∈ E(G) and v₁ = v₂, or v₁v₂ ∈ E(H) and u₁ = u₂. In 2024, Chia and Sim posed the conjecture that sk(K_1,n□C_m) = (n− 2)⌊m−1/2 + 1⌋, for all positive integers n ≥ 2 and m ≥ 4. In this paper, we prove that, for all positive integer n ≥ 2, sk(K_1,n□C₄) = 2(n− 2).

References

Chia, G. and Sim, K. (2024). On the skewness of products of graphs. Discrete Applied Mathematics, pages 295–393.

Cimikowski, R. (1992). Graph planarization and skewness. Congressus Numerantium, pages 21–32.

Ding, Z. (2023). Skewness and the crossing numbers of graphs. AIMS Mathematics.

Garey, M. R. and Johnson, D. S. (1990). Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA.

Guy, R. (1972). The slimming number and genus of graphs. Canadian Mathematical Bulletin, pages 195–200.

Kuratowski, C. (1930). Sur le problème des courbes gauches en topologie. Fundamenta Mathematicae.

Neto, C. D., Schaffer, K., Xavier, E. F., Stolfi, J., Faria, L., and Figueiredo, C. M. H. (2002). The splitting number and skewness of Cn × Cm. Ars Combinatoria, 63:193–205.

Ouyang, Z., Dong, F., and Tay, E. G. (2019). On the skewness of cartesian products with trees. Discrete Applied Mathematics, pages 131–141.

Wagner, K. (1937). Über eine eigenschaft der ebenen komplexe. Mathematische Annalen.