On \(\alpha^{+}\)-stable König-Egerváry graphs (Q1869204): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 05:01, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On \(\alpha^{+}\)-stable König-Egerváry graphs |
scientific article |
Statements
On \(\alpha^{+}\)-stable König-Egerváry graphs (English)
0 references
9 April 2003
0 references
The stability number \(\alpha(G)\) of a graph \(G\) is the cardinality of a stable set of maximum size in \(G\). \(G\) is said to be \(\alpha^+\)-stable if its stability number remains the same upon the addition of any edge. \(G\) is called a König-Egeráry graph if its order equals \(\alpha(G)+ \mu(G)\), where \(\mu(G)\) is the size of a maximum matching in \(G\). The paper characterizes \(\alpha^+\)-stable König-Egeráry graphs, thereby generalizing some previously known results on bipartite graphs and trees. It is also shown that a certain equality is a necessary and sufficient condition for a König-Egeráry graph to have a perfect matching.
0 references
maximum stable set
0 references
maximum matching
0 references
perfect matching
0 references
blossom
0 references
\(\alpha^+\)-stable graph
0 references
stability number
0 references