Core and Corona in 2-Bicritical Odd-Bicyclic Graphs
January 01, 1970
Abstract
Let \(\textrm{core}(G)\) and \(\textrm{corona}(G)\) denote the intersection and the union, respectively, of all maximum independent sets of a graph \(G\). A graph is called \(2\)-bicritical if \(\left|N(S)\right|>\left|S\right|\) for every nonempty independent set \(S\). Pulleyblank 1979 showed that almost all graphs are \(2\)-bicritical.
In this paper, we study the structure of maximum independent sets in \(2\)-bicritical graphs with at most two odd cycles. Using ear–pendant decompositions, we obtain a complete structural classification of these graphs into four families: one-odd cycle, fused-odd, even-linked, and odd-linked graphs. For each family, we compute explicitly \(\alpha(G)\), \(\textrm{core}(G)\), and \(\textrm{corona}(G)\), and describe the corresponding matching structure.
We prove that \(\left|\textrm{core}(G)\right|+\left|\textrm{corona}(G)\right|\) equals either \(2\alpha(G),2\alpha(G)+1\) or \(2\alpha(G)+2\), and we give a complete, purely structural characterization of the graphs in each case in terms of the relative position of their odd cycles.
These results extend a theory originally developed for König–Egerváry graphs and later for almost bipartite graphs to a broader non-König–Egerváry setting.
Maximum Independent Set, Kőnig-Egerváry graph, Corona, Core, 2-bicritical, Characterization 05C70, 05C75
1 Introduction↩︎
Let \(\alpha(G)\) denote the cardinality of a maximum independent set, and let \(\mu(G)\) be the size of a maximum matching in \(G=(V,E)\). It is known that \(\alpha(G)+\mu(G)\) equals the order of \(G\), in which case \(G\) is a König–Egerváry graph [1]–[3]. Kőnig-Egerváry graphs have been extensively studied [4]–[8]. It is known that every bipartite graph is a König–Egerváry graph [9]. These graphs were independently introduced by Deming [1], Sterboul [3], and [2]. A graph \(G\) is almost bipartite if it has only one odd cycle. Let \(\Omega^{*}(G)=\left\{ S:S\textrm{ is an independent set of }G\right\}\), \(\Omega(G)=\{S:S\) is a maximum independent set of \(G\}\), \(\textrm{core}(G)=\bigcap\left\{ S:S\in\Omega(G)\right\}\) [10], and \(\textrm{corona}(G)=\bigcup\left\{ S:S\in\Omega(G)\right\}\) [11].
Theorem 1. If \(G\) is an König–Egerváry graph, then
Theorem 2 ([13]). If \(G\) is an almost bipartite non-König–Egerváry graph, then
\(\left|\textrm{corona}(G)\right|+\left|\textrm{core}(G)\right|=2\alpha(G)+1,\)
\(\textrm{corona}(G)\cup N(\textrm{core}(G))=V(G).\)
From a structural point of view, graphs with at most two odd cycles constitute the first nontrivial extension beyond the almost bipartite case. While bipartite graphs and graphs with a single odd cycle exhibit a rather rigid behavior with respect to maximum independent sets, the presence of two odd cycles allows for qualitatively different configurations, depending on their relative position inside the graph.
The first item of [levit] motivates [mainproblem].
Problem 3 ([[13]][]). Characterize graphs enjoying \(\left|\textrm{corona}(G)\right|+\left|\textrm{core}(G)\right|=2\alpha(G)+1,\)
In [14], a reductive-type characterization was obtained for graphs satisfying \(\left|\textrm{core}(G)\right|+\left|\textrm{corona}(G)\right|=2\alpha(G)+1\). In this paper, we compute \(\textrm{core}(G)\) and \(\textrm{corona}(G)\) explicitly for \(2\)-bicritical graphs with at most two odd cycles. As a consequence, we show that \(\left|\textrm{core}(G)\right|+\left|\textrm{corona}(G)\right|\) is equal to either \(2\alpha(G)\) or \(2\alpha(G)+1\), and we characterize the graphs in each case.
The paper is organized as follows. In 1 we present the general context of the problem and introduce the fundamental concepts. In 2 we fix the notation used throughout the paper. In 3 we classify \(2\)-bicritical graphs with at most two odd cycles into four distinct families: one-odd cycle, fused-odd, even-linked, and odd-linked graphs, according to the behavior of their maximum independent sets, and we derive structural information for each class. In 4 we study even-linked graphs, in 5 we study odd-linked graphs, and in 6 we study fused-odd and one-odd cycle graphs. Finally, in 7 we obtain general characterizations and propose some conjectures and open problems.
2 Preliminaries↩︎
All graphs considered in this paper are finite, undirected, and simple. For any undefined terminology or notation, we refer the reader to Lovász and Plummer [15] or Diestel [16].
Let \(G = (V, E)\) be a simple graph, where \(V = V(G)\) is the finite set of vertices and \(E = E(G)\) is the set of edges, with \(E \subseteq \{\{u, v\} : u, v \in V, u \neq v\}\). We denote the edge \(e=\{u, v\}\) as \(uv\). A subgraph of \(G\) is a graph \(H\) such that \(V(H) \subseteq V(G)\) and \(E(H) \subseteq E(G)\). A subgraph \(H\) of \(G\) is called a spanning subgraph if \(V(H) = V(G)\).
Let \(e \in E(G)\) and \(v \in V(G)\). We define \(G - e := (V, E - \{e\})\) and \(G - v := (V - \{v\}, \{uw \in E : u,w \neq v\})\). If \(X \subseteq V(G)\), the induced subgraph of \(G\) by \(X\) is the subgraph \(G[X]=(X,F)\), where \(F:=\{uv \!\in\! E(G) : u, v \!\in \! X\}\).
The number of vertices in a graph \(G\) is called the order of the graph and denoted by \(\left|G\right|\) or \(n(G)\). A cycle in \(G\) is called odd (resp. even) if it has an odd (resp. even) number of edges.
For a vertex \(v\in V(G)\), the neighborhood of \(v\) is \[N_G(v)=\{u\in V(G): uv\in E(G)\}.\] When no confusion arises, we write \(N(v)\) instead of \(N_G(v)\). For a set \(S\subseteq V(G)\), the neighborhood of \(S\) is \[N_G(S)=\bigcup_{v\in S} N_G(v).\]
A matching \(M\) in a graph \(G\) is a set of pairwise non-adjacent edges. The matching number of \(G\), denoted by \(\mu(G)\), is the maximum cardinality of any matching in \(G\). Matchings induce an involution on the vertex set of the graph: \(M:V(G)\rightarrow V(G)\), where \(M(v)=u\) if \(uv \in M\), and \(M(v)=v\) otherwise. If \(S, U \subseteq V(G)\) with \(S \cap U = \emptyset\), we say that \(M\) is a matching from \(S\) to \(U\) if \(M(S) \subseteq U\). A matching \(M\) is perfect if \(M(v)\neq v\) for every vertex of the graph. A matching is near-perfect if \(\left|{v \in V(G) : M(v) = v}\right| = 1\). A graph is a factor-critical graph if \(G-v\) has perfect matching for every vertex \(v\in V(G)\).
A vertex set \(S \subseteq V\) is independent if, for every pair of vertices \(u, v \in S\), we have \(uv \notin E\). The number of vertices in a maximum independent set is denoted by \(\alpha(G)\). A bipartite graph is a graph whose vertex set can be partitioned into two disjoint independent sets.
We will use the Gallai–Edmonds structure theorem throughout the paper, together with the associated notation.
Theorem 4 ([17], [18] Gallai–Edmonds structure theorem). Let \(G\) be a graph, and define \[\begin{align} D(G) & := \{ v : \textrm{there exists a maximum matching that misses } v \}, \\ A(G) & := \{ v : v \textrm{ is adjacent to some } u \in D(G), \textrm{ but } v \notin D(G) \}, \\ C(G) & := V(G) - (D(G) \cup A(G)). \end{align}\]
If \(G_{1}, \dots, G_{k}\) are the connected components of \(G[D(G)]\) and \(M\) is a maximum matching of \(G\), then:
\(M\) covers \(C(G)\) and matches \(A(G)\) into distinct components of \(G[D(G)]\).
Each \(G_i\) is a factor-critical graph, and the restriction of \(M\) to \(G_i\) is a near-perfect matching.
3 Structural classification of odd-bicyclic graphs↩︎
The aim of this section is to isolate all possible structural configurations of \(2\)-bicritical graphs with at most two odd cycles. This classification will be used systematically in the subsequent sections to compute \(\alpha(G)\), \(\textrm{core}(G)\), and \(\textrm{corona}(G)\) explicitly.
The notion of 2-bicritical graphs was introduced in [19], and they can be characterized as follows.
Theorem 5 ([[19]][]). A graph \(G\) is \(2\)-bicritical if and only if \(\left|N(S)\right|>\left|S\right|\) for every nonempty independent set \(S\subseteq V(G)\).
The class of \(2\)-bicritical graphs can be regarded as the structural counterpart of König–Egerváry graphs [20]. In recent works, several new properties of \(2\)-bicritical graphs have been established; see, for instance, [21]–[23]. It is important to note that Pulleyblank in 1979 showed that almost all graphs are 2-bicritical [19]. In [20], Larson showed that every graph can be decomposed into a 2-bicritical graph and a Kőnig–Egerváry graph.
We say that \(G^{\prime}\) is an odd homeomorph of \(G\) if \(G^{\prime}\) is obtained by replacing each edge of \(G\) with a path of odd length, such that these paths remain internally disjoint. Let \(B\) be a subgraph of \(G\). An ear in \(G\) with respect to \(B\) is an odd-length path in \(G\) whose endpoints lie in \(B\), but whose internal vertices lie outside \(B\), and in which all internal vertices are distinct. A pendant in \(G\) with respect to \(B\) consists of an odd-length simple cycle \(C\) in \(G\), vertex-disjoint from \(B\), together with a positive-length simple path with one end in \(C\) and the other in \(B\), with all other vertices lying outside both \(B\) and \(C\). The vertex in \(B\) is called the end of the pendant.
An ear-pendant decomposition of a graph \(G\) is a sequence \(G_{0},G_{1},\dots,G_{p}=G\) of graphs where \(G_{0}\) is either an odd cycle or an odd homeomorph of \(K_{4}\), and for each \(i\in\{1,\dots,p\}\), \(G_{i}\) is obtained from \(G_{i-1}\) by adding either an ear or a pendant. In [24] the following characterization of 2-bicritical graphs in terms of ear-pendant decompositions was given.
Theorem 6 ([24]). A connected graph is 2-bicritical if and only if it has an ear-pendant decomposition.
Let \(G\) be a connected \(2\)-bicritical graph with at most two odd cycles, and note that \(G\) contains at least one odd cycle. Then \(G\) can be classified into one of the following four classes. This classification reflects qualitatively different behaviors of the parameters \(\textrm{core}(G),\textrm{corona}(G),\alpha(G)\).
- If \(G\) has a unique odd cycle, we say that \(G\) is a one-odd cycle graph. In this case, by the ear-pendant decomposition, it is easy to see that \(G\) necessarily coincides with this odd cycle (see 1).
Suppose now that \(G\) contains exactly two odd cycles and consider an ear-pendant decomposition of \(G\): \[G_{0},\dots,G_{p}=G.\]
If \(G_{0}\) is an odd homeomorph of \(K_{4}\), then \(G\) has more than two odd cycles, a contradiction. Therefore, \(G_{0}\) is an odd cycle.
- If \(G_{1}\) is obtained from \(G_{0}\) by adding an odd ear, then \(p=1\). Indeed, in this case, adding either an odd ear or a pendant to \(G_{1}\) generates at least one new odd cycle (see 1). In this case, we say that \(G\) is a fused-odd graph.
Suppose now that \(G_{1}\) is obtained from \(G_{0}\) by adding a pendant. Let \(k\) denote the length of the path \(P\) that connects the two odd cycles in \(G_{1}\).
If \(k\) is odd, then we say that \(G\) is an odd-linked graph; see 2.
If \(k\) is even, then we say that \(G\) is an even-linked graph; see 2.
In the case of an odd(even)-linked graph, note that in the ear-pendant decomposition of \(G\) no further pendants are added after \(G_{1}\), since this would generate an additional odd cycle. Therefore, for \(i=2,\dots,p\), the graph \(G_{i}\) is obtained from \(G_{i-1}\) by adding an odd ear. Moreover, both end-points of each added odd ear are contained in the path \(P\); otherwise, it is easy to see that a new odd cycle is created (see 3).
The structure of one-odd cycle and fused-odd graphs is relatively simple. By contrast, odd-linked and even-linked graphs exhibit a strong analogy with classical bipartite matching-covered graphs.
These four families exhaust all \(2\)-bicritical graphs with at most two odd cycles and correspond to fundamentally different behaviors of maximum independent sets and matchings.
The study of bipartite matching covered graphs has a long history: Kőnig already used this concept in 1915 while analyzing determinant decompositions [25], and nearly half a century later Hetyei formalized the term elementary instead bipartite matching covered and developed a classical characterization [26]. It should be noted that several results concerning matching covered graphs, such as those in [15], are presented in the more general context of bipartite matching covered graphs.
In this paper, however, we will work with the following equivalent notion, which is more convenient for our purposes. A graph \(G\) is called a bipartite matching covered graph if \(G\) is connected, bipartite, and every edge of \(G\) belongs to a perfect matching.
Bipartite matching covered graphs admit a particularly elegant structural description in terms of ear decompositions, due to Lovász.
Theorem 7 ([[27]][]). Given any bipartite matching covered graph \(G\), there exist a odd length ear decomposition \[G_{1},G_{2},\dots,G_{r}=G\] of matching covered subgraphs of \(G\) where \(G_{1}=K_{2}\).
In the bipartite setting, odd ear decompositions starting from \(K_2\) characterize matching covered graphs.
More precisely, let \(G\) be an odd(even)-linked graph with an ear-pendant decomposition \[G_{0},\dots,G_{p}=G,\] where \(G_{0}\) is an odd cycle and \(G_{1}\) is obtained from \(G_{0}\) by adding a pendant. Let \(P\) be the path that connects the two cycles of \(G_{1}\). Let \(G^{\prime}\) be the graph obtained from \(G\) by deleting the vertices of the cycles of \(G_{1}\) that do not belong to \(V(P)\). Then the following result holds.
\(None\)
Proposition 8. If \(G\) is an odd(even)-linked graph, then there exists a bipartite matching-covered graph \(H\) such that \(G^{\prime}\) is obtained from \(H\) by deleting two (respectively, one) vertices.
Proof. The proof is essentially an application of Lovász’s ear-decomposition of bipartite matching-covered graphs. Suppose that \(G\) is an odd-linked graph; the even case is similar.
Note that \(G^{\prime}\) is bipartite and is obtained from \(P\) by adding a sequence of \(p-1\) odd ears.
\[P,P_{2},\dots,P_{p}=G^{\prime},\]
where \(P_{i}\) is obtained from \(P_{i-1}\) by adding an odd ear, for each \(i=2,\dots,p\). Note that this is achieved by choosing \(P_{i}=G_{i}-(V(G)-V(G^{\prime}))\).
Add a fictitious vertex \(x\notin V(G^{\prime})\), and let \(y\) and \(z\) be the end-points of \(P\). We define \(P_{0}^{\prime}:=(\{x,y\},\{xy\})\approx K_{2}\) and \(P^{\prime}=\left(P_{0}^{\prime}\cup P\right)+xz\). Then,
\[P^{\prime}_{0},P^{\prime},P^{\prime}\cup P_{2},\dots,P^{\prime}\cup P_{p}=P^{\prime}\cup G^{\prime},\]
is an odd-ear decomposition starting from \(K_{2}\). Hence, by [oi12j3j123ijj], the graph \[H:=P^{\prime}\cup G^{\prime}\] is a bipartite matching-covered graph, and it satisfies \(H-x=G^{\prime}\); see 4 for a simple illustration of this proof.
The even case is proved using a similar argument, but adding two fictitious vertices instead of one. ◻
![Figure 4: An illustration of the proof of [oi12j3j123ijj]](/article/2603.11419/_pdflatex/oujhzrlp.png "fig:")
In the following sections, we use this classification to explicitly compute \(\textrm{core}(G)\), \(\textrm{corona}(G)\), and \(\alpha(G)\) for each family, and to study the structural relationships among them.
4 Bicyclic even-linked graphs↩︎
In this section, we determine explicitly \(\alpha(G)\), \(\textrm{core}(G)\), and \(\textrm{corona}(G)\) for \(2\)-bicritical even-linked graphs. We begin by establishing some auxiliary results needed for the main proofs.
Theorem 9 ([28]). An independent set \(S\) is maximum if and only if every independent set disjoint from \(S\) can be matched into \(S\).
Theorem 10. Let \(G\) be a graph and let \(S\) be an independent set. For a vertex \(v\in S\), we have that \(v\in \textrm{core}(G)\) and \(S\) is a maximum independent set if and only if every independent set \(T\) disjoint from \(S\) can be matched into \(S\setminus\{v\}\).
Proof. \((\Rightarrow)\) Suppose that \(v\in \textrm{core}(G)\) and that \(S\) is a maximum independent set of \(G\). Since \(v\in \textrm{core}(G)\), we have \[\alpha(G-v)=\alpha(G)-1.\] In particular, \(S\setminus\{v\}\) is a maximum independent set of \(G-v\).
Now let \(T\) be an independent set disjoint from \(S\). Then \(T\) is also an independent set of \(G-v\) and is disjoint from \(S\setminus\{v\}\). By [19], applied to the graph \(G-v\), it follows that \(T\) can be matched into \(S\setminus\{v\}\).
\((\Leftarrow)\) Suppose now that every independent set \(T\) disjoint from \(S\) can be matched into \(S\setminus\{v\}\). Then, by [19] applied to the graph \(G-v\), it follows that \(S\setminus\{v\}\) is a maximum independent set of \(G-v\). Consequently, \[\alpha(G-v)=|S|-1,\] and therefore \(S\) is a maximum independent set of \(G\).
Moreover, since the deletion of \(v\) reduces the independence number by one, it follows that \(v\) belongs to every maximum independent set of \(G\), that is, \(v\in \textrm{core}(G)\). ◻
Theorem 11 ([[26]][]). Let \(G\) be a bipartite graph with bipartition \((A,B)\). Then the following statements are equivalent:
\(G\) is elementary (that is, the union of perfect matchings in it induces a connected subgraph).
\(G\) has exactly two minimum vertex covers, namely \(A\) and \(B\).
\(\lvert A\rvert = \lvert B\rvert\) and \(\lvert S\rvert + 1 \le \lvert N(S)\rvert\) for every non-empty proper subset \(S \subset A\).
Either \(G = K_{2}\), or \(\lvert V(G)\rvert \ge 4\) and for every \(v \in A\) and \(w \in B\), the graph \(G - v - w\) has a perfect matching.
\(G\) is matching covered graph (that is \(G\) is connected and every edge of \(G\) is contained in some perfect matching).
Theorem 12. Let \(G\) be an even-linked graph of order \(n\), let \(C\) and \(C^{\prime}\) be the unique odd cycles of \(G\), and let \(X\) be the set of vertices in \(V(C)\cup V(C^{\prime})\) having degree \(2\) in \(G\). Then \(G-X\) is a graph with bipartition \((A,B)\) such that \(|A|=|B|+1\). Moreover,
\(\textrm{core}(G)=B\),
\(\alpha(G)=\frac{n-1}{2}\),
\(\left|\textrm{core}(G)\right|=\frac{n-\left|V(C)\cup V(C^{\prime})\right|+1}{2}\).
Proof. Let \(G_{0},G_{1},\dots,G_{p}=G\) be an ear-pendant decomposition of \(G\). Then \(G_{0}\) is an odd cycle and \(G_{1}\) is obtained from \(G_{0}\) by adding a pendant. Moreover, for every \(i=2,\dots,p\), the graph \(G_{i}\) is obtained from \(G_{i-1}\) by adding an odd ear. Observe that none of these ears uses vertices from \(X\). Consequently, the graph \[G^{\prime}:=G-X\] is bipartite and connected; let \((A,B)\) be a bipartition of \(G^{\prime}\).
Arguing as in the proof of 8, the graph \(G^{\prime}\) admits the following decomposition: \[P=P_{1},P_{2},\dots,P_{p}=G^{\prime},\] where each \(P_{i}\) is obtained from \(P_{i-1}\) by adding an odd ear, and \(P\) is the path that connects both cycles in \(G_{1}\). Since \(P\) has even length, adding each odd ear introduces an even number of new vertices. Therefore, \(G-X\) has odd order and, without loss of generality, we may assume that \[|A|=|B|+1.\]
Let \(x\) and \(y\) be the end-points of \(P\); note that \(x,y\in A\). Let \(S^{\prime}\) be a maximum independent set of \(C\cup C^{\prime}\) that contains neither \(x\) nor \(y\). We define \[S:=S^{\prime}\cup B.\]
We show that \(S\) is a maximum independent set of \(G\) using 10. Indeed, fixing \(v\in B\) and given any independent set \(T\) disjoint from \(S\), we prove that \(T\) can be matched into \(S\setminus\{v\}\). In this way, it follows that \(S\) is a maximum independent set of \(G\) and that \(B\subseteq \textrm{core}(G).\)
Claim 13. The set \(T\) can be matched into \(S\setminus\{v\}\).
Proof. For an illustration of the proof, see 5. Let \(H\) be the graph obtained from \(G\) by adding a new vertex \(w\) such that \[N_{H}(w)=\{x,y\}.\] Arguing as in the proof of 8, it follows that \(H-X\) is a bipartite matching-covered graph. In particular, by [hetyei], the graph \((H-X)-v-x\) has a perfect matching \(M\).
Observe that necessarily \(M(w)=y\), since \(w\) has a unique neighbor in \((H-X)-v-x\). We define \[M^{\prime}:=M-\{xy\}.\] Then \(M^{\prime}\) is a matching of \(G-X\) that leaves exactly the vertices \(x,y\), and \(v\) unsaturated.
On the other hand, the set \(S\cap V(C)\) is a maximum independent set of \(C\). By [19], the set \(T\cap V(C)\) can be matched into \(S\cap V(C)\) by means of a matching \(M_{1}\). Similarly, \(T\cap V(C^{\prime})\) can be matched into \(S\cap V(C^{\prime})\) by means of a matching \(M_{2}\). In particular, \[M_{1}\subseteq E(C) \quad\text{and}\quad M_{2}\subseteq E(C^{\prime}).\]
Finally, the vertices of \(T\setminus\bigl(V(C)\cup V(C^{\prime})\bigr)\) can be matched into \(S\setminus\{v\}\) using the matching \(M^{\prime}\). Therefore, \[M_{1}\cup M_{2}\cup M^{\prime}\] is a matching that saturates all vertices of \(T\) in \(S\setminus\{v\}\), which completes the proof. ◻
Note that \(S^{\prime}\) on each cycle \(C\) and \(C^{\prime}\) can be chosen in two distinct disjoint ways, which proves that \(\textrm{core}(G)=B\). On the other hand, note that
\[\begin{align} 2\alpha(G) & = & 2\left|S\right|\\ & = & 2\left|S^{\prime}\right|+2\left|B\right|\\ & = & \left(\left|C\right|+\left|C^{\prime}\right|-2\right)+\left(\left|A\right|+\left|B\right|-1\right)\\ & = & \left(\left|C\right|+\left|C^{\prime}\right|+\left|A\right|+\left|B\right|-2\right)-1\\ & = & n-1, \end{align}\]
that is, \(\alpha(G)=\frac{n-1}{2}\).
Finally, note that
\[\begin{align} 2\left|\textrm{core}(G)\right|+1 & = & 2\left|B\right|+1\\ & = & \left|B\right|+\left|A\right|\\ & = & n-\left|V(C)\cup V(C^{\prime})\right|+2. \end{align}\]
which implies that \(\left|\textrm{core}(G)\right|=\frac{n-\left|V(C)\cup V(C^{\prime})\right|+1}{2}\). ◻
Theorem 14. With the notation and hypotheses of 12, we have \[\textrm{corona}(G)=\left(V(C)\cup V(C^{\prime})\cup B\right)-\{x,y\}=V(G)-A\] and, in particular, \[\left|\textrm{corona}(G)\right|=\frac{n+\left|V(C)\cup V(C^{\prime})\right|-3}{2}.\]
Proof. Note that \(N(\textrm{core}(G))=N(B)=A\), since \(G-X\) is a connected bipartite graph. That is, \(\textrm{corona}(G)\subset V(G)-A\). On the other hand, as in the proof of 12, the set \(S^{\prime}\) on each cycle \(C\) and \(C^{\prime}\) can be chosen in two distinct disjoint ways, but neither \(x\) nor \(y\) belongs to \(\textrm{corona}(G)\). Therefore, \(\left(V(C)\cup V(C^{\prime})\right)-\{x,y\}\subset\textrm{corona}(G)\). Hence, \[\textrm{corona}(G)=\left(V(C)\cup V(C^{\prime})\cup B\right)-\{x,y\}=V(G)-A.\]
On the other hand, note that \[\begin{align} 2\left|\textrm{corona}(G)\right| & = & 2\left|\left(V(C)\cup V(C^{\prime})\cup B\right)-\{x,y\}\right|\\ & = & 2\left|V(C)\cup V(C^{\prime})\right|+2\left|B\right|-4\\ & = & 2\left|V(C)\cup V(C^{\prime})\right|+\left|A\right|+\left|B\right|-5\\ & = & \left(\left|A\right|+\left|B\right|+\left|V(C)\cup V(C^{\prime})\right|-2\right) +\left|V(C)\cup V(C^{\prime})\right|-3\\ & = & n+\left|V(C)\cup V(C^{\prime})\right|-3. \end{align}\]
As desired. ◻
Theorem 15. Let \(G\) be a bicyclic even-linked graph and let \(A\) be the set defined in 12. Then the following properties hold:
\(\left|\textrm{corona}(G)\right|+\left|\textrm{core}(G)\right|=2\alpha(G)\),
\(N(\textrm{core}(G))=A,\)
\(\textrm{corona}(G)\) and \(N(\textrm{core}(G))\) form a partition of \(V(G)\).
Proof. By 12 and 14, we have \[\begin{align} \left|\textrm{corona}(G)\right|+\left|\textrm{core}(G)\right| & = & \frac{n+\left|V(C)\cup V(C^{\prime})\right|-3}{2} +\frac{n-\left|V(C)\cup V(C^{\prime})\right|+1}{2}\\ & = & \frac{2(n-1)}{2}\\ & = & 2\alpha(G). \end{align}\]
In the proof of 14 it is observed that \(N(\textrm{core}(G))=N(B)=A\), and by 14 we have \(\textrm{corona}(G)=V(G)-A\). ◻
Theorem 16. Let \(G\) be an odd-linked graph. Then \[A(G)=\textrm{core}(G),\quad D(G)=V(G)-\textrm{core}(G) \quad\text{and}\quad \mu(G)=\frac{n-1}{2}.\]
Proof. With the notation of the proof of 12, let \(z\in A\). Then, since \(H-X\) is a matching-covered graph, by [hetyei] the graph \(H-X-w-z\) has a perfect matching \(M_{z}\). Let \(M_{X}\) be a perfect matching of \(G[X]\). Then \(M_{z}\cup M_{X}\) is a maximum matching of \(G\) that leaves only \(z\) unsaturated. In particular, \(A\subseteq D(G)\). Moreover, it follows that \[\mu(G)=\frac{n-1}{2}.\]
Analogously, the matching \(M_{x}\cup M_{X}\) leaves only \(x\) unsaturated, and it is easy to modify the matching in \(C\) in such a way that \(V(C)\subseteq D(G)\); see 6.
Analogously, by considering the matching \(M_{y}\cup M_{X}\), it follows that \(V(C^{\prime})\subseteq D(G)\). On the other hand, if a vertex \(b\in B\) belongs to \(D(G)\), then, since \(A\subseteq D(G)\), such a vertex \(b\) is contained in a non-trivial component of \(G[D(G)]\). But by [ge], this component is a factor-critical graph, which cannot be bipartite, leading to the conclusion that \(b\) lies on an odd cycle, a contradiction. Therefore, \[D(G)=V(G)-B=V(G)-\textrm{core}(G) \quad\text{and}\quad A(G)=\textrm{core}(G).\] As desired. ◻
Corollary 1. Let \(G\) be an even-linked graph of order \(n\). Then \(\alpha(G)+\mu(G)=n-1\).
5 Bicyclic odd-linked graphs↩︎
In this section, we study \(2\)-bicritical odd-linked graphs. In contrast with the even-linked case, the behavior of \(\textrm{core}(G)\) and \(\textrm{corona}(G)\) is particularly simple: we show that \(\textrm{core}(G)=\emptyset\) and \(\textrm{corona}(G)=V(G)\), and we determine the corresponding matching structure.
Theorem 17. Let \(G\) be a bicyclic odd-linked graph of order \(n\). Then the following items hold.
\(G\) has a perfect matching,
\(\alpha(G)=\frac{n-2}{2}\),
\(\textrm{core}(G)=\emptyset\),
\(\textrm{corona}(G)=V(G).\)
Proof. For an illustration of the proof, see 7. Let \(C\) and \(C^{\prime}\) be the unique odd cycles of \(G\), and let \(X\) be the set of vertices in \(V(C)\cup V(C^{\prime})\) having degree \(2\) in \(G\). Let \(G_{0},G_{1},\dots,G_{p}=G\) be an ear-pendant decomposition of \(G\). Then \(G_{0}\) is an odd cycle and \(G_{1}\) is obtained from \(G_{0}\) by adding a pendant. Moreover, for every \(i=2,\dots,p\), the graph \(G_{i}\) is obtained from \(G_{i-1}\) by adding an odd ear. Each of these ears does not use vertices from \(X\). Thus \(G^{\prime}:=G-X\) is a connected bipartite graph, say with bipartition \((A,B)\). Then, as in the proof of 8, \(G^{\prime}\) admits the following decomposition: \[P,P_{2},\dots,P_{p}=G^{\prime}\] where each graph is obtained from the previous one by adding an odd ear, and \(P\) is the path that connects both cycles in \(G_{1}\). Since \(P\) has odd length, after adding each odd ear we introduce an even number of new vertices; therefore \(G-X\) has even order and \(|A|=|B|\). A perfect matching in \(P\) extends easily to a perfect matching in \(P_{2}\), and proceeding in this way we obtain a perfect matching of \(G^{\prime}\), which extends—by choosing a near-perfect matching in each cycle \(C\) and \(C^{\prime}\)—to a perfect matching of \(G\).
But \(G\) is a non-empty \(2\)-bicritical graph, and hence it is not a Kőnig–Egerváry graph, that is, \[\alpha(G)+\mu(G)=\alpha(G)+\frac{n}{2}<n,\] and therefore \(\alpha(G)\le\frac{n}{2}-1=\frac{n-2}{2}\).
Let \(x\) and \(y\) be the end-points of \(P\), and write \(C=c_{1},\dots,c_{k}\) and \(C^{\prime}=c_{1}^{\prime},\dots,c_{t}^{\prime}\), where \(c_{1}=c_{k}=x\in A\) and \(c_{1}^{\prime}=c_{t}^{\prime}=y\in B\). Then the set
\[\begin{align} S_{1} & =B\cup\{c_{i}:i\text{ is even}\}\cup\{c_{i}^{\prime}:i\text{ is even and }i\neq2\}, \end{align}\]
is an independent set of \(G\) such that \[\begin{align} \left|S_{1}\right| & = & \left|B\right|+\frac{\left|V(C)\right|-1}{2}+\frac{\left|V(C^{\prime})\right|-3}{2}\\ & = & \left|B\right|+\frac{\left|V(C)\cup V(C^{\prime})\right|-2}{2}-1\\ & = & \frac{n-2}{2}. \end{align}\]
Thus \(S_{1}\) is a maximum independent set and \(\alpha(G)=\frac{n-2}{2}\). Similarly, we may consider the following maximum independent sets:
\[\begin{align} S_{2} & =B\cup\{c_{i}:i\text{ is odd and }i\neq1\}\cup\{c_{i}^{\prime}:i\text{ is odd and }i\neq1,t\},\\ S_{3} & =A\cup\{c_{i}^{\prime}:i\text{ is even}\}\cup\{c_{i}:i\text{ is even and }i\neq2\},\\ S_{4} & =A\cup\{c_{i}^{\prime}:i\text{ is odd and }i\neq1\}\cup\{c_{i}:i\text{ is odd and }i\neq1,k\}, \end{align}\]
It is easy to see that the union/intersection of the sets \(S_{1},\dots,S_{4}\) yields \(V(G)\) and \(\emptyset\), respectively. In other words, \(\textrm{core}(G)=\emptyset\) and \(\textrm{corona}(G)=V(G).\) ◻
Corollary 2. If \(G\) is a bicyclic odd-linked graph of order \(n\), then \(\alpha(G)+\mu(G)=n-1\).
Corollary 3. If \(G\) is a bicyclic odd-linked graph, then \(\left|\textrm{core}(G)\right|+\left|\textrm{corona}(G)\right|=2\alpha(G)\) and \(\textrm{corona}(G)\) and \(N(\textrm{core}(G))\) form a partition of \(V(G)\).
6 Fused-odd graphs↩︎
For completeness in this section, we analyze fused-odd graphs; due to the structure of these graphs, the analysis is much simpler than in the previous cases. For the rest, recall the following classical result on factor-critical graphs.
Theorem 18 ([[29]][]). A graph \(G\) is factor-critical if and only if \(G\) has an odd-length ear decomposition starting from an odd cycle.
Lemma 1. A factor-critical graph of order at least two is not a Kőnig–Egerváry graph.
Proof. Let \(G\) be a factor-critical graph of order \(n\). Suppose that \(G\) is a Kőnig–Egerváry graph; then \(\mu(G)=\frac{n-1}{2}\), and hence \(\alpha(G)=n-\frac{n-1}{2}=\frac{n+1}{2}\). Let \(S\) be a maximum independent set of \(G\) and let \(v\notin S\). Then \(G-v\) has order \(n-1\) and an independent set with \(\frac{n+1}{2}\) vertices; therefore, \(G-v\) does not have a perfect matching, a contradiction. ◻
Theorem 19. Let \(G\) be a fused-odd graph of order \(n\). Then
\(\mu(G)=\alpha(G)=\frac{n-1}{2}\),
\(\textrm{core}(G)=\emptyset\),
\(\textrm{corona}(G)=V(G)\) if and only if the odd cycles share at least two vertices.
Proof. By [lovasz], \(G\) is a factor-critical graph, and hence \(\mu(G)=\frac{n-1}{2}\). But by 1, \(G\) is not a Kőnig–Egerváry graph; therefore, \(\alpha(G)+\mu(G)=\alpha(G)+\frac{n-1}{2}\le n-1\), and thus \(\alpha(G)\le\frac{n-1}{2}\). Since \(G\) is a fused-odd graph, there is a vertex \(x\) such that the graph \(G-x\) is a bipartite graph with perfect matching. Then note that \(\alpha(G-x)+\mu(G-x)=n-1\), \(\mu(G-x)=\mu(G)\) and \(\alpha(G)+\mu(G)<n\). But since \(\alpha(G-x)\le\alpha(G)\) we have that \(\alpha(G-x)=\alpha(G)\). Therefore \(\Omega(G-x)\subset\Omega(G)\), and hence \(\textrm{core}(G)=\emptyset\).
Trivially \(x\) is unique if and only if the odd cycles share exactly one vertex (see [asopdkakso123123]). Otherwise the previous argument shows that \(\textrm{corona}(G)=V(G)\). If \(x\) is unique it is easy to see that \(\textrm{corona}(G)=V(G)-\{x\}\). ◻
Corollary 4. Let \(G\) be a fused-odd graph of order \(n\). Then
\(\left|\textrm{corona}(G)\right|+\left|\textrm{core}(G)\right|=2\alpha(G)+1\),
\(\alpha(G)+\mu(G)=n-1\).
7 Conclusions↩︎
In this final section, we summarize the main consequences of the previous results and collect general statements for \(2\)-bicritical graphs with at most two odd cycles. We also propose some conjectures and open problems motivated by this work.
We now collect the main consequences obtained in the previous sections into a unified statement. Note that 19 and 4 also hold when \(G\) is a one-odd cycle graph. By definition, one-odd cycle, fused-odd, even-linked, and odd-linked graphs are connected graphs. If \(G\) is a disconnected \(2\)-bicritical graph with at most two odd cycles, then by [puyelarpendietnedesc], \(G\) is formed by two components, each of which is an odd cycle. Hence, the disconnected case is trivial, as well as the one-odd cycle case. Therefore, by 2, 3, 1, and 15, we obtain the following.
Theorem 20. Let \(G\) be a \(2\)-bicritical graph with two odd cycles, then:
If \(G\) is connected and the two odd cycles share at most one vertex, then \(\left|\textrm{core}(G)\right|+\left|\textrm{corona}(G)\right|=2\alpha(G)\),
If both odd cycles share at least two vertices, then \(\left|\textrm{core}(G)\right|+\left|\textrm{corona}(G)\right|=2\alpha(G)+1\),
If \(G\) is disconnected, then \(\left|\textrm{core}(G)\right|+\left|\textrm{corona}(G)\right|=2\alpha(G)+2\).
Theorem 21. Let \(G\) be a \(2\)-bicritical graph with at most two odd cycles. Then \(\textrm{corona}(G)\mathbin{\dot{\cup}}N(\textrm{core}(G))=V(G)\) if and only if there do not exist two odd cycles that share at least two vertices.
Theorem 22. Let \(G\) be a \(2\)-bicritical graph with at most two odd cycles. If \(G\) is connected, then \[\alpha(G)+\mu(G)=n-1.\] If \(G\) is disconnected, then \[\alpha(G)+\mu(G)=n-2.\]
Conjecture 23. If \(G\) is a \(2\)-bicritical graph with two odd cycles, then \(\textrm{core}(G)\) and \(\textrm{corona}(G)\) can be computed in polynomial time.
Problem 24. If \(G\) is a graph with \(k\) odd cycles, explicitly determine \(\textrm{core}(G)\) and \(\textrm{corona}(G)\) for \(k\ge1\).
Problem 25. If \(G\) is a \(2\)-bicritical graph with \(k\) odd cycles, explicitly determine \(\textrm{core}(G)\) and \(\textrm{corona}(G)\) for \(k\ge3\).
Acknowledgments↩︎
This work was partially supported by Universidad Nacional de San Luis, grants PROICO 03-0723 and PROIPRO 03-2923, MATH AmSud, grant 22-MATH-02, Consejo Nacional de Investigaciones Científicas y Técnicas grant PIP 11220220100068CO and Agencia I+D+I grants PICT 2020-00549 and PICT 2020-04064.
Declaration of generative AI and AI-assisted technologies in the writing process↩︎
During the preparation of this work the authors used ChatGPT-3.5 in order to improve the grammar of several paragraphs of the text. After using this service, the authors reviewed and edited the content as needed and take full responsibility for the content of the publication.
Data availability↩︎
Data sharing not applicable to this article as no datasets were generated or analyzed during the current study.
Declarations↩︎
Conflict of interest The authors declare that they have no conflict of interest.