Hereditary Efficiently Dominatable Graphs
From MaRDI portal
Publication:5325951
DOI10.1002/jgt.21685zbMath1269.05089OpenAlexW1541111991MaRDI QIDQ5325951
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
perfect codeforbidden induced subgraph characterizationhereditary graph classefficient dominationperfect dominationhereditary efficiently dominatable graph
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