Domination in 4-Regular Graphs With No Induced 4-Cycles

Michael A. Henning; Anders Yeo

doi:10.1002/jgt.70013

Domination in 4-Regular Graphs With No Induced 4-Cycles

Mathematics and Applied Mathematics

University of Southern Denmark

Research output: Contribution to journal › Article › peer-review

Abstract

A set (Formula presented.) of vertices in a graph (Formula presented.) is a dominating set of (Formula presented.) if every vertex not in (Formula presented.) is adjacent to a vertex in (Formula presented.). The domination number of (Formula presented.), denoted by (Formula presented.), is the minimum cardinality of a dominating set in (Formula presented.). The (Formula presented.) -conjecture for domination in 4-regular graphs states that if (Formula presented.) is a 4-regular graph of order (Formula presented.), then (Formula presented.). We prove this conjecture when (Formula presented.) has no induced 4-cycle.

Original language	English
Journal	Journal of Graph Theory
DOIs	https://doi.org/10.1002/jgt.70013
Publication status	Accepted/In press - 2026

Keywords

4-cycles
4-regular graph
domination number

ASJC Scopus subject areas

Geometry and Topology
Discrete Mathematics and Combinatorics

Access to Document

10.1002/jgt.70013

Cite this

@article{154216c0d37044a49f72447399a03703,

title = "Domination in 4-Regular Graphs With No Induced 4-Cycles",

abstract = "A set (Formula presented.) of vertices in a graph (Formula presented.) is a dominating set of (Formula presented.) if every vertex not in (Formula presented.) is adjacent to a vertex in (Formula presented.). The domination number of (Formula presented.), denoted by (Formula presented.), is the minimum cardinality of a dominating set in (Formula presented.). The (Formula presented.) -conjecture for domination in 4-regular graphs states that if (Formula presented.) is a 4-regular graph of order (Formula presented.), then (Formula presented.). We prove this conjecture when (Formula presented.) has no induced 4-cycle.",

keywords = "4-cycles, 4-regular graph, domination number",

author = "Henning, \{Michael A.\} and Anders Yeo",

note = "Publisher Copyright: {\textcopyright} 2026 The Author(s). Journal of Graph Theory published by Wiley Periodicals LLC.",

year = "2026",

doi = "10.1002/jgt.70013",

language = "English",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

}

TY - JOUR

T1 - Domination in 4-Regular Graphs With No Induced 4-Cycles

AU - Henning, Michael A.

AU - Yeo, Anders

PY - 2026

Y1 - 2026

N2 - A set (Formula presented.) of vertices in a graph (Formula presented.) is a dominating set of (Formula presented.) if every vertex not in (Formula presented.) is adjacent to a vertex in (Formula presented.). The domination number of (Formula presented.), denoted by (Formula presented.), is the minimum cardinality of a dominating set in (Formula presented.). The (Formula presented.) -conjecture for domination in 4-regular graphs states that if (Formula presented.) is a 4-regular graph of order (Formula presented.), then (Formula presented.). We prove this conjecture when (Formula presented.) has no induced 4-cycle.

AB - A set (Formula presented.) of vertices in a graph (Formula presented.) is a dominating set of (Formula presented.) if every vertex not in (Formula presented.) is adjacent to a vertex in (Formula presented.). The domination number of (Formula presented.), denoted by (Formula presented.), is the minimum cardinality of a dominating set in (Formula presented.). The (Formula presented.) -conjecture for domination in 4-regular graphs states that if (Formula presented.) is a 4-regular graph of order (Formula presented.), then (Formula presented.). We prove this conjecture when (Formula presented.) has no induced 4-cycle.

KW - 4-cycles

KW - 4-regular graph

KW - domination number

UR - https://www.scopus.com/pages/publications/105032158161

U2 - 10.1002/jgt.70013

DO - 10.1002/jgt.70013

M3 - Article

AN - SCOPUS:105032158161

SN - 0364-9024

JO - Journal of Graph Theory

JF - Journal of Graph Theory

ER -

Domination in 4-Regular Graphs With No Induced 4-Cycles

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this