TY - JOUR

T1 - On the critical difference of almost bipartite graphs

AU - Levit, Vadim E.

AU - Mandrescu, Eugen

N1 - Publisher Copyright:
© 2020, Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2022/8

Y1 - 2022/8

N2 - A set S⊆ V is independent in a graph G= (V, E) if no two vertices from S are adjacent. The independence numberα(G) is the cardinality of a maximum independent set, while μ(G) is the size of a maximum matching in G. If α(G) + μ(G) equals the order of G, then G is called a König–Egerváry graph (Deming in Discrete Math 27:23–33, 1979; Sterboul in J Combin Theory Ser B 27:228–229, 1979). The number d(G) = max { | A| - | N(A) | : A⊆ V} is called the critical difference of G (Zhang in SIAM J Discrete Math 3:431–438, 1990) (where N(A) = { v: v∈ V, N(v) ∩ A≠ ∅ }). It is known that α(G) - μ(G) ≤ d(G) holds for every graph (Levit and Mandrescu in SIAM J Discrete Math 26:399–403, 2012; Lorentzen in Notes on covering of arcs by nodes in an undirected graph, Technical report ORC 66-16. University of California, Berkeley, CA, Operations Research Center, 1966; Schrijver in Combinatorial optimization. Springer, Berlin, 2003). In Levit and Mandrescu (Graphs Combin 28:243–250, 2012), it was shown that d(G) = α(G) - μ(G) is true for every König–Egerváry graph. A graph G is (i) unicyclic if it has a unique cycle and (ii) almost bipartite if it has only one odd cycle. It was conjectured in Levit and Mandrescu (in: Abstracts of the SIAM conference on discrete mathematics, Halifax, Canada, p 40, abstract MS21, 2012, 3rd international conference on discrete mathematics, June 10–14, Karnatak University. Dharwad, India, 2013) and validated in Bhattacharya et al. (Discrete Math 341:1561–1572, 2018) that d(G) = α(G) - μ(G) holds for every unicyclic non-König–Egerváry graph G. In this paper, we prove that if G is an almost bipartite graph of order n(G) , then α(G) + μ(G) ∈ { n(G) - 1 , n(G) }. Moreover, for each of these two values, we characterize the corresponding graphs. Further, using these findings, we show that the critical difference of an almost bipartite graph G satisfies d(G)=α(G)-μ(G)=|core(G)|-|N(core(G))|,where by core(G) we mean the intersection of all maximum independent sets.

AB - A set S⊆ V is independent in a graph G= (V, E) if no two vertices from S are adjacent. The independence numberα(G) is the cardinality of a maximum independent set, while μ(G) is the size of a maximum matching in G. If α(G) + μ(G) equals the order of G, then G is called a König–Egerváry graph (Deming in Discrete Math 27:23–33, 1979; Sterboul in J Combin Theory Ser B 27:228–229, 1979). The number d(G) = max { | A| - | N(A) | : A⊆ V} is called the critical difference of G (Zhang in SIAM J Discrete Math 3:431–438, 1990) (where N(A) = { v: v∈ V, N(v) ∩ A≠ ∅ }). It is known that α(G) - μ(G) ≤ d(G) holds for every graph (Levit and Mandrescu in SIAM J Discrete Math 26:399–403, 2012; Lorentzen in Notes on covering of arcs by nodes in an undirected graph, Technical report ORC 66-16. University of California, Berkeley, CA, Operations Research Center, 1966; Schrijver in Combinatorial optimization. Springer, Berlin, 2003). In Levit and Mandrescu (Graphs Combin 28:243–250, 2012), it was shown that d(G) = α(G) - μ(G) is true for every König–Egerváry graph. A graph G is (i) unicyclic if it has a unique cycle and (ii) almost bipartite if it has only one odd cycle. It was conjectured in Levit and Mandrescu (in: Abstracts of the SIAM conference on discrete mathematics, Halifax, Canada, p 40, abstract MS21, 2012, 3rd international conference on discrete mathematics, June 10–14, Karnatak University. Dharwad, India, 2013) and validated in Bhattacharya et al. (Discrete Math 341:1561–1572, 2018) that d(G) = α(G) - μ(G) holds for every unicyclic non-König–Egerváry graph G. In this paper, we prove that if G is an almost bipartite graph of order n(G) , then α(G) + μ(G) ∈ { n(G) - 1 , n(G) }. Moreover, for each of these two values, we characterize the corresponding graphs. Further, using these findings, we show that the critical difference of an almost bipartite graph G satisfies d(G)=α(G)-μ(G)=|core(G)|-|N(core(G))|,where by core(G) we mean the intersection of all maximum independent sets.

KW - Bipartite graph

KW - Core

KW - Critical difference

KW - Critical set

KW - Independent set

KW - König–Egerváry graph

KW - Matching

UR - http://www.scopus.com/inward/record.url?scp=85090233344&partnerID=8YFLogxK

U2 - 10.1007/s10801-020-00968-x

DO - 10.1007/s10801-020-00968-x

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:85090233344

SN - 0925-9899

VL - 56

SP - 59

EP - 73

JO - Journal of Algebraic Combinatorics

JF - Journal of Algebraic Combinatorics

IS - 1

ER -