On the critical difference of almost bipartite graphs
- PDF / 398,672 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 37 Downloads / 214 Views
On the critical difference of almost bipartite graphs Vadim E. Levit1
· Eugen Mandrescu2
Received: 5 June 2019 / Accepted: 4 August 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract 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.
B
Vadim E. Levit [email protected]
Extended author information available on the last page of the article
123
Journal of Algebraic Combinatorics
Keywords Independent set · Core · Matching · Critical set · Critical difference · Bipartite graph · König–Egerváry graph
1 Introduction Throughout this paper, G = (V , E) is a finite, undirected, loopless graph without multiple edges, with vertex set V = V (G) of cardinality n (G) and edge set E = E(G) of size m (G). If X ⊂ V , then G[X ] is the subgraph of G spanned by X . By G − W , we mean the subgraph G[V − W ], if W ⊂ V (G). For F ⊂ E(G), by G − F we denote the subgraph of G obtained by deleting the edges of F, and we use G−e, if F = {e}. If A, B ⊂ V and A ∩ B = ∅, then (A, B) stands for the set {e = ab : a ∈ A, b ∈ B, e ∈ E}. The neighborhood of a vertex v ∈ V is the s
Data Loading...
