On \(\alpha^{+}\)-stable König-Egerváry graphs (Q1869204): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
Import240304020342 (talk | contribs)
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
    0 references
    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
    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

    Identifiers