On the critical difference of almost bipartite graphs

DOI10.1007/S10801-020-00968-XMaRDI QIDQ2159389zbMATH OpenOpenAlexFDO

Authors Vadim E. Levit, Eugen Mandrescu

Publication date 29 July 2022

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

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

zbMATH Keywords

matchingbipartite graphcoreindependent setcritical setcritical differenceKönig-Egerváry graph

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)

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.

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

Cites work

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