Hereditary Efficiently Dominatable Graphs

DOI10.1002/jgt.21685zbMath1269.05089OpenAlexW1541111991MaRDI QIDQ5325951

Martin Milanič

Publication date: 31 July 2013

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: http://www.cobiss.si/scripts/cobiss?command=DISPLAY&base=cobib&rid=1537135300&fmt=11

zbMATH Keywords

perfect codeforbidden induced subgraph characterizationhereditary graph classefficient dominationperfect dominationhereditary efficiently dominatable graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

A dichotomy for weighted efficient dominating sets with bounded degree vertices ⋮ Efficient domination through eigenvalues ⋮ Weighted Efficient Domination for $$P_6$$ -Free and for $$P_5$$ -Free Graphs ⋮ Weighted Efficient Domination for $P_5$-Free and $P_6$-Free Graphs ⋮ Graph classes with and without powers of bounded clique-width ⋮ Weighted efficient domination in two subclasses of \(P_6\)-free graphs ⋮ A note on efficient domination in a superclass of \(P_5\)-free graphs ⋮ Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs ⋮ Exact algorithms for minimum weighted dominating induced matching ⋮ Efficient domination for classes of \(P_6\)-free graphs ⋮ Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs ⋮ On efficient domination for some classes of \(H\)-free chordal graphs ⋮ On efficient domination for some classes of \(H\)-free chordal graphs ⋮ Efficient Domination for Some Subclasses of $$P_6$$ -free Graphs in Polynomial Time ⋮ On efficient domination for some classes of \(H\)-free bipartite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graphs of separability at most 2
• On rigid circuit graphs
• New graph classes of bounded clique-width
• The strong perfect graph theorem
• Claw-free graphs. IV: Decomposition theorem
• Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
• On maximal independent sets of vertices in claw-free graphs
• Trivially perfect graphs
• Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs
• A linear time algorithm to solve the weighted perfect domination problem in series-parallel graphs
• Weighted efficient domination problem on some perfect graphs
• Universally signable graphs
• Weighted domination of cocomparability graphs
• Graphs without odd holes, parachutes or proper wheels: A generalization of Meyniel graphs and of line graphs of bipartite graphs
• Stability number of bull- and chair-free graphs revisited
• A theorem of Truemper
• Decomposition of odd-hole-free graphs by double star cutsets and 2-joins
• Weighted independent perfect domination on cocomparability graphs
• The weighted perfect domination problem and its variants
• Quasi-threshold graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Perfect codes in graphs
• Even-hole-free graphs part I: Decomposition theorem
• A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs
• Efficient Edge Domination on Hole-Free Graphs in Polynomial Time
• The Complexity of the Partial Order Dimension Problem
• Even and odd holes in cap-free graphs
• Independent Sets in Asteroidal Triple-Free Graphs
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• 1-perfect codes in Sierpiński graphs
• A structure theorem for graphs with no cycle with a unique chord and its consequences
• Difference graphs