On the critical difference of almost bipartite graphs

DOI10.1007/S10801-020-00968-XzbMATH Open1493.05233arXiv1905.09462OpenAlexW3083137321MaRDI QIDQ2159389FDOQ2159389

Authors: Vadim E. Levit, Eugen Mandrescu 

Publication date: 29 July 2022

Published in: Journal of Algebraic Combinatorics (Search for Journal in Brave)

Abstract: A set $SsubseteqV$ is extit{independent} in a graph $G=left(V,Eight)$ if no two vertices from $S$ are adjacent. The extit{independence number} $alpha(G)$ is the cardinality of a maximum independent set, while $mu(G)$ is the size of a maximum matching in $G$. If $alpha(G)+mu(G)$ equals the order of $G$, then $G$ is called a extit{K"{o}nig-Egerv'{a}ry graph }cite{dem,ster}. The number $dleft(Gight)=maxleftvertAightvert-leftvertNleft(Aight)ightvert:AsubseteqV$ is called the extit{critical difference} of $G$ cite{Zhang} (where $Nleft(Aight)=leftv:vinV,Nleft(vight)capAeqemptysetight$). It is known that $alpha(G)-mu(G)leqdleft(Gight)$ holds for every graph cite{Levman2011a,Lorentzen1966,Schrijver2003}. In cite{LevMan5} it was shown that $d(G)=alpha(G)-mu(G)$ is true for every K"{o}nig-Egerv'{a}ry graph. A graph $G$ is extit{(i)} extit{unicyclic} if it has a unique cycle, extit{(ii)} extit{almost bipartite} if it has only one odd cycle. It was conjectured in cite{LevMan2012a,LevMan2013a} and validated in cite{Bhattacharya2018} that $d(G)=alpha(G)-mu(G)$ holds for every unicyclic non-K"{o}nig-Egerv'{a}ry graph $G$. In this paper we prove that if $G$ is an almost bipartite graph of order $nleft(Gight)$, then $alpha(G)+mu(G)inleftnleft(Gight)-1,nleft(Gight)ight$. 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)=alpha(G)-mu(G)=leftvert mathrm{core}(G) ightvert -leftvert N(mathrm{core}(G)) ightvert , ] where by extrm{core}$left(Gight)$ we mean the intersection of all maximum independent sets.

Full work available at URL: https://arxiv.org/abs/1905.09462

Recommendations

• On critical difference, independence number and matching number of graphs
• A Note on n-Critical Bipartite Graphs and Its Application
• Critical sets in bipartite graphs
• scientific article; zbMATH DE number 1792564
• Minimum \(k\)-critical bipartite graphs
• On \(b\)-vertex and \(b\)-edge critical graphs
• On edge-\(b\)-critical graphs
• scientific article; zbMATH DE number 1187326
• On the deficiency of bipartite graphs
• scientific article; zbMATH DE number 5757

zbMATH Keywords

matchingbipartite graphcoreindependent setcritical set[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=K%EF%BF%BD%EF%BF%BDnig-Egerv%EF%BF%BD%EF%BF%BDry+graph&go=Go K��nig-Egerv��ry graph]critical difference

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Computing the bipartite edge frustration of fullerene graphs
• Vertex domination-critical graphs
• Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems
• The bipartite edge frustration of composite graphs
• Combinatorial properties of the family of maximum stable sets of a graph
• On \(\alpha^{+}\)-stable König-Egerváry graphs
• Critical independent sets and König-Egerváry graphs
• On the core of a unicyclic graph
• On the structure of \(\alpha\)-stable graphs
• A characterization of the graphs in which the transversal number equals the matching number
• König-Egerváry graphs, 2-bicritical graphs and fractional matchings
• Vertices belonging to all critical sets of a graph
• Node-weighted graphs having the König-Egerváry property
• On the number of vertices belonging to all maximum stable sets of a graph
• On \(\alpha\)-critical edges in König--Egerváry graphs
• Problems on matchings and independent sets of a graph
• On the structure of the minimum critical independent set of a graph

Cited In (3)

• On critical difference, independence number and matching number of graphs
• On graphs admitting two disjoint maximum independent sets
• On the intersection of all critical sets of a unicyclic graph

This page was built for publication: On the critical difference of almost bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2159389)