On $α^{++}$-Stable Graphs
| dc.creator | Levit, Vadim E. | |
| dc.creator | Mandrescu, Eugen | |
| dc.date | 2000-03-09 | |
| dc.date.accessioned | 2026-07-07T04:34:15Z | |
| dc.date.available | 2026-07-07T04:34:15Z | |
| dc.description | The stability number of a graph G, denoted by alpha(G), is the cardinality of a stable set of maximum size in G. A graph is well-covered if every maximal stable set has the same size. G is a Koenig-Egervary graph if its order equals alpha(G) + mu(G), where mu(G) is the cardinality of a maximum matching in G. In this paper we characterize $α^{++}$-stable graphs, namely, the graphs whose stability numbers are invariant to adding any two edges from their complements. We show that a König-Egerváry graph is $α^{++}$-stable if and only if it has a perfect matching consisting of pendant edges and no four vertices of the graph span a cycle. As a corollary it gives necessary and sufficient conditions for $α^{++}$-stability of bipartite graphs and trees. For instance, we prove that a bipartite graph is $α^{++}$-stable if and only if it is well-covered and C4-free. | |
| dc.description | 11 pages, 3 figures | |
| dc.identifier | https://arxiv.org/abs/math/0003057 | |
| dc.identifier | http://arxiv.org/abs/math/0003057 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/58832 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C69, 05C70 (Primary) 05C05, 05C75 (Secondary) | |
| dc.title | On $α^{++}$-Stable Graphs | |
| dc.type | text |