
arXiv: 2603.10315
A graph is almost bipartite if it contains exactly one odd cycle, and it is Konig-Egervary if the sum of the independence number and the matching number equals the order of the graph. We introduce the class of Bipartite-Almost Bipartite graphs (BAB-graphs), defined through a controlled union of a bipartite graph and several almost bipartite non-Konig-Egervary graphs. This family unifies and generalizes the previously studied classes of almost bipartite non-Konig-Egervary and R-disjoint graphs. While an almost bipartite non-Konig-Egervary graph contains a single odd cycle, an R-disjoint graph has exactly k pairwise disjoint odd cycles. A BAB-graph may contain many odd cycles that are not necessarily disjoint. We describe the structure of BAB-graphs by means of the Gallai-Edmonds decomposition and obtain explicit expressions for nucleus(G), diadem(G), and ker(G), which allow us to extend several known results for the previous classes. Moreover, we show that the determinant of the adjacency matrix of a BAB-graph can be factorized in terms of the determinants of the adjacency matrices of its component graphs. As a consequence, we confirm the conjecture stating the validity of this factorization for R-disjoint graphs. Finally, we derive combinatorial consequences of these results and establish new bounds for |corona(G)| + |ker(G)|.
Combinatorics, FOS: Mathematics, Combinatorics (math.CO)
Combinatorics, FOS: Mathematics, Combinatorics (math.CO)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
