Perfect Matching and Zero-Sum 3-Magic Labeling

1. Introduction and Basic Definitions

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.

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)\to 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⩾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\mathrm{\setminus }\{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}\mathrm{\setminus }\{2\}$ or $\mathbb{N}\mathrm{\setminus }\{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\ne 5)$, $\mathbb{N}\mathrm{\setminus }\{2,4\}\subseteq N(G)$. Moreover, they proved that if $r$ $(r\ne 5)$ is odd and $G$ is a $2$-edge connected $r$-regular graph, then $N(G)=\mathbb{N}\mathrm{\setminus }\{2\}$, implying $G$ admits a zero-sum 3-magic labeling. Thus they proposed the following conjecture.

As a consequence of our main result, we obtain the following result, partially confirming Conjecture 1.

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)\to 2$, and $E(E(G)–EM)\to 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.

2. The Proof of Theorem 1

We begin with several important lemmas. The first one is well known as Tutte’s Theorem [3] and is essential in the present paper.

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.

We remark that Lemma 4 does not hold when $d⩾3$. However, we may obtain a similar result for a vertex pair when $d=3$.

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⩽d_{P_j}(v)⩽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 $v{v}_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)⩽3|S_p|$. Since $|S|⩾|S_p|$, we have: $$3|S|⩾3|S_p|⩾3q(G-S).$$ Then, $|S|⩾q(G-S),$ yielding a contradiction. Therefore, Tutte’s condition holds, and thus by Lemma 1 (Tutte’s Theorem), $G$ has a perfect matching.

Acknowledgments

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).