On $α$-Square-Stable Graphs
| dc.creator | Levit, Vadim E. | |
| dc.creator | Mandrescu, Eugen | |
| dc.date | 1999-12-30 | |
| dc.date.accessioned | 2026-07-07T05:32:33Z | |
| dc.date.available | 2026-07-07T05:32:33Z | |
| dc.description | The stability number of a graph G, denoted by alpha(G), is the cardinality of a maximum stable set, and mu(G) is the cardinality of a maximum matching in G. If alpha(G) + mu(G) equals its order, then G is a Koenig-Egervary graph. We call G an $α$-square-stable graph, shortly square-stable, if alpha(G) = alpha(G*G), where G*G denotes the second power of G. These graphs were first investigated by Randerath and Wolkmann. In this paper we obtain several new characterizations of square-stable graphs. We also show that G is an square-stable Koenig-Egervary graph if and only if it has a perfect matching consisting of pendant edges. Moreover, we find that well-covered trees are exactly square-stable trees. To verify this result we give a new proof of one Ravindra's theorem describing well-covered trees. | |
| dc.description | 13 pages, 6 figures | |
| dc.identifier | https://arxiv.org/abs/math/9912234 | |
| dc.identifier | http://arxiv.org/abs/math/9912234 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/79698 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C75, 05C69 (Primary) 05C05, 05C70 (Secondary) | |
| dc.title | On $α$-Square-Stable Graphs | |
| dc.type | text |