On $α$-Critical Edges in König-Egerváry Graphs
| dc.creator | Levit, Vadim E. | |
| dc.creator | Mandrescu, Eugen | |
| dc.date | 2000-02-10 | |
| dc.date.accessioned | 2026-07-07T04:33:39Z | |
| dc.date.available | 2026-07-07T04:33:39Z | |
| 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. If alpha(G-e) > alpha(G), then e is an alpha-critical edge, and if mu(G-e) < mu(G), then e is a mu-critical edge, where mu(G) is the cardinality of a maximum matching in G. G is a Koenig-Egervary graph if alpha(G) + mu(G) equals its order. Beineke, Harary and Plummer have shown that the set of alpha-critical edges of a bipartite graph is a matching. In this paper we generalize this statement to Koenig-Egervary graphs. We also prove that in a Koenig-Egervary graph alpha-critical edges are also mu-critical, and that they coincide in bipartite graphs. We obtain that for any tree its stability number equals the sum of the cardinality of the set of its alpha-critical vertices and the size of the set of its alpha-critical edges. Eventually, we characterize the Koenig-Egervary graphs enjoying this property. | |
| dc.description | 15 pages, 10 figures | |
| dc.identifier | https://arxiv.org/abs/math/0002070 | |
| dc.identifier | http://arxiv.org/abs/math/0002070 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/58659 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C69, 05C70 (Primary) 05C05, 05C75 (Secondary) | |
| dc.title | On $α$-Critical Edges in König-Egerváry Graphs | |
| dc.type | text |