Complete description of forbidden subgraphs in the structural domination problem

DOI10.1016/J.DISC.2008.05.053zbMath1210.05093OpenAlexW2046940797MaRDI QIDQ1025505

Gábor Bacsó

Publication date: 19 June 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2008.05.053

zbMATH Keywords

connected graphsgraph domination

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Connectivity (05C40)

Related Items (14)

Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time ⋮ The complexity of connected dominating sets and total dominating sets with specified induced subgraphs ⋮ On graphs for which the connected domination number is at most the total domination number ⋮ A note on connected dominating sets of distance-hereditary graphs ⋮ Distance domination versus iterated domination ⋮ On the existence of total dominating subgraphs with a prescribed additive hereditary property ⋮ On dominating sets whose induced subgraphs have a bounded diameter ⋮ Transversals and domination in uniform hypergraphs ⋮ Structural domination and coloring of some \(( P_7 , C_7)\)-free graphs ⋮ Infinite versus finite graph domination ⋮ On maximum independent sets in \(P_{5}\)-free graphs ⋮ Connected Domination ⋮ Domination, coloring and stability in \(P_5\)-reducible graphs ⋮ On connected dominating sets of restricted diameter

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Domination properties and induced subgraphs
• Introduction to ``Topics on Domination
• Characterization of graphs dominated by induced paths
• The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree
• On the existence of two non-neighboring subgraphs in a graph
• Maximum induced trees in graphs
• Star-cutsets and perfect graphs
• Dominating cliques in \(P_ 5\)-free graphs
• On \(m\)-centers in \(P_ t\)-free graphs
• Dominating subgraphs in graphs with some forbidden structures
• On a property of the class of n-colorable graphs
• A characterization of graphs without long induced paths
• Hereditary Domination in Graphs: Characterization with Forbidden Induced Subgraphs
• The Comparability Graph of a Tree
• Dominating sets with small clique covering number
• Perfect connected-dominant graphs
• Graphs without induced P₅and C₅
• Some results on graphs without long induced paths
• Dominating Bipartite Subgraphs in Graphs
• Dominating cliques in graphs

This page was built for publication: Complete description of forbidden subgraphs in the structural domination problem