2023/08/07 by Vadim E. Levit, Levit, Vadim E., Eugen Mândrescu +1
Computer Science · Mathematics · #05C69 (Primary) 05C70 (Secondary) #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #G.2.2 #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2308.03503
openalex publication_date 2023/08/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let α(G) denote the cardinality of a maximum independent set, while μ(G) be the size of a maximum matching in G=( V,E) . Let ξ(G) denote the size of the intersection of all maximum independent sets. It is known that if α(G)+μ(G)=n(G)=\vert V\vert , then G is a König-Egerváry graph. If α(G)+μ(G)=n(G) -1, then G is a 1-König-Egerváry graph. If G is not a König-Egerváry graph, and there exists a vertex v∈ V (an edge e∈ E) such that G-v (G-e) is König-Egerváry, then G is called a vertex (an edge) almost König-Egerváry graph (respectively). The critical difference d(G) is max\d(I):I\inInd(G)\, where Ind(G) denotes the family of all independent sets of G. If A\inInd(G) with d( X) =d(G), then A is a critical independent set. Let diadem (G)=\bigcup\S:S is a critical independent set in G\, and \varrhov( G) denote the number of vertices v∈ V( G) , such that G-v is a König-Egerváry graph. In this paper, we characterize all types of almost König-Egerváry graphs and present interrelationships between them. We also show that if G is a 1-König-Egerváry graph, then \varrhov( G) ≤ n( G) +d( G) -ξ( G) -β(G), where β(G)=\vert diadem(G)\vert . As an application, we characterize the 1-König-Egerváry graphs that become König-Egerváry after deleting any vertex.