Details

Autor(en) / Beteiligte

• Akbari, A.
• Akbari, S.
• Doosthosseini, A.
• Hadizadeh, Z.
• Henning, Michael A.
• Naraghi, A.

Titel

Independent domination in subcubic graphs

Ist Teil von

• Journal of combinatorial optimization, 2022, Vol.43 (1), p.28-41

Ort / Verlag

New York: Springer US

Erscheinungsjahr

2022

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• A set S of vertices in a graph G is a dominating set if every vertex not in S is adjacent to a vertex in  S . If, in addition, S is an independent set, then S is an independent dominating set. The independent domination number i ( G ) of G is the minimum cardinality of an independent dominating set in G . In Goddard and Henning (Discrete Math 313:839–854, 2013) conjectured that if G is a connected cubic graph of order  n , then i ( G ) ≤ 3 8 n , except if G is the complete bipartite graph K 3 , 3 or the 5-prism C 5 □ K 2 . Further they construct two infinite families of connected cubic graphs with independent domination three-eighths their order. In this paper, we provide a new family of connected cubic graphs G of order n such that i ( G ) = 3 8 n . We also show that if G is a subcubic graph of order n with no isolated vertex, then i ( G ) ≤ 1 2 n , and we characterize the graphs achieving equality in this bound.