Equistable distance-hereditary graphs
A graph is equistable if a non-negative function on its vertices exists such that a set \(S\) of vertices has total weight 1 if and only if \(S\) is maximal stable. This concept was introduced by \textit{N. V. R. Mahadev, U. N. Peled} and \textit{F. Sun} [J.\ Graph Theory 18, 281--299 (1994; Zbl 0794.05112)]. Some of the current authors (\textit{E. Korach} and \textit{U. N. Peled}) characterised equistable series-parallel graphs [Discrete Appl.\ Math.\ 132, 149--162 (2003; Zbl 1029.05132)] and (\textit{U.N. Peled} and \textit{U. Rotics}) equistable chordal graphs [ibid., 203--210 (Zbl 1029.05134)] by the absence of a bad \(P_4\), where \((a,b,c,d)\) is bad if a stable set \(S \supseteq \{a,d\}\) exists such that \(N(b) \cap N(c) \subseteq N(S)\). This extends to distance-hereditary graphs, and enables us to recognise equistable the graphs in this class in time \(O(n^5m)\). In general it is not known whether equistable graphs can be recognised in polynomial time, but deciding whether a given \(P_4\) is bad is NP-complete.
- 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
- Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
- Dominating cliques in distance-hereditary graphs
- Equistable chordal graphs
- Equistable graphs
- Equistable series-parallel graphs
- Graph classes between parity and distance-hereditary graphs
- Graph Classes: A Survey
- 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?)
- 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
- Equistable series-parallel graphs
- Equistable chordal graphs
- Twin subgraphs and core-semiperiphery-periphery structures
- (k,+)-distance-hereditary graphs
- Short proofs on the structure of general partition, equistable and triangle graphs
- Equistable graphs, general partition graphs, triangle graphs, and graph products
- Decomposing 1-Sperner hypergraphs
- Equistable simplicial, very well-covered, and line graphs
- Distance-hereditary graphs are clique-perfect
- Strong cliques and equistability of EPT graphs
- Equistarable bipartite graphs
- Recognizing k-equistable graphs in FPT time
- Equistarable graphs and counterexamples to three conjectures on equistable graphs
- On equistable, split, CIS, and related classes of graphs
- Equistable graphs
- On the Query Complexity of Estimating the Distance to Hereditary Graph Properties
- On the recognition of \(k\)-equistable graphs
- Almost distance-hereditary graphs
- Complexity results for equistable graphs and related classes
- A characterization of almost-2-distance-hereditary graphs in terms of their forbidden subgraphs
- Distance-hereditary graphs and signpost systems
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)
