Domination of subcubic planar graphs with large girth

Since Reed conjectured in 1996 that the domination number of a connected cubic graph of order n is at most ⌈1/3n⌉, thedomination number of cubic graphs has been extensively studied. It is now known that the conjecture is false in general, but Henning and Dorbec showed that it holds for graphs with girth at least 9. Zhu and Wu stated an analogous conjecture for 2-connected cubic planar graphs. In this paper, we present a new upper bound for the domination number of subcubic planar graphs: if G is a subcubic planar graph with girth at least 8, then γ(G) < n₀ + 3/4 n₁ + 11/20 n₂ + 7/20 n₃, where ni denotes the number of vertices in G of degree i, for i ∈ {0, 1, 2, 3}. We also prove that if G is a subcubic planar graph with girth at least 9, then γ(G) < n₀ + 13/17 n₁ + 9/17 n₂ + 6/17 n₃.

Authors

Institutions

Publication Details

Journal
Ars Mathematica Contemporanea
Published
2025-02-06
DOI
https://doi.org/10.26493/1855-3974.3389.86c
Primary Topic
Advanced Graph Theory Research
Type
article
Field-Weighted Citation Impact
0.00

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Domination of subcubic planar graphs with large girth

Eric Culver, Stephen G. Hartke, Eun‐Kyung Cho, Vesna Iršič Chenoweth
Ars Mathematica Contemporanea
Advanced Graph Theory Research
article

Domination of subcubic planar graphs with large girth

Eric Culver, Stephen G. Hartke, Eun‐Kyung Cho, Vesna Iršič Chenoweth
article en

Abstract

Since Reed conjectured in 1996 that the domination number of a connected cubic graph of order n is at most ⌈1/3n⌉, thedomination number of cubic graphs has been extensively studied. It is now known that the conjecture is false in general, but Henning and Dorbec showed that it holds for graphs with girth at least 9. Zhu and Wu stated an analogous conjecture for 2-connected cubic planar graphs. In this paper, we present a new upper bound for the domination number of subcubic planar graphs: if G is a subcubic planar graph with girth at least 8, then γ(G) < n₀ + 3/4 n₁ + 11/20 n₂ + 7/20 n₃, where ni denotes the number of vertices in G of degree i, for i ∈ {0, 1, 2, 3}. We also prove that if G is a subcubic planar graph with girth at least 9, then γ(G) < n₀ + 13/17 n₁ + 9/17 n₂ + 6/17 n₃.

Ars Mathematica ContemporaneaVol. 26(2)
Brigham Young University (US), Institute of Mathematics, Physics, and Mechanics (SI), Hanyang University (KR), University of Colorado Denver (US)
National Science Foundation, European Commission, National Research Foundation, National Research Foundation of Korea, Javna Agencija za Raziskovalno Dejavnost RS
Climate action
Openalex Percentile: Top 97%
Advanced Graph Theory Research
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.