Equistable distance-hereditary graphs

DOI10.1016/J.DAM.2006.06.018MaRDI QIDQ2473043zbMATH OpenOpenAlexFDO

Authors Ephraim Korach, Udi Rotics, Uri N. Peled

Publication date 26 February 2008

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

Full work available at URL https://doi.org/10.1016/j.dam.2006.06.018

zbMATH Keywords

equistable graphdistance-hereditary graphequistabilitystrong equistability

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distance in graphs (05C12) Structural characterization of families of graphs (05C75)

Recommendations

• Equistable series-parallel graphs
• Equistable graphs
• Equistarable graphs and counterexamples to three conjectures on equistable graphs
• On the recognition of \(k\)-equistable graphs
• Equistable chordal graphs

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3561379 (Why is no real title available?)
• scientific article; zbMATH DE number 553917 (Why is no real title available?)
• scientific article; zbMATH DE number 1500541 (Why is no real title available?)
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• A class of threshold and domishold graphs: Equistable and equidominating graphs
• A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
• A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
• A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
• Compact-port routing models and applications to distance-hereditary graphs
• Completely separable graphs
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• Distance-hereditary graphs
• Dominating cliques in distance-hereditary graphs
• Equistable chordal graphs
• Equistable graphs
• Equistable series-parallel graphs
• Graph Classes: A Survey
• Graph classes between parity and distance-hereditary graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• On the clique-width of some perfect graph classes
• Polynomial time algorithms for Hamiltonian problems on bipartite distance-hereditary graphs
• Threshold graphs and related topics
• Topology of series-parallel networks

Cited in

(19)

• Short proofs on the structure of general partition, equistable and triangle graphs
• Twin subgraphs and core-semiperiphery-periphery structures
• Strong cliques and equistability of EPT graphs
• Distance-hereditary graphs and signpost systems
• Equistarable bipartite graphs
• On equistable, split, CIS, and related classes of graphs
• Complexity results for equistable graphs and related classes
• (k,+)-distance-hereditary graphs
• Equistable series-parallel graphs
• Equistable chordal graphs
• Recognizing k-equistable graphs in FPT time
• Equistarable graphs and counterexamples to three conjectures on equistable graphs
• On the recognition of \(k\)-equistable graphs
• Equistable graphs, general partition graphs, triangle graphs, and graph products
• On the Query Complexity of Estimating the Distance to Hereditary Graph Properties
• Equistable simplicial, very well-covered, and line graphs
• Almost distance-hereditary graphs
• Decomposing 1-Sperner hypergraphs
• Distance-hereditary graphs are clique-perfect

This page was built for publication: Equistable distance-hereditary graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2473043)