Name
Abstract | ||
|---|---|---|
A stable set $I$ of a graph $G$ is called $k$-extendable, $k \,{\ge}\, 1$, if there exists a stable set $X \,{\subseteq}\,V(G) {\setminus} I$ such that $|X| \,{\le}\, k$ and $|N(X) \,{\cap}\, I| \,{extendable if every stable set in $G$, which is not maximum, is $k$-extendable. Let us denote by ${\rm E}(k)$ the class of all $k$-extendable graphs.We present a finite forbidden induced subgraph characterization of the maximal hereditary subclass ${\rm PE}(k)$ in ${\rm E}(k)$ for every $k \,{\ge}\,1$.Thus, we define a hierarchy ${\rm PE}(1) \,{\subset}\, {\rm PE}(2) \,{\subset}\,{\cdots}\,{ \subset}\, {\rm PE}(k) \,{\subset}\,{ \cdots}\,$ of hereditary classes of graphs, in each of which a maximum stable set can be found in polynomial time. The hierarchy covers all graphs, and all its classes can be recognized in polynomial time. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1017/S0963548304006376 | Combinatorics, Probability & Computing |
Keywords | Field | DocType |
maximal hereditary subclass,hereditary class,maximum stable set,rm pe,rm e,extendable graph,polynomial time,induced subgraph characterization,stable set | Graph,Discrete mathematics,Combinatorics,Induced subgraph,Independent set,Mathematics | Journal |
Volume | Issue | ISSN |
14 | 3 | 0963-5483 |
Citations | PageRank | References |
3 | 0.47 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter L. Hammer | 1 | 1996 | 288.93 |
| Igor E. Zverovich | 2 | 177 | 25.35 |