Large domination number in connected bipartite subcubic graphs

Zenodo (CERN European Organization for Nuclear Research) 2026 Preprint Open access

Read full text
Authors: Kaled Ben Razine
DOI: 10.5281/zenodo.18529460
Cited by: 0

Abstract

We construct an explicit infinite family of connected bipartite subcubic graphs \(G_k\) with \(|V(G_k)| = 4k+1\) and domination number \(\gamma(G_k) = 2k\). This shows that the classical bound \(\gamma(G) \leq |V(G)|/2\) is asymptotically tight even under strong structural constraints: connectivity, bipartiteness, and maximum degree at most 3.

Fields of Study & Subjects

Advanced Graph Theory Research Graph Labeling and Dimension Problems Complexity and Algorithms in Graphs

Publication details

Journal / source
Zenodo (CERN European Organization for Nuclear Research)
Publication date
9 February 2026
Document type
Preprint