Sobre a skewness do produto cartesiano de estrelas e ciclos

• Gabriel Couto UERJ
• Mauro Nigro UERJ

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

Resumo

Um grafo G é planar quando pode ser representado num plano sem que suas arestas se cruzem. A skewness do grafo G, denotada por sk(G), é o menor número de arestas que precisam ser removidas de G para que o grafo resultante seja planar. O produto cartesiano dos grafos simples G = (V(G), E(G)) e H = (V(H), E(H)) é o grafo G□H cujo conjunto de vértices é V(G) × V(H) e cujo conjunto de arestas é o conjunto de todos os pares (u₁, v₁)(u₂, v₂) de forma que ou u₁u₂ ∈ E(G) e v₁ = v₂, ou v₁v₂ ∈ E(H) e u₁ = u₂. Em 2024, Chia e Sim conjecturaram que sk(K_1,n□C_m) = (n − 2)⌊m−1/2 + 1⌋ para todo inteiro positivo n ≥ 2 e m ≥ 4. Neste artigo, provamos que para qualquer inteiro positivo n ≥ 2, sk(K_1,n□C₄) = 2(n− 2).

Referências

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.