Recently, it was proved that if \(K_{2,2n}\) admits an edge \(k\)-product cordial labeling, then either \(k=2n+1\) or \(k\ge 4n+1\), and two related existence problems were posed. In this paper, we prove that \(K_{2,2n}\) is edge \((2n+1)\)-product cordial if and only if \(2n+1\) is a prime. We further show that \(K_{2,4}\) is edge \(k\)-product cordial if and only if \(k=5\) or \(k\ge 9\), while \(K_{2,6}\) is edge \(k\)-product cordial if and only if \(k=7\) or \(k\ge 13\). These results completely answer one of the posed questions and provide further evidence for a general existence conjecture.
A graph of order \(p\) and size \(q\) is called a \((p,q)\) -graph. For \(k\ge 2\) , we let \(\mathbb Z_k=\{0,1,\dots, k-1\}\) be the standard complete residue system modulo \(k\) . Notation and concepts not defined in this paper are referred to the book [1] .
Suppose \(G=(V,E)\) is a \((p,q)\) -graph without isolated vertex. Let \(f:E\to \mathbb Z_k\) be an edge labeling of \(G\) . Let the vertex labeling \(f^*:V\to \mathbb Z_k\) be defined by \(f^*(v)\equiv \prod_{uv\in E} f(uv) \pmod k\) , for every vertex \(v\) . An edge \(e\in E\) and a vertex \(v\in V\) are called an \(i\) -edge and \(j\) -vertex (under \(f\) ), if \(f(e)=i\) and \(f^*(v)=j\) , respectively, where \(i,j\in\mathbb Z_k\) . Let \(e_f(i)\) and \(v_f(j)\) denote the number of \(i\) -edges and the number of \(j\) -vertices, respectively.
For \(k\ge 2\) , an edge labeling \(f: E\to \mathbb Z_k\) of \(G=(V,E)\) is said to be an edge \(k\) -product cordial labeling of \(G\) if \(|e_f(i_1)-e_f(i_2)|\le 1\) and \(|v_f(j_1)-v_f(j_2)|\le 1\) for \(i_1, i_2, j_1,j_2\in \mathbb Z_k\) . \(G\) is edge \(k\) -product cordial if \(G\) admits an edge \(k\) -product cordial labeling.
We first introduce some necessary notation and concepts. Suppose \(f:E\to\mathbb Z_k\) is an edge labeling of \(G=(V,E)\) . In the following, we always let \(E_0\) be the set of all \(0\) -edges under \(f\) and let \(G_0\) be the subgraph of \(G\) induced by the edges in \(E_0\) , i.e., \(G_0=G[E_0]\) . Clearly \(e_f(0)=|E_0|\) and \(v_{f}(0)\ge |V(G_0)|\) . We shall keep these notation throughout the paper.
Let \(G\) be a graph and \(G’\) be a copy of \(G\) . The shadow graph of a graph \(G\) , denoted as \(D(G)\) , is a graph obtained by joining each vertex \(v\) of \(G\) to the neighbors of the vertex \(v’\) in \(G’\) which corresponds to \(v\) . This concept was first introduced by Sampathkumar [2] in 1973. In this paper, we consider the shadow graph of a star \(K_{1,n}\) for \(n\ge 1\) .
Let the vertex and the edge sets of the star \(K_{1,n}\) be \(\{u, u_1, \dots, u_n\}\) and \(\{uu_i\;|\; 1\le i\le n\}\) , respectively. Then we let \(\{u, u’\}\cup\{u_i, u_i’\;|\; 1\le i\le n\}\) and \(\{uu_i, uu_i’, u’u_i, u’u_i’\;|\; 1\le i\le n\}\) be the vertex and edge sets of the graph \(D(K_{1,n})\) , respectively. Thus, \(D(K_{1,n})\) is a \((2n+2, 4n)\) -graph. Note that \(D(K_{1,n})\cong K_{2,2n}\) . So in the coming sections, we shall use \(K_{2,2n}\) instead of \(D(K_{1,n})\) .
In [3] , there are two questions related to the theorem below.
Theorem 1.1. [3, Theorem 2.1] Let \(n\ge 1\) and \(k\ge 2\) . Suppose \(D(K_{1,n})\) admits an edge \(k\) -product cordial labeling \(f\) , then \(k\ge 4n+1\) or \(k=2n+1\) .
Question 1.2. [3, Question 2.5] Is \(D(K_{1,n})\) edge \((2n+1)\) -product cordial for \(n\ge 3\) ?
Question 1.3. [3, Question 2.6] Is \(D(K_{1,n})\) edge \(k\) -product cordial for \(n\ge 2\) when \(k\ge 4n+1\) ?
In this paper, we will answer the first question completely and investigate the second question for \(n=2,3\) .
In [3] , there is an edge \((2n+1)\) -product cordial labeling for each of \(K_{2,2n}\) when \(n=1,2\) . For completeness, these labelings are reproduced in Figures 1(a) and 1(b) . All edge labels are indicated next to the respective edges and the induced vertex labels are indicated on the vertices, respectively. It is straight forward to verify the correctness.
Remark 2.1. In Theorem 1.1 , suppose \(K_{2,2n}\) admits an edge \((2n+1)\) -product cordial labeling \(f\) . Note that \(K_{2,2n}\) is a \((4n, 2n+2)\) -graph. From the definition of \((2n+1)\) -product cordial labeling, we have \(e_f(i)\ge \left\lfloor\frac{4n}{2n+1}\right\rfloor=1\) and \(v_f(j)\le \left\lceil\frac{2n+2}{2n+1}\right\rceil=2\) , for \(0\le i,j\le 2n\) . Thus, \(e_f(0)\ge 1\) and this implies that \(v_f(0)\ge 2\) . Therefore, \(v_f(0)=2\) . Since there are only \(2n+2\) vertices, \(v_f(j)=1\) for \(1\le j\le 2n\) .
If \(e_f(0)\ge 2\) , i.e., \(|E_0|\ge 2\) , then \(G_0\) is either acyclic or contains a cycle of order at least 4. This implies that \(v_f(0)\ge 3\) which is a contradiction. Thus, we have \(e_f(0)=1\) , \(v_f(0)=2\) and \(v_f(j)=1\) for \(1\le j\le 2n\) . Since each edge is incident to either \(u\) or \(u’\) , by symmetry, we may assume that \(f(uu_n’)=0\) .
Before studying the edge \(k\) -product cordiality of \(K_{2,2n}\) , we recall some structure about the group of units modulo \(k\) .
Let \(U(\mathbb Z_k)\) be the set of all units in \(\mathbb Z_k\) , i.e., \(U(\mathbb Z_k)=\{i\in\mathbb Z_k\;|\; \mbox{gcd}(i,k)=1\}\) . It is known that \(U(\mathbb Z_k)\) is a multiplicative Abelian group. Suppose \(k=\displaystyle\prod_{j=1}^r p_{j}^{k_j}\) is the prime factorization, where \(p_1, \dots, p_r\) are distinct primes. It is well-known that \[U(\mathbb Z_k)\cong U(\mathbb Z_{p_1^{k_1}})\times \cdots \times U(\mathbb Z_{p_r^{k_r}}).\]
Moreover, \(U(\mathbb Z_k)\) is a cyclic group if and only if \(k= 2,4, p^j, 2p^j\) , where \(p\) is an odd prime and \(j\ge 1\) . We shall use \(\mathfrak{C}_n\) to denote the multiplicative cyclic group of order \(n\) . In fact, \(U(\mathbb Z_2)\cong \mathfrak{C}_1\) , \(U(\mathbb Z_4)\cong \mathfrak{C}_2\) , \(U(\mathbb Z_{p^i})\cong U(\mathbb Z_{2p^i})\cong \mathfrak{C}_{\phi(p^i)}=\mathfrak{C}_{p^i-p^{i-1}}\) , where \(p\) is an odd prime, \(i\ge 1\) and \(\phi\) is the Euler function. Moreover, \(U(\mathbb Z_{2^j})\cong \mathfrak{C}_2\times \mathfrak{C}_{2^{j-2}}\) , where \(j\ge 3\) . Thus, the order of \(U(\mathbb Z_k)\) is always even when \(k\ge 3\) .
Theorem 2.2. Suppose \(2n+1\) is a prime for \(n\ge 1\) . \(K_{2,2n}\) is edge \((2n+1)\) -product cordial.
Proof. We only need to consider \(n\ge 3\) . First we construct the following table.
| 1 | 2 | \(\cdots\) | n-1 | n | n+1 | \(\cdots\) | 2n-1 | |
| 1 | 2 | \(\cdots\) | n-1 | n+1 | n+2 | \(\cdots\) | 2n | |
| Column sum of the above array | 2 | 4 | \(\cdots\) | 2n-2 | 2n+1 | 2n+3 | \(\cdots\) | 4n-1 |
| Take modulo 2n | 2 | 4 | \(\cdots\) | 2n-2 | 1 | 3 | \(\cdots\) | 2n-1 |
Note that entries in the last row of the table are the final exponents of the induced column products of a primitive root.
Let \(\rho\) be the primitive root of modulo \(2n+1\) , i.e., \(\rho\) is a generator of the cyclic group \(U(\mathbb Z_{2n+1})\cong \mathfrak{C}_{2n}\) . Define \(f:E\to \mathbb Z_{2n+1}\) by
\(f(uu_i)=\rho^i\) , \(1\le i\le n\) (the first \(n\) entries of the first row of Table 1 );
\(f(uu_i’)=\rho^{n+i}\) , \(1\le i\le n-1\) (the last \(n-1\) entries of the first row of Table 1 ) and \(f(uu’_n)=0\) ;
\(f(u’u_i)=\rho^i\) , \(1\le i\le n-1\) (the first \(n-1\) entries of the second row of Table 1 ) and \(f(u’u_n)=\rho^{n+1}\) (the first \(n\) -th entry of the second row of Table 1 );
\(f(u’u’_i)=\rho^{n+1+i}\) , \(1\le i\le n-1\) (the last \(n-1\) entries of the second row of Table 1 ) and \(f(u’u’_n)=\rho^{2n}\) .
Note that \(\rho^{2n}\equiv 1\pmod{2n+1}\) and \(\rho^n\equiv -1\equiv 2n\pmod{2n+1}\) . Now \(e_f(0)=1\) , \(e_f(\rho^n)=e_f(2n)=1\) , and \(e_f(i)=2\) , where \(1\le i\le 2n-1\) .
From the last row of Table 1 , we have \(f^*(u_j)=\rho^{2j}\) , \(1\le j\le n-1\) ; \(f^*(u_n)=\rho^{2n+1}=\rho\) ; \(f^*(u’_j)=\rho^{2j+1}\) , \(1\le j\le n-1\) ; and \(f^*(u’_n)=f^*(u)=0\) . Now \[\begin{aligned}f^{*}(u’) &= \left(\prod_{i=1}^{n-1}\rho^{i}\right) \left(\prod_{i=n+1}^{2n}\rho^{i}\right)\rho^{2n} \\ &= \left(\prod_{i=1}^{n-1}\rho^{i}\right) \left(\prod_{j=1}^{n-1}\rho^{2n-j}\right) \rho^{2n}\rho^{2n} \qquad \bigl(\text{write } i=2n-j\bigr) \\ &= \left(\prod_{i=1}^{n-1}\rho^{i}\rho^{2n-i}\right) \rho^{2n}\rho^{2n} =1, \qquad ( \rho^{2n}=1 \text{ in } \mathbb{Z}_{2n+1}). \end{aligned}\]
Now, the values of \(f^*(u’)=1=\rho^0\) , \(f^*(u_n)=\rho\) and \(f^*(u_j)=\rho^{2j}\) , \(f^*(u’_j)=\rho^{2j+1}\) for \(1\le j\le n-1\) run through \(\rho^0, \rho^1,\dots, \rho^{2n-1}\) once, i.e., \(\mathbb Z_{2n+1}\setminus\{0\}\) once. Combining with \(f^*(u’_n)=f^*(u)=0\) , we have \(v_f(j)=1\) , \(1\le j\le 2n\) and \(v_f(0)=2\) . Thus \(f\) is an edge \((2n+1)\) -product cordial labeling of \(K_{2,2n}\) . \(\square\)
Example 2.3. Let \(n=3\) so that \(k=2n+1=7\) . It is known that \(3\) is a primitive root modulo 7. Namely, \(3^1=3\) , \(3^2=2\) , \(3^3=6\) , \(3^4=4\) , \(3^5=5\) , \(3^6=1\) in \(\mathbb Z_7\) . According to the proof above, we have the following edge \(7\) -product cordial labeling for \(K_{2,2n}\) (Figure 2 ).
Instead of drawing a figure, we shall present the values of a labeling \(f\) for \(K_{2,6}\) by the following table. \[\begin{array}{|c|c|c|c|c|c|c|} f(uu_{1}) & f(uu_{2}) & f(uu_{3}) & f(uu’_{1}) & f(uu’_{2}) & f(uu’_{3}) & f^{*}(u) \\ \hline f(u’u_{1}) & f(u’u_{2}) & f(u’u_{3}) & f(u’u’_{1}) & f(u’u’_{2}) & f(u’u’_{3}) & f^{*}(u’) \\ \hline f^{*}(u_{1}) & f^{*}(u_{2}) & f^{*}(u_{3}) & f^{*}(u’_{1}) & f^{*}(u’_{2}) & f^{*}(u’_{3}) & \mathbb{Z}_{k} \end{array} \;=\; \begin{array}{|c|c|c|c|c|c|c|} 3 & 2 & 6 & 4 & 5 & 0 & 0 \\ \hline 3 & 2 & 4 & 5 & 1 & 1 & 1 \\ \hline 2 & 4 & 3 & 6 & 5 & 0 & \mathbb{Z}_{7} \end{array}\]
We shall use a similar presentation for a general \(n\ge 3\) , namely \[\begin{array}{|c|c|c|c|c|c|c} f(uu_{1}) & \cdots & f(uu_{n}) & f(uu’_{1}) & \cdots & f(uu’_{n}) & f^{*}(u) \\ \hline f(u’u_{1}) & \cdots & f(u’u_{n}) & f(u’u’_{1}) & \cdots & f(u’u’_{n}) & f^{*}(u’) \\ \hline f^{*}(u_{1}) & \cdots & f^{*}(u_{3}) & f^{*}(u’_{1}) & \cdots & f^{*}(u’_{3}) & \mathbb{Z}_{k} \end{array}\]
Theorem 2.4. If \(k=2n+1\) is a composite, then \(K_{2,2n}\) is not edge \(k\) -product cordial.
Proof. Let \(k=ab\) , where \(3\le a\le b<k\) and \(a\) is a prime. Suppose \(K_{2,2n}\) admits an edge \(k\) -product cordial labeling \(f\) . We keep the notation defined in Remark 2.1 .
Since \(1\le e_f(i)\le 2\) for \(1\le i\le 2n\) and \(\sum\limits_{i=1}^{2n} e_f(i)=4n-1\) , there is only one \(i\) such that \(e_f(i)=1\) . Let \(A\) be the set of all \(ja\) -edges for some \(1\le j\le b-1\) and \(B\) be the set of all \(la\) -vertices for some \(1\le l\le b-1\) . By Remark 2.1 and the above result, we have \(2(b-1)\ge |A|\ge 2(b-2)+1\) and \(|B|=b-1\) .
Suppose \(u’\in B\) . There are \(b-2\) vertices of degree 2 in \(B\) . Let \(v\) be one such degree 2 vertex. Therefore, \(v\) is incident with at most two edges in \(A\) . Thus, there are at most \(2(b-2)\) edges incident with vertices in \(B\setminus \{u’\}\) . Consequently, there is at least one edge in \(A\) whose end vertex is not of degree 2 which is impossible
Suppose \(u’\notin B\) . Thus, all \(b-1\) vertices in \(B\) are of degree 2. Moreover, each vertex in \(B\) is incident to only one edge in \(A\) . Therefore, \(|A|=|B|=b-1\) . It contradicts \(|A|\ge 2b-3\) . \(\square\)
We have the following theorem immediately.
Theorem 2.5. \(K_{2,2n}\) is edge \((2n+1)\) -product cordial if and only if \(2n+1\) is a prime.
Let us consider the graph \(K_{2,4}\) . We know that \(K_{2,4}\) is edge \(5\) -product cordial in [3] . So we consider the first case listed in Theorem 1.1 , i.e., \(k\ge 4n+1=9\) .
Recall that, we shall show the edge labels and vertex labels of a labeling \(f\) by a table. So one will see from the table that the edge labels are distinct as well as the vertex labels are also distinct. This means that \(e_f(i)\) is either 0 or 1 and \(v_f(j)\) is also either 0 or 1. Hence, this implies that \(f\) is a required labeling.
Lemma 3.1. If \(U(\mathbb Z_k)\) contains an element of order at least \(8\) , then \(K_{2,4}\) is edge \(k\) -product cordial.
Proof. Let \(\rho\) be an element in \(U(\mathbb Z_k)\) of order \(m\ge 8\) . We define an edge labeling \(f\) for \(K_{2,4}\) as follows (Table 2 ).
| \(1\) | \(\rho\) | \(\rho^{-1}\) | \(\rho^{4}\) | \(\rho^{4}\) |
| \(\rho^{-2}\) | \(\rho^{2}\) | \(\rho^{3}\) | \(\rho^{-3}\) | \(1\) |
| \(\rho^{-2}\) | \(\rho^{3}\) | \(\rho^{2}\) | \(\rho\) | \(\mathbb{Z}_{k}\) |
Since \(m\ge 8\) , \(1, \rho\) , \(\rho^{-1}=\rho^{m-1}\) , \(\rho^4\) , \(\rho^{-2}=\rho^{m-2}\) , \(\rho^2\) , \(\rho^{-3}=\rho^{m-3}\) are distinct in \(U(\mathbb Z_k)\) . Similarly, \(\rho^{-2}\) , \(1\) , \(\rho\) , \(\rho^2\) , \(\rho^3\) , \(\rho^{4}\) are distinct in \(U(\mathbb Z_k)\) . Hence, \(f\) is an edge \(k\) -product cordial labeling for \(K_{2,4}\) . \(\square\)
Example 3.2. Let \(k=13\) . It is known that \(2\) is a primitive root modulo 13. Namely, \(2^2=4\) , \(2^3=8\) , \(2^4=3\) , \(2^5=6\) , \(2^6=12\) , \(2^7=11\) , \(2^8=9\) , \(2^9=5=2^{-3}\) , \(2^{10}=10=2^{-2}\) , \(2^{11}=7=2^{-1}\) , \(2^{12}=1\) in \(\mathbb Z_{13}\) . According to Table 2 , we have the following \(13\) -product cordial labeling for \(K_{2,4}\) . \[\begin{array}{|c|c|c|c|c} 1 & 2 & 7 & 3 & 3 \\ \hline 10 & 4 & 8 & 5 & 1 \\ \hline 10 & 8 & 4 & 2 & \mathbb{Z}_{13} \end{array}\]
Corollary 3.3. Suppose \(k=2^j\) , \(j\ge 4\) . \(K_{2,4}\) is edge \(k\) -product cordial.
Proof. For \(j=4\) , i.e., \(k=16\) , we have the following labeling. \[\begin{array}{|c|c|c|c|c} 3 & 13 & 1 & 15 & 9 \\ \hline 2 & 4 & 8 & 6 & 0 \\ \hline 6 & 4 & 8 & 10 & \mathbb{Z}_{16} \end{array}\]
Consider \(j\ge 5\) . Since \(U(\mathbb Z_{2^j})\cong \mathbb Z_2\times Z_{2^{j-2}}\) , there is an element \(\rho\in U(\mathbb Z_{2^j})\) of order \(8\) . By Lemma 3.1 , we have the corollary. \(\square\)
Example 3.4. Let \(k=32\) . Thus, \(\phi(32)=16\) and \(U(\mathbb Z_{32})\cong \mathfrak{C}_2\times \mathfrak{C}_8\) . \(3\) is an element in \(U(\mathbb Z_{32})\) of order 8. Namely, \(3^2=9\) , \(3^3=27\) , \(3^4=17\) , \(3^5=3^{-3}=19\) , \(3^6=3^{-2}=25\) , \(3^7=3^{-1}=11\) , \(3^8=1\) in \(\mathbb Z_{32}\) . According to Table 2 , we have the labeling
\[\begin{array}{|c|c|c|c|c} 1 & 3 & 11 & 17 & 17 \\ \hline 25 & 9 & 27 & 19 & 1 \\ \hline 25 & 27 & 9 & 13 & \mathbb{Z}_{32} \end{array}\]
Corollary 3.5. Let \(p\) be an odd prime. Suppose \(k=p^j\) or \(k=2p^j\) for \(j\ge 1\) . If \(k\ge 9\) , then \(K_{2,4}\) is edge \(k\) -product cordial.
Proof. Now, \(U(\mathbb Z_k)\) is a cyclic group of order \(\phi(k)=p^{j-1}(p-1)\) .
If \(p\ge 11\) , then \(\phi(k)\ge 10\) . By Lemma 3.1 , we have the result.
Suppose \(p=7\) . Since \(k\ge 9\) , \(k=7^j\) for \(j\ge 2\) or \(k=2\times 7^i\) for \(i\ge 1\) . If \(k=7^j\) with \(j\ge 2\) , then \(\phi(k)=7^{j-1}\times 6\) . We may choose \(\rho\) in \(U(\mathbb Z_k)\) of order \(14\) . If \(k=2\times 7^i\) with \(i\ge 2\) , then it is similar to the previous case. The remaining case is \(k=14\) . We shall consider this case later.
Suppose \(p=5\) . If \(k=5^j\) with \(j\ge 2\) , then \(\phi(k)=5^{j-1}\times 4\) . We may choose \(\rho\) in \(U(\mathbb Z_k)\) of order \(10\) . If \(k=2\times 5^i\) with \(i\ge 2\) , then it is similar to the previous case. The remaining case is \(k=10\) . We shall consider this case later.
Suppose \(p=3\) . Suppose \(k=3^j\) with \(j\ge 2\) . Then \(\phi(k)=3^{j-1}\times 2\ge 18\) if \(j\ge 3\) . We may choose \(\rho\) in \(U(\mathbb Z_k)\) of order \(18\) . The remaining case is \(k=9\) .
Suppose \(k=2\times 3^i\) with \(i\ge 1\) . Since \(k\ge 9\) , \(i\ge 2\) . If \(i\ge 3\) , then it is similar to the previous case. The remaining case is \(k=18\) .
Thus, the remaining cases are \(k=9, 10, 14, 18\) . For each \(k\) , we have the following labelings.
\[\begin{array}{|c|c|c|c|c} 2 & 4 & 1 & 8 & 1 \\ \hline 6 & 5 & 7 & 3 & 0 \\ \hline 3 & 2 & 7 & 6 & \mathbb{Z}_{9} \end{array} \qquad \begin{array}{|c|c|c|c|c} 3 & 7 & 1 & 9 & 9 \\ \hline 4 & 5 & 6 & 2 & 0 \\ \hline 2 & 5 & 6 & 8 & \mathbb{Z}_{10} \end{array} \qquad \begin{array}{|c|c|c|c|c} 3 & 9 & 1 & 13 & 1 \\ \hline 2 & 7 & 12 & 4 & 0 \\ \hline 6 & 7 & 12 & 10 & \mathbb{Z}_{14} \end{array} \qquad \begin{array}{|c|c|c|c|c} 5 & 13 & 1 & 17 & 7 \\ \hline 2 & 3 & 16 & 6 & 0 \\ \hline 10 & 3 & 16 & 12 & \mathbb{Z}_{18} \end{array}\]
Hence, we have the corollary. \(\square\)
Lemma 3.6. Suppose \(k\ge 12\) is a composite number, and \(k\) is neither \(p^j\) nor \(2p^j\) for some prime \(p\) and \(j\ge 1\) . \(K_{2,4}\) is edge \(k\) -product cordial.
Proof. Let \(k=ab\) with gcd \((a,b)=1\) . Suppose \(a=2\) . Since \(k=2b\) is neither \(p^j\) nor \(2p^j\) , \(b\) has at least two distinct odd prime factors, say \(p,q\) . Let \(i\) be the larger integer such that \(p^i\) is a factor of \(b\) . Rewrite \(k=(2p^i)(b/p^i)\) , then gcd \((2p^i, b/p^i)=1\) , \(2p^i\ge 3\) and \(b/p^i\) is odd.
So, now we may assume \(k=ab\) , gcd \((a,b)=1\) , \(a\ge 3\) and \(b\) is odd. Since \(\phi(a)\) and \(\phi(b)\) are even, \(|U(\mathbb Z_{ab})|=\phi(ab)=\phi(a)\phi(b)\) is a multiple of 4. Note that \(\{1, -1\}\subset U(\mathbb Z_{ab})\) .
Claim 1: Suppose \(\alpha\in U(\mathbb Z_{ab})\setminus\{1,-1\}\) , then \(\alpha\ne -\alpha\) .
If not, then we have \(2\alpha\equiv 0\pmod{ab}\) . Since gcd \((\alpha, ab)=1\) , we have \(2\equiv 0\pmod{ab}\) which is impossible.
Suppose \(|U(\mathbb Z_{ab})|\ge 8\) . We may choose \(\alpha, \beta, \gamma\in U(\mathbb Z_{ab})\) such that 1, \(-1\) , \(\alpha\) , \(-\alpha\) , \(\beta\) , \(-\beta\) , \(\gamma\) , \(-\gamma\) are distinct. Define \(f\) by Table 3
| \(1\) | \(-1\) | \(\alpha\) | \(-\alpha\) | \(\alpha^{2}\) |
| \(a\) | \(-b\) | \(\beta\) | \(-\gamma\) | \(0\) |
| \(a\) | \(b\) | \(\alpha\beta\) | \(\alpha\gamma\) | \(\mathbb{Z}_{ab}\) |
Since \(a,b\notin U(\mathbb Z_{ab})\) , gcd \((a,b)=1\) and \(\{1, -1, \alpha, -\alpha, \beta, -\gamma\}\subset U(\mathbb Z_{ab})\) , all edge labels are distinct. Since \(\alpha, \beta, \gamma\) are distinct elements in the group \(U(\mathbb Z_{ab})\) , \(\alpha^2, \alpha\beta, \alpha\gamma\) are distinct. Thus, all six vertex labels are distinct. Hence, \(f\) is an edge \(ab\) -product cordial labeling for \(K_{2,4}\) .
Suppose \(|U(\mathbb Z_{ab})|=4\) , then \(\phi(a)=\phi(b)=2\) . Since \(b\) is odd, \(b=3\) . Since gcd \((a,b)=1\) and \(\phi(a)=2\) , we have \(a=4\) . Thus \(k=12\) . Define \(f\) by \[\begin{array}{|c|c|c|c|c} 1 & 5 & 7 & 11 & 1 \\ \hline 2 & 3 & 4 & 6 & 0 \\ \hline 2 & 3 & 4 & 6 & \mathbb{Z}_{12} \end{array}\] Hence, \(f\) is an edge \(12\) -product cordial labeling for \(K_{2,4}\) .
\(\square\)
Remark 3.7. From the proof of Lemma 3.6 , we have checked that the edge labels (or the vertex labels) are distinct. In general, there are two kinds of labels, say \(U\) and \(N\) , where \(U\) is the list of labels in \(U(\mathbb Z_k)\) and \(N\) is the list of labels not in \(U(\mathbb Z_k)\) . Thus, it is suffice to show that each list contains distinct elements.
Example 3.8. Let \(k=35\) . Now \(U(\mathbb Z_{35})\cong U(\mathbb Z_{5})\times U(\mathbb Z_7)\cong \mathfrak C_4\times \mathfrak C_6\) . We use the following two methods to demonstrate the proof of Lemma 3.1 and the proof of Lemma 3.6 .
Method 1 : Since \(U(\mathbb Z_{35})\cong \mathfrak C_4\times \mathfrak C_6\) , there is an element in \(U(\mathbb Z_{35})\) whose order is lcm{4,6}=12. Actually, the order of \(2\) in \(U(\mathbb Z_{35})\) is 12. Namely \(2^2=4\) , \(2^3=8\) , \(2^4=16\) , \(2^9=22\) , \(2^{10}=9\) , \(2^{11}=18\) (all arithmetics are taken in \(\mathbb Z_{35}\) to label the edges of the graph \(K_{2,4}\) ). According to Table 2 , we have
\[\begin{array}{|c|c|c|c|c} 1 & 2 & 18 & 16 & 16 \\ \hline 9 & 4 & 8 & 22 & 1 \\ \hline 9 & 8 & 4 & 2 & \mathbb{Z}_{35} \end{array}\]
Method 2 : We may choose \(\alpha=2\) , \(\beta=3\) , \(\gamma=4\) . According to Table 3 we have
\[\begin{array}{|c|c|c|c|c} 1 & -1 & 2 & -2 & 4 \\ \hline 5 & -7 & 3 & -4 & 0 \\ \hline 5 & 7 & 6 & 8 & \mathbb{Z}_{35} \end{array} \;=\; \begin{array}{|c|c|c|c|c} 1 & 34 & 2 & 33 & 4 \\ \hline 5 & 28 & 3 & 31 & 0 \\ \hline 5 & 7 & 6 & 8 & \mathbb{Z}_{35} \end{array}\]
Theorem 3.9. \(K_{2,4}\) is edge \(k\) -product cordial if and only if \(k=5\) or \(k\ge 9\) .
Let us consider the graph \(K_{2,6}\) . We know that \(K_{2,6}\) is edge \(7\) -product cordial in the above section. So we consider the first case listed in Theorem 1.1 , i.e., \(k\ge 4n+1=13\) .
Lemma 4.1. If \(U(\mathbb Z_k)\) contains an element of order at least \(12\) , then \(K_{2,6}\) is edge \(k\) -product cordial.
Proof. Let \(\rho\) be an element in \(U(\mathbb Z_k)\) of order \(m\ge 12\) . We define an edge labeling \(f\) for \(K_{2,6}\) as follows. \[\begin{array}{|c|c|c|c|c|c|c} 1 & \rho^{-1} & \rho^{4} & \rho^{-4} & \rho^{5} & \rho^{-5} & \rho^{-1} \\ \hline \rho^{-2} & \rho & \rho^{-3} & \rho^{6} & \rho^{3} & \rho^{2} & \rho^{7} \\ \hline \rho^{-2} & 1 & \rho & \rho^{2} & \rho^{8} & \rho^{-3} & \mathbb{Z}_{k} \end{array}\]
The exponents of the twelve edge labels form the set of consecutive integers, \(\{-5,-4, \dots,\\ 6\}\) . Thus, they are distinct in \(U(\mathbb Z_k)\) .
Since \(m\ge 12\) , \(\rho^{-3}=\rho^{m-3}\) , \(\rho^{-2}=\rho^{m-2}\) , \(\rho^{-1}=\rho^{m-1}\) , \(1\) , \(\rho\) , \(\rho^2\) , \(\rho^7\) , \(\rho^8\) are distinct. Thus, \(f\) is an edge \(k\) -product cordial labeling for \(K_{2,6}\) . \(\square\)
Corollary 4.2. Suppose \(k=2^j\) , \(j\ge 4\) . \(K_{2,6}\) is edge \(k\) -product cordial.
Proof. Consider \(j=4,5\) , i.e., \(k=16\) and 32. We have the following labelings, respectively. \[\begin{array}{|c|c|c|c|c|c|c} 1 & 3 & 9 & 11 & 7 & 15 & 1 \\ \hline 2 & 4 & 6 & 8 & 13 & 12 & 0 \\ \hline 2 & 12 & 6 & 8 & 11 & 4 & \mathbb{Z}_{16} \end{array} \qquad \begin{array}{|c|c|c|c|c|c|c} 1 & 17 & 3 & 25 & 19 & 11 & 11 \\ \hline 27 & 9 & 2 & 4 & 6 & 8 & 0 \\ \hline 27 & 25 & 6 & 4 & 18 & 24 & \mathbb{Z}_{32} \end{array}\]
Consider \(j\ge 6\) . Since \(U(\mathbb Z_{2^j})\cong \mathbb Z_2\times Z_{2^{j-2}}\) , there is an element \(\rho\in U(\mathbb Z_{2^j})\) of order \(16\) . By Lemma 4.1 , we have the corollary. \(\square\)
Corollary 4.3. Let \(p\) be an odd prime. Suppose \(k=p^j\) or \(k=2p^j\) for \(j\ge 1\) . If \(k\ge 13\) , then \(K_{2,6}\) is edge \(k\) -product cordial.
Proof. Now, \(U(\mathbb Z_k)\) is a cyclic group of order \(\phi(k)=p^{j-1}(p-1)\) . If \(U(\mathbb Z_k)\) contains an element of order \(m\ge 12\) , then by Lemma 4.1 , we have an edge \(k\) -product labeling.
Thus, we only need to deal with those \(k\) such that \(\phi(k)\le 11\) , i.e., \(p^{j-1}(p-1)\le 11\) . Since \(\phi(k)\) is even, first we need to find out the values of \(p\) such that \(p^{j-1}(p-1)\le 10\) .
Suppose \(j=1\) , then \(p-1\le 10\) implies that \(p=3, 5, 7, 11\) . Since \(k\ge 13\) , we have \(k=14, 22\) .
Suppose \(j\ge 2\) . We have \(3(p-1)\le p^{j-1}(p-1)\le 10\) and \(2p^{j-1}\le p^{j-1}(p-1)\le 10\) . The only solution is \(p=3\) and \(j=2\) . Hence \(k=18\) . Tables below define an edge \(k\) -product cordial labeling for \(K_{2,6}\) , where \(k=14, 18, 22\) , respectively. \[\begin{gathered} \begin{array}{|c|c|c|c|c|c|c} 1 & 3 & 5 & 9 & 11 & 13 & 13 \\ \hline 2 & 4 & 7 & 10 & 8 & 6 & 0 \\ \hline 2 & 12 & 7 & 6 & 4 & 8 & \mathbb{Z}_{14} \end{array} \qquad \begin{array}{|c|c|c|c|c|c|c} 1 & 5 & 7 & 11 & 13 & 17 & 17 \\ \hline 2 & 3 & 4 & 6 & 8 & 9 & 0 \\ \hline 2 & 15 & 10 & 12 & 14 & 9 & \mathbb{Z}_{18} \end{array} \\[1.2em] \begin{array}{|c|c|c|c|c|c|c} 1 & 3 & 5 & 7 & 9 & 13 & 9 \\ \hline 2 & 4 & 21 & 19 & 17 & 11 & 0 \\ \hline 2 & 12 & 17 & 1 & 21 & 11 & \mathbb{Z}_{22} \end{array} \end{gathered}\] \(\square\)
Lemma 4.4. Let \(k=2^{r} 3^{s} 5^{t}7^{q}\) , where \(r,s,t,q\ge 0\) . If every element in \(U(\mathbb Z_k)\) is of order at most \(9\) , then the followings hold.
\(q\) and \(t\) are not both positive;
if \(t=1\) , then \(s=0,1\) ;
\(0\le q\le 1\) , \(0\le t\le 1\) , \(0\le s\le 2\) and \(0\le r\le 5\) .
Proof. First we know that \[U(\mathbb Z_k)\cong U(\mathbb Z_{2^r})\times (\mathfrak C_{2\times 3^{s-1}})\times (\mathfrak C_{4\times 5^{t-1}})\times (\mathfrak C_{6\times 7^{q-1}}).\] Note that, if the exponent of the prime is zero, then the corresponding subgroup does not appear in the above formula. If \(q\ge 1\) and \(t\ge 1\) , then \(U(\mathbb Z_k)\) contains an element with order at least lcm \(\{4,6\}=12\) . We have (a).
If \(t=1\) and \(s\ge 2\) , then \(U(\mathbb Z_k)\) contains an element with order lcm \(\{4,6\}=12\) . We have (b).
If \(q\ge 2\) , then \(U(\mathbb Z_k)\) contains an element of order at least 42.
If \(t\ge 2\) , then \(U(\mathbb Z_k)\) contains an element of order 20.
If \(s\ge 3\) , then \(U(\mathbb Z_k)\) contains an element of order 18.
If \(r\ge 6\) , then \(U(\mathbb Z_k)\) contains an element of order 16.
So we have (c). \(\square\)
Theorem 4.5. Suppose \(k\ge 13\) is a composite number, and \(k\) is neither \(p^j\) nor \(2p^j\) for some prime \(p\) and \(j\ge 1\) . \(K_{2,6}\) is edge \(k\) -product cordial.
Proof. Similar to the proof of Lemma 3.6 , we may let \(k=ab\) , where gcd \((a,b)=1\) , \(a\ge 3\) and \(b\ge 3\) . Moreover the order of \(U(\mathbb Z_k)\) is a 4 multiple.
Suppose \(\rho\) is an element in \(U(\mathbb Z_k)\) of order \(m\ge 10\) . We define an edge labeling \(f\) as follows. \[\begin{array}{|c|c|c|c|c|c|c} 1 & \rho & \rho^{-1} & \rho^{2} & \rho^{-2} & \rho^{5} & \rho^{5} \\ \hline a & \rho^{3} & \rho^{4} & \rho^{-3} & b & \rho^{-4} & 0 \\ \hline a & \rho^{4} & \rho^{3} & \rho^{-1} & b\rho^{-2} & \rho & \mathbb{Z}_{ab} \end{array}\]
The exponents of the ten edge labels in the above table, which are in \(U(\mathbb Z_k)\) , form the set of consecutive integers, \(\{-4,-3, \dots, 5\}\) . So they are distinct. Clearly, \(a ,b\) are distinct. Hence, all edge labels are distinct. Similarly, \(\rho, \rho^{-1}=\rho^{m-1}, \rho^3, \rho^4, \rho^5\) are distinct elements in \(U(\mathbb Z_k)\) . Also \(0, a, b\rho^{-2}\) are distinct elements not in \(U(\mathbb Z_k)\) . If not, suppose \(b\rho^{-2}\equiv a \pmod{ab}\) (or \(b\rho^{-2} \equiv 0\pmod{ab}\) , resp.). Thus, \(b^2\rho^{-2}\equiv ab\equiv 0\pmod{ab}\) (or \(b \equiv0\pmod{ab}\) ), respectively). This implies \(b^2\equiv 0\pmod{ab}\) (or \(b\equiv 0\pmod{ab}\) , respectively) which is impossible. Thus, all vertex labels are distinct. Hence \(f\) is an edge \(k\) -product cordial labeling for \(K_{2,6}\) .
Thus, we assume that every element in the group \(U(\mathbb Z_k)\) is of order at most 9. If \(k\) has a prime factor \(p\) with \(p\ge 11\) , then \(U(\mathbb Z_k)\) contains an element of order at least 10. Therefore, we only need to consider \(k=2^{r} 3^{s} 5^{t}7^{q}\) , where \(r,s,t,q\ge 0\) . By Lemma 3.7 , we have \(0\le q\le 1\) , \(0\le t\le 1\) , \(0\le s\le 2\) and \(0\le r\le 5\) . For easy discussion, let us consider \(k\) being odd or even.
Suppose \(k\) is odd. If \(s=0\) , then under the assumption, it is not a case. So \(s=1,2\) . Suppose \(s=2\) . By Lemma 3.7 , \(k=3^2\times 7=63\) only. Suppose \(s=1\) , then \(k=15, 21\) .
Suppose \(k\) is even. If \(r=1\) , then under the assumption, at least two of \(s,t,q\) are positive. However, \(t\) and \(q\) cannot be both positive. Thus, \(k=30, 42, 126\) .
If \(5\ge r\ge2\) , then \(U(\mathbb Z_{2^r})\cong \mathfrak C_2\times \mathfrak C_{2^{r-2}}\) . Under the assumption, at least one of \(s,t,q\) is positive. But \((q,t)=(1,1)\) and \((s,t)=(2,1)\) are excluded.
Suppose \(r=4,5\) . If \(q=1\) or \(s=2\) , then \(\mathfrak C_{2^{r-2}}\times \mathfrak C_{6}\) contains an element of order 12. Thus, we may assume \(q=0\) and \(s=0,1\) . If \(t=0\) , then under the assumption \(k=48, 96\) . If \(t=1\) , then \(k=80, 160, 240, 480\) .
Suppose \(r=3\) . Then \(k=56, 168, 504, 40, 120, 24, 72\) .
Suppose \(r=2\) . Then \(k=28, 84, 252, 20, 60, 12\ \mbox{(not a case)}, 36\) .
Let us summarize the above cases.
Case 1. \(k=\) 21, 28, 36, 42, 56, 63, 72, 84, 126, 168, 252, 504.
Case 2. \(k=\) 80, 160, 240, 480.
Case 3. \(k=40, 48, 60, 96, 120\) .
Case 4. \(k=\) 15, 20, 24, 30.
For Case 1, one may check that \(U(\mathbb Z_k)\) contains a subgroup isomorphic to \(\mathfrak C_2\times \mathfrak C_6\) . Without loss of generality, we may let the generators of this subgroup be \(-1\) and \(\alpha\) , where the order of \(\alpha\) is 6. That is, \(C_2\times \mathfrak C_6=\{\pm \alpha^i\;|\; 0\le i\le 5\}\) . We define an edge labeling \(f\) as follows. \[\begin{array}{|c|c|c|c|c|c|c} 1 & -1 & \alpha & -\alpha & \alpha^{3} & -\alpha^{3} & -\alpha^{2} \\ \hline \alpha^{4} & \alpha^{5} & -\alpha^{2} & -\alpha^{5} & \alpha^{2} & -\alpha^{4} & -\alpha^{4} \\ \hline \alpha^{4} & -\alpha^{5} & -\alpha^{3} & 1 & \alpha^{5} & \alpha & \mathbb{Z}_{k} \end{array}\]
Clearly, all edge labels are distinct and all vertex labels are also distinct.
For Case 2, one may check that \(U(\mathbb Z_k)\) contains a subgroup isomorphic to \(\mathfrak C_4\times \mathfrak C_4\) . Without loss of generality, we may let the generators of this subgroup be \(\beta\) and \(\gamma\) , where the order of \(\beta\) and \(\gamma\) are 4. That is, \(\mathfrak C_4\times \mathfrak C_4=\{\beta^i\gamma^j\;|\; 0\le i,j\le 3\}\) . We define an edge labeling \(f\) as follows. \[\begin{array}{|c|c|c|c|c|c|c} \beta^{2}\gamma & \gamma & \gamma^{2} & \beta & \beta\gamma & \beta\gamma^{2} & \beta\gamma^{3} \\ \hline 1 & \beta^{3} & \beta^{2} & \beta^{2}\gamma^{3} & \beta^{3}\gamma & \beta^{3}\gamma^{2} & \beta\gamma^{2} \\ \hline \beta^{2}\gamma & \beta^{3}\gamma & \beta^{2}\gamma^{2} & \beta^{3}\gamma^{3} & \gamma^{2} & 1 & \mathbb{Z}_{k} \end{array}\]
Clearly, all edge labels are distinct and all vertex labels are also distinct.
For Case 3, \(U(\mathbb Z_k)\) contains a subgroup isomorphic to \(\mathfrak C_2\times\mathfrak C_2\times \mathfrak C_4\) . Without loss of generality, we may let this subgroup be \(\{\pm \delta^i\epsilon^j\;|\; 0\le i\le 1, 0\le j\le 3\}\) , where the order of \(\delta\) is 2 and the order of \(\epsilon\) is 4. We define an edge labeling \(f\) as follows. \[\begin{array}{|c|c|c|c|c|c|c} 1 & -1 & \epsilon & \epsilon^{3} & -\epsilon & -\epsilon^{3} & -1 \\ \hline \delta\epsilon^{3} & \delta\epsilon & \epsilon^{2} & -\epsilon^{2} & -\delta & \delta & 1 \\ \hline \delta\epsilon^{3} & -\delta\epsilon & \epsilon^{3} & -\epsilon & \delta\epsilon & -\delta\epsilon^{3} & \mathbb{Z}_{k} \end{array}\]
For Case 4, we have \[\begin{gathered} \begin{array}{|c|c|c|c|c|c|c} 1 & 2 & 4 & 7 & 8 & 11 & 8 \\ \hline 14 & 13 & 9 & 6 & 3 & 5 & 0 \\ \hline 14 & 11 & 6 & 12 & 9 & 10 & \mathbb{Z}_{15} \end{array} \qquad \begin{array}{|c|c|c|c|c|c|c} 1 & 3 & 7 & 9 & 11 & 13 & 7 \\ \hline 19 & 17 & 6 & 2 & 4 & 5 & 0 \\ \hline 19 & 11 & 2 & 18 & 4 & 5 & \mathbb{Z}_{20} \end{array} \\[1.2em] \begin{array}{|c|c|c|c|c|c|c} 1 & 5 & 7 & 17 & 19 & 23 & 23 \\ \hline 8 & 3 & 6 & 10 & 16 & 21 & 0 \\ \hline 8 & 15 & 18 & 2 & 16 & 3 & \mathbb{Z}_{24} \end{array} \qquad \begin{array}{|c|c|c|c|c|c|c} 1 & 7 & 11 & 13 & 17 & 19 & 13 \\ \hline 2 & 23 & 29 & 3 & 4 & 5 & 0 \\ \hline 2 & 11 & 19 & 9 & 8 & 5 & \mathbb{Z}_{30} \end{array} \end{gathered}\]
Hence we have the theorem. \(\square\)
Combining all results in this section and Theorem 1.1 , we have
Theorem 4.6. \(K_{2,6}\) is edge \(k\) -product cordial if and only if \(k=7\) or \(k\ge 13\) .
From the above proof, in order to find an edge \(k\) -product cordial labeling for \(K_{2,2n}\) with \(k\ge 4n+1\) , it is sufficient to choose \(4n\) distinct nonzero residues and obtain \(2n + 2\) distinct row and column products.
If the order of \(U(\mathbb Z_k)\) is at least \(2n\) , then we can fill \(2n\) elements of \(U(\mathbb Z_k)\) in the first row. Now, the first row product is an element in \(U(\mathbb Z_k)\) . Next, we arrange another \(2n\) elements in the second row such that all column products are distinct nonzero elements (see Lemma 3.1 ). If we can do that, then it is easy to swap some pairs of elements within the same column such that all the products are distinct. If \(k\) is not a prime, then we choose other \(2n\) elements for the second row such that the product of these elements is zero (see the proof of Theorem 4.5 ).
However, it would be more difficult when the order of \(U(\mathbb Z_k)\) is less than \(2n\) . Let us show an example. Suppose \(n=4\) and \(k=18>4n+1\) . Then \(U(\mathbb Z_{18})=\{1,5,7,11,13,17\}\) . We have \[\begin{array}{|c|c|c|c|c|c|c|c|c} 1 & 5 & 7 & 17 & 13 & 11 & 8 & 4 & 4 \\ \hline 2 & 14 & 9 & 10 & 16 & 15 & 3 & 12 & 0 \\ \hline 2 & 16 & 9 & 8 & 10 & 3 & 6 & 12 & \mathbb{Z}_{18} \end{array}\]
Hence, we have an edge \(18\) -product cordial labeling for \(K_{2,8}\) .
Finally, we propose the following conjecture.
Conjecture 5.1. For \(n\ge 4\) , \(K_{2,2n}\) is edge \(k\) -product cordial if and only if \(k=2n+1\) is a prime or \(k\ge 4n+1\) .