Connected Dominating Sets in Graphs With Stability Number Three

2017/03/20 by Vladimir Bercov, Bercov, Vladimir
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.1703.06556

openalex publication_date 2017/03/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In the special case of graphs G of independence number a(G)=3 without induced chordless cycles C7 it is shown that exists connected dominating set D of vertices with number of vertices n(D)<=4. Using the concept of connected dominating sets, we defined a new invariant h(G) that does not exceed the number of Hadwiger. For the considered graphs it is shown that h(G)>=n(G)/4.

Related

• Three domination number and connectivity in graphs
• A Note on Connected Dominating Set in Graphs Without Long Paths And Cycles
• Domination structure in 3-connected graphs
• Partial domination - the isolation number of a graph
• On the structure of dominating graphs