Menu
A mapping \(l : E(G) \rightarrow A\), where \(A\) is an abelian group written additively, is called an edge labeling of the graph \(G\). For every positive integer \(h \geqslant 2\), a graph \(G\) is said to be zero-sum \(h\)-magic if there is an edge labeling \(l\) from \(E(G)\) to \(\mathbb{Z}_{h} \backslash \{0\}\) such that \(s(v) = \sum_{uv\in E(G)}l(uv) = 0\) for every vertex \(v \in V(G)\). In 2014, Saieed Akbari, Farhad Rahmati and Sanaz Zare proved that if \(r\) \((r\not= 5)\) is odd and \(G\) is a \(2\)-edge connected \(r\)-regular graph, \(G\) admits a zero-sum 3-magic labeling, and they also conjectured that every 5-regular graph admits a zero-sum \(3\)-magic. In this paper, we first prove that every 5-regular graph with every edge contained in a triangle must have a perfect matching, and then we denote the edge set of the perfect maching by \(EM\), and we make a labeling \(l : E(EM) \rightarrow {2}\), and \(E(E(G) – EM) \rightarrow {1}\). Thus we can easily see this labeling is a zero-sum 3-magic, confirming the above conjecture with a moderate condition.
Graphs \(G\) considered here are all connected, finite and undirected with multiple-edges without loops. Finding a matching in a bipartite graph can be treated as a network flow. The study of matchings in a bipartite graph can be traced back to the early of the 20th century. In 1935, P. Hall proved a well-known result (Hall’s Theorem) which provided a necessary and sufficient condition for an \(X, Y\)-bipartite graph to have a matching that saturates \(X\) [1,3.1.11 Theorem]. When \(|X|=|Y|\), Hall’s Theorem is the Marriage Theorem, proved originally by Frobenius in 1917 [2]. Later in 1947, Tutte [3] investigated the problem concerning the existence of a perfect matching in a general graph and provided a necessary and sufficient condition (Tutte’s Condition) for such a graph to have a perfect matching [Lemma 1]. If every vertex in a graph has the same degree \(r\) then this graph is referred to as a \(r\)–\(regular\) graph. In case of regular graphs, Peterson [4] proved that every \(3\)-regular graph without a bridge (an edge whose deletion disconnects the graph) has a perfect matching. In 1981, Naddef and Pulleyblank considered K-regular graphs with specified edge connectivity and showed some classical theorems and some new results concerning the existence of matchings can be proved by using polyhedral characterization of Edmonds [5]. It is not hard to see that a \(5\)-regular \(4\)-edge connected graph has a perfect matching (see [5] for detail). However very little is known about the existence of a perfect matching in a general \(5\)-regular graph. In this paper we provide a sufficient condition for a \(5\)-regular graph to have a perfect matching and our main result is as follows.
Theorem 1. Every 5-regular graph in which each edge is contained in a triangle has a perfect matching.
Our motivation for this work is towards resolving a conjecture of Saieed Akbari, Farhad Rahmati and Sanaz Zare [6]. Before discussing this conjecture we require some more notation. A mapping \(l : E(G) \rightarrow A\), where \(A\) is an abelian group written additively, is called an edge labeling of the graph \(G\). Given an edge labeling \(l\) of the graph \(G\), the symbol \(s(v)\), which represents the sum of the labels of edges incident with \(v\), is defined to be \(s(v) = \sum_{uv\in E(G)} l(uv)\), where \(v \in V(G)\). For every positive integer \(h \geqslant 2\), a graph \(G\) is said to be \(zero\)–\(sum\) \(h\)–\(magic\) if there is an edge labeling from \(E(G)\) into \(\mathbb{Z}_{h} \backslash \{0\}\) such that \(s(v) = 0\) for every vertex \(v \in V(G)\). The \(null\) set of a graph \(G\), denoted by \(N(G)\), is the set of all natural numbers \(h\in \mathbb{N}\) such that \(G\) admits a zero-sum \(h\)-magic labeling.
Recently, Choi, Georges and Mauro [7] proved that if \(G\) is a \(3\)-regular graph, then \(N(G)\) is \(\mathbb{N}\backslash \{2\}\) or \(\mathbb{N}\backslash \{2,4\}\). Saieed Akbari, Farhad Rahmati and Sanaz Zare [6] extend this result by showing that if \(G\) is an \(r\)-regular graph, then for even \(r\) \((r >2)\), \(N(G) =\mathbb{N}\) and for odd \(r\) \((r\not= 5)\), \(\mathbb{N}\backslash\{2,4\} \subseteq N(G)\). Moreover, they proved that if \(r\) \((r\not= 5)\) is odd and \(G\) is a \(2\)-edge connected \(r\)-regular graph, then \(N(G) =\mathbb{N}\backslash \{2\}\), implying \(G\) admits a zero-sum 3-magic labeling. Thus they proposed the following conjecture.
Conjecture 1. Every 5-regular graph admits a zero-sum 3-magic labeling.
As a consequence of our main result, we obtain the following result, partially confirming Conjecture 1.
Corollary 1. Every 5-regular graph in which each edge is contained in a triangle admits a zero-sum 3-magic labeling.
By Theorem 1, every 5-regular graph in which each edge is contained in a triangle has a perfect matching. We denote the edge set of the perfect maching by \(EM\), and we make a labeling \(l : E(EM) \rightarrow {2}\), and \(E(E(G) – EM) \rightarrow {1}\). It is easily to see this labeling is a zero-sum 3-magic. Thus every 5-regular graph in which each edge is contained in a triangle admits a zero-sum 3-magic labeling, proving Corollary 1.
We next introduce some basic definitions which will be used in the proof of our main result. If \(X\) and \(Y\) are disjoint vertex sets of \(G\) with \(x \in X\) and \(y \in Y\), an edge{\(x\), \(y\)} is usually written as \(xy\) (or \(yx\)), and such an edge \(xy\) is also called an \(X-Y\) edge. The set of all \(X-Y\) edges in the edge set \(E\) is denoted by \(E(X,Y)\). We denoted by \(G(X,Y)\) the subgraph of \(G\) with vertex set \(X\bigcup Y\) and the edge set \(E(X,Y)\). An \(odd\) (or even) \(component\) of a graph is a connected component of odd (or even) number of vertices, and an \(odd\) (or even) \(vertex\) is a vertex with odd (or even) degree.
Definition 1. For a graph \(G\), for any vertex set \(S\) of \(G\), and any odd component \(Q\) of \(G – S\), consider a connected component of \(G (S, V(Q))\) which has odd number of edges in \(E (S, V(Q))\). The vertices of this component induce a subgraph \(P\) in \(G\), and we call it an odd component induced subgraph.
Definition 2. Let \(S\) be any vertex set and \(v \in S\). The vertex \(v\) is called removable from \(S\) if \(q(G – S') = q(G – S) – 1\), where \(q(G-S)\) denotes the number of odd components of \(G-S\) and \(S'= S – v\).
Definition 3. Let \(S\) be any vertex set, and let \(v,w \in S\). The vertex pair \((v, w)\) is called removable from \(S\) if \(q(G – S') = q(G – S) – 2\), where \(S'=S-v-w\).
Definition 4. Let \(S\) be any vertex set, \(Q\) be one of the odd components of \(G – S\), we call \(Q\) the first type of odd component (with respect to \(S\)) if there is an odd component induced subgraph \(P\), such that there exists a removable vertex or a removable vertex pair in \(S\cap V(P)\). Otherwise, \(Q\) is called the second type of odd component (with respect to \(S\)).
Definition 5. Let \(S\) be any vertex set, \(Q\) be an odd component of \(G – S\) and \(P\) be an odd component induced subgraph. A
connected subgraph \(K\) of \(P\) is called a \(2\)–\(claw\) \(substructure\), if the following conditions
hold:
1. \(V(K) \cap S\) has 3 vertices \(\{v, v_{1}, v_{2}\}\), and each vertex is
connected to exactly 3 odd components of \(G-S\).
2. The degree of \(v\) in \(P\) is 3.
In this case the vertices \(\{v, v_{1},
v_{2}\}\) are called \(roots\)
of \(K\).
We begin with several important lemmas. The first one is well known as Tutte’s Theorem [3] and is essential in the present paper.
Lemma 1. (Tutte’s Theorem)A graph \(G\) has a perfect matching if and only if \(q(G-S) \leqslant |S|\) for all \(S \subseteq V(G)\) , where \(q(G-S)\) denotes the number of odd components of \(G-S\).
If a graph \(G\) has no perfect matching, then there must exist \(S \subseteq V(G)\) with \(q(G-S) > |S|\). Such a set \(S\) is called an \(antifactor\) set of \(G\).
From now on we always assume that \(G\) is a 5-regular graph in which each edge is contained in a triangle.
Lemma 2. For any vertex set \(S\), every odd component of \(G – S\) has at least one odd component induced subgraph.
Proof. For any vertex set \(S\), and any odd component \(Q\) of \(G – S\), we assume that \(|E (S, V(Q)) | = d\), and the number of vertices in \(Q\) is \(p\). Since \(Q\) is an odd component, we know that \(p\) is odd. Let \(q\) be the sum of the degrees of each vertex contained in \(Q\). Clearly \(q\) is even by the handshaking lemma. Since \(G\) is a \(5\) – regular graph, we have \[q = 5p – d.\] Thus \(d\) is odd as \(q\) is even and \(p\) is odd. That is, the sum of the edges of all connected portions of \(G(S, V(Q))\) is odd, so \(G(S, V(Q))\) has at least one connected subgraph having an odd number of edges. The vertices of this connected subgraph induce a subgraph in \(G\) which is the desired odd component induced subgraph.
Lemma 3. For every vertex set \(S\) and every odd component induced subgraph \(P\), there exists at least one vertex \(v \in S \cap V(P)\), such that \(d_{P}(v) \geqslant 3\).
Proof. Assume that for every vertex \(v\) in \(S \cap V(P)\), we have \(d_{P}(v) \leqslant 2\). Since \(v\) has an edge in \(P\) and this edge is also in a triangle, the fact that the triangle is a connected graph implys that it is in \(P\), so we must have \(d_{P}(v) \not= 1\), and thus \(d_{P}(v) = 2\) for every vertex \(v\) in \(S \cap V(P)\). Suppose that there are \(k\) vertices in \(S \cap V(P)\), and \(s\) edges in \(E(S) \cap E(P)\). Then \(|E(S,V(Q)) \cap E(P)| = 2k-2s\), which is even, a contradiction. Thus the lemma holds.
Lemma 4. If a vertex \(v\) in \(S\) is connected to \(d\) odd components (where \(d \leqslant 2\)), then \(v\) is a removable vertex .
Proof. If \(v \in S\) is connected to only one odd component \(Q\), then we remove \(v\) out of \(S\), and denote the new vertex set by \(S_{1}=S-v\). Since \(Q\) is an odd component, after adding a vertex \(v\) to \(Q\), it becomes an even component. Note that there is no change in parity for all other odd components. Thus \(q(G – S_{1}) = q(G – S) – 1\), so \(v\) is a removable vertex.
If \(v\) is connected to \(2\) odd components \(Q_{i}\) and \(Q_{j}\), then we also remove \(v\) out of \(S\), and denote the new vertex set by \(S_{1}=S-v\). Since \(v\) is connected to \(Q_{j}\) and \(Q_{i}\), at this time, \(Q_{i}\), \(Q_{j}\) and \(v\) become a new connected component, and the number of its vertices is \(|Q_{i}| + |Q_{j}| + 1\) which is odd. Note that the number of odd components is reduced by one, that is, \(q(G – S_{1}) =q(G – S) – 1\), so \(v\) is a removable vertex.
We remark that Lemma 4 does not hold when \(d \geqslant 3\). However, we may obtain a similar result for a vertex pair when \(d = 3\).
Lemma 5. If a vertex pair \((v, w)\) in \(S\) is connected to exactly \(3\) odd components, then \((v, w)\) is a removable vertex pair.
Proof. Assume that the vertex pair \((v_{1}, v_{2})\) is connected to \(3\) odd components \(Q_{i}\), \(Q_{j}\) and \(Q_{k}\). We move \((v_{1}, v_{2})\) out of \(S\), and denote the new vertex set by \(S_{1}\). Clearly \(|S_{1}| = |S| – 2\). As before, there is no change in parity for all odd components except \(Q_{i}\), \(Q_{j}\) and \(Q_{k}\). Since the vertex pair \((v_{1}, v_{2})\) is connected to \(Q_{i}\), \(Q_{j}\) and \(Q_{k}\), the components \(Q_{i}\), \(Q_{j}\) and \(Q_{k}\) and the vertex pair \((v_{1}, v_{2})\) become a new connected component, and the number of its vertices \(|Q_{i}| + |Q_{j}| + |Q_{k}| + 2\) is odd. So the number of odd components is reduced by two, and we have \(q(G – S_{1}) = q(G – S) – 2\). Thus the vertex pair \((v_{1}, v_{2})\) is a removable vertex pair.
Lemma 6. Let \(Q\) be a second type of odd component in \(G-S\) and \(P_{j}\) be the jth odd component induced subgraph of \(Q\). Then for all \(j\), \(P_{j}\) has a \(2\)-claw substructure.
Proof. According to Lemma 2, \(Q\) has an odd component induced subgraph \(P_{j}\). Let \(v\) be a vertex of \(V(P_{j}) \cap S\) such that \(d_{P_{j}}(v)\) is maximum among all vertices in \(V(P_{j}) \cap S\). By Lemma 3, we have \[3 \leqslant d_{P_{j}}(v) \leqslant 5.\] We now divide the rest of the proof into 3 cases.
Case 1. \(d_{P_{j}}(v) = 5.\)
In this case, since \(G\) is a \(5\)-regular graph, all the edges connected to \(v\) are in \(P_{j}\), so there is only one odd component adjacent to \(v\). By Lemma 4, \(v\) is a removable vertex, and thus \(Q\) is a first type of odd component, yielding a contradiction.
Case 2. \(d_{P_{j}}(v) = 4.\)
In this case, since \(G\) is a \(5\)-regular graph, only one of the edges of \(v\) is not in \(P_{j}\), so there are at most \(2\) odd components adjacent to \(v\). By Lemma 4, \(v\) is a removable vertex, and thus \(Q\) is a first type of odd component, yielding a contradiction.
Case 3. \(d_{P_{j}}(v) = 3.\)
Since \(d_{p_{j}}(v)=3\) and \(G\) is \(5\)-regular, we know that \(v\) is connected to at most two other odd components. We may always assume that \(v\) is connected to two other odd components \(Q_s\) and \(Q_t\). For otherwise, by Lemma 4, \(v\) is removable, and thus \(Q\) is the first type, yielding a contradiction.
Subcase 1. \(v\) has \(0\) edge in \(E(S) \cap E(P_{j}).\)
In this subcase, as mentioned before, \(v\) is connected to two other odd components \(Q_{t}\) and \(Q_{s}\). We assume that \(e_{Q_{t}}(v)\) is connected to \(Q_{t}\), where \(e_{Q_{t}}(v)\) denotes the neighbors of \(v\) in \(Q_{t}\), and \(e_{Q_{s}}(v)\) is connected to \(Q_{s}\). Let us consider \(e_{Q_{t}}(v)\). By the assumption of \(G\), \(e_{Q_{t}}(v)\) must be an edge of a triangle, so there must exist another edge \(e_t\) connected to \(v\) in this triangle. If \(e_{t} = e_{Q_{s}}(v)\), then we deduce that \(Q_{t}\) is connected to \(Q_{s}\), yielding a contradiction, because \(Q_{t}\) and \(Q_{s}\) are different odd components. The same argument shows that \(e_{t} \notin E(P_{j})\), so \(e_{t}\) is the 6th edge of \(v\), yielding a contradiction.
Subcase 2. \(v\) has \(1\) edge in \(E(S) \cap E(P_{j})\).
In this subcase, \(v\) has \(2\) edges in \(E(V(Q), S)\). Let \(v_{1}\), \(v_{2} \in Q\) be the \(2\) vertices, which are adjacent to \(v\). And \(v_{3}\in S\) be the vertex which is adjacent to \(v\). Let \(v_{4} \in Q_{t}\) and \(v_{5} \in Q_{s}\), which are adjacent to \(v\).
Since the edge \(e(v_{4},v)\) is in a triangle, we may let \(v_q\) be such that \(vv_{4}v_{q}\) is a triangle. Thus \(v_{q}\) is a neighbor of \(v\), and so \(v_{q} \in \{ v_{i}|i = 1, 2, 3, 4, 5\}\). As proved before \(v_{q} \notin \{ v_{i}|i = 1, 2, 4, 5\}\) (as \(Q\), \(Q_{t}\), \(Q_{s}\) are different odd components, so any two of \(Q\), \(Q_{t}\), \(Q_{s}\) are not connected), so \(v_{q} = v_{3}\). For the same reason, \(v_{3}\) is connected to \(v_{5}\) in \(Q_{t}\). Since \(v_{3} \in V(P_{j})\), there exists a vertex \(v_{6} \in Q\) adjacent to \(v_{3}\). If \((v,v_{3})\) is connected to \(3\) different components, by Lemma 5, \((v, v_{3})\) is a removable vertex pair, yielding a contradiction.
Otherwise, the last neighbor \(v_{p}\) of \(v_{3}\) is in another odd component. Since the edge \(e(v_{3}, v_{p})\) is in a triangle, \(v_{3}\) must have another neighbor \(v_{q}\) which is adjacency to \(v_{p}\). As before \(v_{q} \notin \{ v_{i}|i = p , 4, 5, 6\}\). Thus \(v_q =v\), which implies that \(v\) has 6 neighbors, yielding a contradiction.
Subcase 3. \(v\) has \(2\) edge in \(E(S) \cap E(P_{j})\).
In this subcase, we assume that \(2\) vertices \(v_{1}\) and \(v_{2}\) are the neighbors of \(v\) and in \(S \cap V(P_{j})\). If one of the vertex in \(\{v, v_{1}, v_{2}\}\) is connected to at most 1 other odd component, then according to Lemma 4, then this vertex is removable, so \(Q\) is a first type of odd component, yielding a contradiction.
Next we may assume that \(v\) is connected to two odd components other than \(Q\). and \(v_{i} \in \{v_{1}, v_{2}\}\) is connected to three odd components other than \(Q\). Let \(e_{1}\), \(e_{2}\) and \(e_{3}\) be the edges joining \(v_{i}\). Without loss of generality, we may assume there is an edge \(e_{j}\) connected to \(e_{1}\). As we proved before, the third vertex of the triangle containing \(e_{1}\) must be \(v\). So \(v\) has a neighbor in this component outside of \(P_{j}\). Similar results hold for \(e_{2}\) and \(e_{3}\). Thus we have 3 neighbors of \(v\) outside of \(P_{j}\). This together with \(d_{p_{j}}(v)=3\) shows that \(v\) has six neighbors, yielding a contradiction.
In conclusion, we have just shown that every vertex in \(\{v, v_{1}, v_{2}\}\) is connected to \(Q\) and 2 other odd components. Therefore, \(P_j\) has a 2-claw substructure.
Subcase 4. \(v\) has \(3\) edges in \(E(S) \cap E(P_{j})\).
In this subcase, \(v\) has no neighbour in \(Q\), that is \(E(v) \cap E(Q,S) = \varnothing\), contradicting the definition of \(P_{j}\).
We are now ready to prove Theorem 1.
Proof of Theorem 1:
Assume that the vertex set \(S\) is a minimal counterexample to Tutte’s condition, i.e., \(S\) is a minimal set such that \(|S|< q(G-S)\). Then every odd component of \(G-S\) is of the second type. For otherwise, if \(Q\) is the first type of odd component of \(G-S\), then there exists an odd component induced subgraph \(P\), which has a removable vertex \(v\) (or a removable vertex pair (\(v_{1}\) ,\(v_{2}\))). Let \(S_{1}\) be the new vertex set after removing \(v\) (or (\(v_{1}\) ,\(v_{2}\))) from \(S\). Then \(S_{1}= S – v\) (or \(S_{1}= S- v_{1}-v_{2}\)). So we may replace \(S\) by \(S_{1}\). By the definitions 2 and 3, we have \(q(G-S_{1})= q(G-S)-1\) (or \(q(G-S_{1})= q(G-S)-2\)). That is \(q(G-S_{1})-|S_{1}|=q(G-S)-|S|\). So \(|S_{1}|<q(G-S_{1})\), yielding a contradiction to the minimality of \(S\).
Suppose that \(Q\) is a second type of odd component and \(P\) is an odd component induced subgraph. By Lemma 6, \(P\) has a 2-claw substructure which has a set of 3 roots. Let \(S_{p}\) be the set of all such roots corresponding to all odd components of \(G-S\). Each vertex in \(S_{p}\) has 3 edges connecting itself to the odd components. Let \(E(S_{p})\) denote the set of all these edges. Then \(|E(S_{p})|=3|S_{p}|\). Since \(P\) has a 2-claw substructure, there are at least three edges form \(Q\) to \(S_{p}\). So this gives at least \(3q(G – S)\) edges (from all odd components to \(S_{p}\)). Since each of these edges is in \(E(S_{p})\), we obtain \(3q(G – S)\leqslant 3 |S_{p}|\). Since \(|S| \geqslant |S_{p}|\), we have: \[3|S| \geqslant 3|S_{p}| \geqslant 3q(G-S).\] Then, \(|S| \geqslant q(G-S),\) yielding a contradiction. Therefore, Tutte’s condition holds, and thus by Lemma 1 (Tutte’s Theorem), \(G\) has a perfect matching.
This research was supported in part by a Discovery Grant from the Natural Sciences and Engineering Research Council of Canada (Grant No. RGPIN 2017-03903).