What question did this study set out to answer?

To establish a lower bound for the 2-domination number in terms of the radius of a connected graph.

July 31, 20260 citationsOpen Access

The 2-domination number is at least the radius

Key Points

To establish a lower bound for the 2-domination number in terms of the radius of a connected graph.
Defined a 2-dominating set and its properties in connected graphs.
Introduced a portable absorption construction to create a spanning tree with the desired radius.
Characterized extremal graphs, including even cycles and blob cycles.
Proved that the 2-domination number gamma_2(G) is at least the radius of G, i.e., gamma_2(G) >= rad(G).
Demonstrated that for every 2-dominating set, a vertex can be found that maintains a distance condition to all other vertices in the set.
Identified classes of graphs, such as even cycles, where the bound is sharp.

Abstract

Let G be a connected graph. A set S of vertices is 2-dominating if everyvertex outside S has at least two neighbors in S, and gamma₂ (G) is theminimum size of such a set. We prove that gamma₂ (G) >= rad (G). In fact weprove the stronger statement that every 2-dominating set S admits a vertex cwith d (c, x) <= |S|-1 for all x in S, so that rad (G) <= |S|. The bound issharp: even cycles satisfy gamma₂ = rad, and we characterize the extremalgraphs of radius at least 3 (the "blob cycles"). The proof introduces a portabsorption construction, which builds from a 2-dominating set a spanning treecontaining it whose radius is at most |S|-1. Preprint. To the best of our knowledge no lower bound on gamma₂ in terms ofthe radius has previously appeared; this claim awaits independent humanrefereeing. Results were found with the aid of an automatedconjecture-and-verification system and every proof has since been written andaudited by hand.

Ask AI

Helpful

Bookmark

View Full Paper