On 1-König-Egerváry Graphs

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 [12]. It is known that if α(G)+μ(G)=n(G)=V, then G is a König-Egerváry graph [5, 7, 24]. 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). For X⊆V(G), the number X-N(X) is the difference of X, denoted d(X). The critical differenced(G) is max{d(I):I∈Ind(G)}, where Ind(G) denotes the family of all independent sets of G. If A∈Ind(G) with dA=d(G), then A is a critical independent set [25]. Let diadem(G)=⋃{S:S is a critical independent set in G} [8], and ϱvG denote the number of vertices v∈VG, such that G-v is a König-Egerváry graph [22]. 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 ϱvG≤nG+dG-ξG-β(G), where β(G)=diadem(G). As an application, we characterize the 1-König-Egerváry graphs that become König-Egerváry after deleting any vertex.