We say that a graph \(G\) has a path-system with respect to a set \(W\) of even number of vertices in \(G\) if \(G\) has vertex-disjoint paths \(P_1,P_2, \ldots, P_m\) such that (i) each path \(P_i\) connects two vertices of \(W\) and (ii) the set of end-vertices of the paths \(P_i\) is exactly \(W\). In particular, \(m=|W|/2\). Moreover, if \(G\) has a path-system with respect to every set \(W\) of even number of vertices in \(G\), we say that \(G\) has a path system. We prove the following theorems: (i) if \(G\) is an \(r\)-edge-connected \(r\)-regular graph, then for any \(r-1\) edges \(e_1,\ldots, e_{r-1}\), \(G-\{e_1,\ldots, e_{r-1}\}\) has a path-system, (ii) every \(k\)-connected \(K_{1,k+1}\)-free graph has a path-system, and (iii) if a connected bipartite graph \(G\) with bipartition \((A,B)\) satisfies \(|A| \le 2|B|\), \(|N_G(X)| \ge 2|X|\) or \(N_G(X)=B\) for all \(X\subseteq A\), and \(|N_G(Y)| \ge |Y|\) or \(N_G(Y)=A\) for all \(Y\subseteq B\), then \(G\) has a path-system with respect to every set \(W\) of even number of vertices of \(A\).
We consider simple graphs, which have neither loops nor multiple edges. Let \(G\) be a graph with vertex set \(V(G)\) and edge set \(E(G)\). For a vertex \(v\) of a subgraph \(H\) of \(G\), we denote by \(\deg_H(v)\) the degree of \(v\) in \(H\), and by \(N_H(v)\) the neighborhood of \(v\) in \(H\). Thus \(\deg_H(v)=|N_H(v)|\).
Let \(W\) be a set of even number of vertices of a graph \(G\). Then we say that \(G\) has a path-system with respect to \(W\) if there are vertex-disjoint paths \(P_1,P_2, \ldots, P_ m\) in \(G\) such that (i) each path \(P_i\) connects two vertices of \(W\) and (ii) the set of the end-vertices of \(P_i\)’s is equal to \(W\); in particular, no internal vertex of each \(P_i\) is contained in \(W\), and \(m=|W|/2\). Moreover, we say that \(G\) has a path-system if for every set \(W\) of even number of vertices of \(G\), \(G\) has a path-system with respect to \(W\). It is obvious that if a graph \(G\) of even order has a path-system, then \(G\) has a 1-factor by considering a path-system with respect to \(V(G)\).
A criterion for a graph to have a path-system is given in the following theorem. Note that \(\omega(G)\) denotes the number of components of \(G\).
Theorem 1.1 (Lu and Kano [5]).A connected graph \(G\) has a path-system if and only if \[\omega(G-S) \le |S|+1 \quad \mbox{for all} \quad S\subset V(G).\]
We begin with some known results on path-systems. The following theorem is related to the theorem which says that an \((r-1)\)-edge connected \(r\)-regular graph of even order has a 1-factor containing any given edge \(e\) (Bäbler [8], Theorem 2.37 of [1]).
Theorem 1.2 (Kaiser [3]).Let \(r \geq 3\) be an integer. Then every \(r\)-edge-connected \(r\)-regular graph has a path-system. Moreover, for any given edge \(e\) and for every set \(W\) of even number of vertices, \(G\) has a path-system with respect to \(W\) one of whose paths passes through \(e\).
The star \(K_{1,m}\) of order \(m+1\) is the complete bipartite graph with partite sets of size 1 and \(m\). The star \(K_{1,3}\) is often called a claw. A graph that has no induced subgraph isomorphic to \(K_{1,m}\) is called a \(K_{1,m}\)-free graph. The following theorem is a generalization of the theorem which says that every connected claw-free graph of even order has a 1-factor (Sumner [7], Theorem 2.43 of [1]).
Theorem 1.3 (Furuya and Kano [2])Every connected claw-free graph has a path-system.
In this paper, we prove the following three theorems.
The first theorem is related to Theorem 1.2 and to the theorem which says that for an \((r-1)\)-edge connected \(r\)-regular graph \(G\) of even order and for its any \(r-1\) edges \(e_1, \ldots, e_{r-1}\), \(G-\{e_1, \ldots, e_{r-1}\}\) has a 1-factor (Plesník [6], Theorem 2.39 of [1]).
Theorem 1.4. Let \(r\ge 2\) be an integer, and \(G\) be an \(r\)-edge-connected \(r\)-regular graph. Then for any \(r-1\) edges \(e_1, e_2, \ldots, e_{r-1}\) of \(G\), \(G-\{e_1,e_2, \ldots, e_{r-1}\}\) has a path-system.
The \(r\)-edge-connectedness in Theorem 1.4 is necessary. Namely, we can show that there are infinitely many \((r-1)\)-edge connected \(r\)-regular graphs that have no path-system. Let \(r\ge 3\) be an odd integer, and \(H\) be an \(r\)-edge connected \(r\)-regular graph, which has a 1-factor, and let \(H^*\) be the graph obtained from \(H\) by removing \((r-1)/2\) independent edges. Then \(H^*\) has \(r-1\) vertices of degree \(r-1\), and all the other vertices have degree \(r\). Let \(D_0, D_1, \ldots, D_{2r-1}\) be \(2r\) copies of \(H^*\), and let \(v_0, v_1, \ldots, v_{2r-3}\) be \(2r-2\) new vertices. We construct an \((r-1)\)-edge connected \(r\)-regular graph \(G\) as follows. For every \(D_j, 0\le j\le 2r-3\), letting \(x_0,x_1, \ldots, x_{r-2}\) be the \(r-1\) vertices of \(D_j\) with degree \(r-1\), and join \(x_{i}\) to \(v_{j+i}\) for every \(0\le i \le r-2\), where \(v_s=v_t\) if \(s\equiv t \pmod{2r-2}\). Additionally, join each of \(2r-2\) vertices of \(D_{2r-2} \cup D_{2r-1}\) with degree \(r-1\) to one of \(\{v_0, v_1, \ldots ,v_{2r-3}\}\). Then the resulting graph \(G\) is an \((r-1)\)-edge connected \(r\)-regular graph. Since \(\omega (G-\{v_0, v_1, \ldots, v_{2r-3}\} )=2r\), \(G\) has no path-system by Theorem 1.1. If \(r\) is even, then every \((r-1)\)-edge connected \(r\)-regular graph is \(r\)-edge connected. So, in the case where \(r\) is even, we can similarly show that there are infinitely many \((r-2)\)-edge connected \(r\)-regular graphs \(G\) which have no path-system. Consequently, the edge-connectivity in Theorem 1.4 is sharp.
The following theorem is a generalization of the theorem which says that every \(k\)-connected \(K_{1,k+1}\)-free graph of even order has a 1-factor (Sumner [7]).
Theorem 1.5. For an integer \(k\ge 2\), every \(k\)-connected \(K_{1,k+1}\)-free graph has a path-system.
The following theorem gives a sufficient condition for a bipartite graph to have a path-system with respect to any subset of one partite set.
Theorem 1.6. Let \(G\) be a connected bipartite graph with bipartition \((A,B)\). Suppose that \(|A| \le 2|B|\), \[\ |N_G(X)| \ge 2 |X| \quad \mbox{or} \quad N_G(X)=B \quad \mbox{for all} \quad X\subseteq A, ~~ \mbox{and} \label{eq-1} \ \tag{1}\] \[ |N_G(Y)| \ge |Y| \hspace{1.6em} \mbox{or} \quad N_G(Y)=A \quad \mbox{for all} \quad Y\subseteq B. \label{eq-2} \tag{2}\]
Then for every set \(W\) of even number of vertices of \(A\), \(G\) has a path-system with respect to \(W\).
Let \(G\) be a graph and \(H\) be a subgraph of \(G\). Then for two disjoint vertex sets \(X\) and \(Y\) of \(G\), the set of edges of \(H\) joining \(X\) to \(Y\) and the number of edges of \(H\) joining \(X\) to \(Y\) are denoted by \(E_H(X,Y)\) and \(e_H(X,Y)\), respectively. Thus \(e_H(X,Y)=|E_H(X,Y)|\). We first prove Theorem 1.4 by making use of Theorem 1.1.
Proof of Theorem 1.4. Let \(G\) be an \(r\)-edge-connected \(r\)-regular graph. If \(r=2\), then \(G\) is a cycle, and \(G-e_1\) is a Hamilton path in the cycle, and so the theorem holds. Thus we may assume that \(r\ge 3\). Suppose to the contrary that for some \(r-1\) edges \(e_1, e_2, \ldots, e_{r-1}\) of \(G\), \(G-\{e_1, e_2, \ldots, e_{r-1}\}\) has no path-system. By Theorem 1, \(H=G-\{e_1, e_2, \ldots, e_{r-1}\}\) has a vertex set \(S\) such that \(\omega(H-S) \ge |S|+2\).
Let \(D_1, D_2, \ldots, D_m\) be the components of \(H-S\), where \(m=\omega(H-S) \ge |S|+2\). Let \(\mathcal{E} =\{e_1, e_2, \ldots, e_{r-1}\}\). Then \(H=G-\mathcal{E}\). We need the following notation. For two disjoint vertex sets \(X\) and \(Y\) of \(G\), the number of edges in \(\mathcal{E}\) joining \(X\) to \(Y\) is denoted by \(e_{\mathcal{E}}(X,Y)\). Furthermore, \(e_G(V(D_i), V(D_j))\), \(e_{\mathcal{E}}(V(D_i), V(D_j))\) and \(e_{\mathcal{E}}(V(D_i),S)\) are briefly written by \(e_G(D_i,D_j)\), \(e_{\mathcal{E}}(D_i,D_j)\) and \(e_{\mathcal{E}}(D_i,S)\), respectively.
Since \(G\) is \(r\)-edge-connected, for each \(j\), \(1\le j \le m\), we have \[\begin{aligned} & r \le e_G(D_j,S ) + \sum_{i\ne j} e_{\mathcal{E}}(D_j,D_i) , \end{aligned}\] and \[\begin{aligned} & \sum_{1\le j \le m} e_{\mathcal{E}}(D_j,S) +\frac{1}{2} \sum_{1\le j \le m} \left( \sum_{i\ne j} e_{\mathcal{E}}(D_j,D_i)\right) \le | \mathcal{E}| = r-1. \end{aligned}\]
By the above two inequalities, we obtain \[\begin{aligned} r(|S|+2) ~ & \le rm \\ & \le \sum_{1\le j \le m}\left( e_G(D_j,S) + \sum_{i\ne j} e_{\mathcal{E}}(D_j,D_i) \right) \\ & \le \sum_{v\in S} \deg_G(v) + \sum_{1\le j \le m}\left( \sum_{i\ne j} e_{\mathcal{E}}(D_j,D_i) \right) \\ & \le r|S| + 2(r-1) – 2 \sum_{1\le j \le m} e_{\mathcal{E}}(D_j,S) \\ & < r(|S|+2) . \end{aligned}\]
This is a contradiction. Hence, Theorem 1.4 is proved. ◻
We next prove Theorem 1.5.
Proof of Theorem 1.5. Let \(G\) be a \(k\)-connected \(K_{1,k+1}\)-free graph. Suppose that \(G\) has no path-system. By Theorem 1.1, there exists a vertex set \(S\) in \(G\) such that \(\omega(G-S) \ge |S|+2\). Since \(G\) is \(k\)-connected and \(G-S\) is not connected, we have \(|S| \ge k\). Let \(D_1, D_2, \ldots, D_m\) be the components of \(G-S\), where \(m=\omega(G-S) \ge |S|+2\).
Construct a bipartite graph \(H:=H(\mathcal{D},S)\) with bipartition \((\mathcal{D},S)\) from \(G\) as follows:
(i) \(\mathcal{D}=\{D_1,D_2, \ldots, D_m\}\) consists of \(m\) vertices which correspond to \(m\) components of \(G-S\), and
(ii) \(D_i \in \mathcal{D}\) and \(v\in S\) are adjacent in \(H\) if and only if there is an edge in \(G\) joining \(v\) to \(D_i\).
Since \(G\) is \(k\)-connected, we have \(\deg_H(D_i) \ge k\) for every \(1 \le i \le m\). Thus, \(e_H(\mathcal{D},S)\geq km\). On the other hand, each vertex \(v \in S\) satisfies \(\deg_H(v) \le k\) because \(G\) is \(K_{1,k+1}\)-free. Hence, \(e_H(\mathcal{D},S) \le k|S|\), leading to \(m \le |S|\). This contradicts \(m \ge |S|+2\). Therefore, the theorem is proved. ◻
In order to prove Theorem 1.6, we focus on a parity \((g,f)\)-factor. Let \(\mathbb{Z}\) denote the set of integers, and let \(G\) be a graph. For two functions \(g,f:V(G) \to \mathbb{Z}\) satisfying \(g(v) \le f(v)\) and \(g(v) \equiv f(v) \pmod{2}\) for all \(v\in V(G)\), a spanning subgraph \(F\) of \(G\) is called a parity \((g,f)\)-factor if \[g(v) \le \deg_F(v) \le f(v) \quad \mbox{and} \quad \deg_F(v) \equiv f(v) \pmod{2} ,\] for all \(v\in V(G)\). For an integer-valued function \(h\) defined on \(V(G)\) and a subset \(X\subseteq V(G)\), we briefly write \[h(X):=\sum_{x\in X} h(x) \quad \mbox{and} \quad \deg_G(X):= \sum_{x\in X} \deg_G(x).\]
A criterion for a graph to have a parity \((g,f)\)-factor is given in the following theorem.
Theorem 2.1 (Lovasz [4], Theorem 6.1 in [1]).Let \(G\) be a connected graph and let \(g,f:V(G) \to \mathbb{Z}\) be two functions satisfying \(g(v) \le f(v)\) and \(g(v) \equiv f(v) \pmod{2}\) for all vertices \(v\) of \(G\). Then \(G\) has a parity \((g,f)\)-factor if and only if for all disjoint subsets \(S,T \subseteq V(G)\), \[\begin{aligned} \eta(S,T) := f(S) + \deg_G(T) -g(T) -e_G(S,T) -q(S,T) \ge 0, \end{aligned}\] where \(q(S,T)\) denotes the number of components \(D\) of \(G-(S\cup T)\) satisfying \[\begin{aligned} f(D)+ e_G(D,T) \equiv 1 \pmod{2}. \label{eq-9} \end{aligned} \tag{3}\]
Moreover, it is shown in [5] that \[\begin{aligned} \eta(S,T) \equiv f(V(G)) \pmod{2} . \label{eq-10} \end{aligned} \tag{4}\]
Note that in Theorem 2.1, we allow \(g(x)<0\) for some vertices \(x\) and \(\deg_G(y)<f(y)\) for some vertices \(y\). Moreover, a component \(D\) of \(G-(S\cup T)\) satisfying (3) is called an \(f\)-odd component of \(G-(S \cup T)\).
We are ready to prove Theorem 1.6.
Proof of Theorem 1.6. Let \(G\) be a connected bipartite graph with bipartition \((A,B)\) which satisfies (1) and (2), and let \(W\) be a set of even number of vertices of \(A\). Write \(N\) for a sufficiently large odd integer. Define two functions \(g,f :V(G) \to \mathbb{Z}\) as \[g(v)= \left\{ \begin{array}{ll} -N & \mbox{if $v\in W$,} \\ -N-1 & \mbox{otherwise,} \end{array} \right. \quad \mbox{and} \quad f(v)= \left\{ \begin{array}{ll} 1 & \mbox{if $v\in W$,} \\ 2 & \mbox{otherwise.} \end{array} \right.\]
Then \(G\) has a path-system with respect to \(W\) if and only if \(G\) has a parity \((g,f)\)-factor. Note that if a parity \((g,f)\)-factor contains cycles, then we can remove them. In other word, a minimal parity \((g,f)\)-factor is a path-system with respect to \(W\). By Theorem 2.1, it suffices to show that \(\eta(S,T)=f(S) + \deg_G(T) -g(T) -e_G(S,T) -q(S,T)\ge 0\) for all disjoint subsets \(S\) and \(T\) of \(V(G)\).
Since \(f(V(G))\) is even, \(\eta(\emptyset, \emptyset)= -q(\emptyset, \emptyset)=0\) and so we may assume that \(S\cup T \ne \emptyset\). If \(T\) contains a vertex of \(G\), then \(\eta(S,T)\ge 0\) because \(N\) is sufficiently large. Hence, we consider the case where \(T\) is an empty set. It suffices to show that \(\eta(S,\emptyset)=f(S) – q(S,\emptyset) \ge 0\) for all subsets \(\emptyset \neq S \subseteq V(G)\).
Let \(D_1, D_2, \ldots, D_m\) be the \(f\)-odd components of \(G-S\), where \(m=q(S, \emptyset)\). Then \(f(D_i) \equiv 1 \pmod{2}\) for every \(1\le i \le m\), which implies that \(D_i\) has an odd number of vertices of \(W\). In particular, each \(D_i\) contains at least one vertex of \(W \subseteq A\). Put \(X= V(D_1) \cup V(D_2) \cup \cdots \cup V(D_m)\). We consider the following two cases.
Case 1. There exists a component \(D_k\), \(1 \le k \le m\), such that \(V(D_k) \cap B \neq \emptyset\).
Note that \(V(D_k)\cap A \ne \emptyset\). Let \(X'=X \setminus V(D_k)\). Then \(N_G(X'\cap A)\ne B\) and \(N_G(X'\cap B)\ne A\). It follows from (1) and (2) that \[\begin{aligned} 2 |X'\cap A| & \le |N_G(X'\cap A) | \le |X'\cap B| +|S\cap B|, \end{aligned}\] and \[\begin{aligned} |X'\cap B| & \le |N_G(X'\cap B) | \le |X'\cap A| + |S\cap A| . \end{aligned}\]
Adding the above two inequalities implies that \[m-1 \le |X'\cap A| \le |S\cap A|+|S\cap B| =|S|.\]
By this inequality, we obtain \[\begin{aligned} \eta(S, \emptyset) & = f(S) -q(S,\emptyset) \\ & = f(S\cap A) +f(S\cap B) – m \\ & = 2|S| – |S\cap W| – m \ge -1. \end{aligned}\] Since \(\eta(S, \emptyset)\equiv f(V(G)) \equiv 0 \pmod{2}\) by (4), the above inequality implies that \(\eta(S, \emptyset) \ge 0\). Consequently, \(\eta(S,\emptyset) \ge 0\) in this case.
Case 2. Every \(D_i\), \(1\le i \le m\), satisfies \(V(D_i) \cap B = \emptyset\).
Since \(G\) is a bipartite graph and \(V(D_i) \subseteq A\), we have \(|V(D_i)|=1\) for every \(1\le i \le m\). Hence, \(X \subseteq A\), \(|X|=m\), and \((A \cap S) \cup N_G(X) \subseteq S\).
If \(N_G(X) \neq B\), then \(|N_G(X)| \ge 2|X|\) by (1) and thus \[\begin{aligned} \eta(S,\emptyset) =f(S) – q(S,\emptyset) \ge 2|N_G(X)|-m \ge 4|X|-m \ge 0. \end{aligned}\]
Thus, we may assume that \(N_G(X)=B\). It follows from the assumption \(|A| \le 2|B|\) that \[\begin{aligned} \eta(S,\emptyset)&=f(S) – q(S,\emptyset) \ge 2|N_G(X)|-m\\ & = 2|B|-m \ge |A|-m \ge 0. \end{aligned}\]
Consequently, the proof is complete. ◻
The second author was supported by JSPS KAKENHI Grant Numbers 20K03724.
The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.
No data was used for the research described in the article.