
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.
strong equistability, Distance in graphs, Applied Mathematics, equistable graph, Equistable graphs, Distance-hereditary graphs, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), distance-hereditary graph, equistability, Discrete Mathematics and Combinatorics, Structural characterization of families of graphs
strong equistability, Distance in graphs, Applied Mathematics, equistable graph, Equistable graphs, Distance-hereditary graphs, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), distance-hereditary graph, equistability, Discrete Mathematics and Combinatorics, Structural characterization of families of graphs
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 12 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
