2024/05/21 by Vadim E. Levit, Levit, Vadim E., Eugen Mândrescu +1
Computer Science · Engineering · Mathematics · #05C69 (Primary) 05C70 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Finite Group Theory Research #G.2.2 #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2405.13176
openalex publication_date 2024/05/21 · 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) . It is known that if α(G)+μ(G)=\vert V\vert , then G is a König-Egerváry graph. 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. For a graph G, 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. A graph is called almost bipartite if it has a unique odd cycle. In this paper, we show that if G is an almost bipartite non-König-Egerváry graph with the unique odd cycle C, then the following assertions are true: 1. every maximum matching of G contains \lfloor V(C)/2\rfloor edges belonging to C; 2. V(C)∪ NG[ diadem( G) ] =V and V(C)∩ NG[ diadem( G) ] =∅; 3. \varrhov( G) =\vert corona( G) \vert -\vert diadem( G) \vert , where corona( G) is the union of all maximum independent sets of G; 4. \varrhov( G) =\vert V\vert if and only if G=C2k+1 for some integer k≥1.