This paper investigates the existence of pair mean cordial (PMC) labelings for several classes of graphs, namely, \(m\) copies of paths, \(m\) copies of cycles, spider graphs, generalized theta graphs, Tunjung graphs, and volcano graphs.
In this study, we focus exclusively on graphs that are finite, simple, and undirected. Graph theory originated in 1736, when Leonhard Euler solved the famous Seven Bridges of Königsberg problem by representing physical landmasses and bridges as networks of vertices and edges. By the late 1960s, the field had expanded to include graph labeling, introduced by mathematicians such as Alex Rosa [1], which involves assigning numerical values to the vertices and edges of a graph according to specific mathematical rules. While early labeling methods, such as graceful labeling, proved valuable for practical applications including radar design and network addressing, their strict mathematical requirements limited their applicability to many complex graph structures. Among the various types of graph labeling, cordial labeling and its variants have attracted considerable attention because of their simple definitions and rich structural properties.
To overcome some of these limitations, I. Cahit introduced cordial labeling in 1987. This concept simplified the labeling process by using a binary system consisting of \(0\) and \(1\) and requiring a balanced distribution in which the numbers of the two labels differ by at most one. In recent years, this concept has evolved into pair mean cordial labeling (PMC-labeling), a variation that combines Cahit’s balanced binary condition with specific mean-based rules for determining edge labels. Determining which graph families admit a PMC-labeling remains an active area of research and provides useful mathematical frameworks for the study of graph structures and related applications. The concept of mean labeling was initially introduced by S. Somasundaram and R. Ponraj [2]. Various forms of graph labeling have been investigated in [3–11]. Pair mean cordial labeling is one such variation that extends the concept of cordial labeling by incorporating mean-based edge assignments. It has been shown in [12–16] that paths, cycles, stars, and several families of trees admit pair mean cordial labelings under suitable conditions.
Terminology and notation not explicitly defined in this paper are taken from Harary [17] and Gallian [18]. The study of pair mean cordial labeling is motivated by its significance in both mathematical theory and practical applications. From a theoretical perspective, PMC-labeling helps researchers understand how the structure of a graph can accommodate balanced numerical patterns based on the mean values associated with adjacent vertices. By studying these patterns, mathematicians can classify different graph families and develop general methods for analyzing their structural properties. From an applied perspective, the balanced nature of PMC-labeling may be useful in optimization problems arising in technology and engineering. It provides a framework for applications such as communication network design, wireless channel assignment, radar signal design, and the modeling of molecular structures in chemistry.
In this paper, we investigate the PMC-labeling properties of several classes of graphs, including \(m\) copies of paths, \(m\) copies of cycles, spider graphs, generalized theta graphs, Tunjung graphs, and volcano graphs. We prove that these graph classes admit pair mean cordial labelings under the required conditions.
The following definitions are required for the upcoming section.
Definition 1. [18] The spider graph \(Sp_{n,m}\), is a graph with the vertex set \(V(Sp_{n,m})=\{v_{0},v_{i,j} \mid 1\leq i \leq n\, \&\, 1\leq j \leq m\}\) and the edge set \(E(Sp_{n,m})=\{ v_{i,j}v_{i+1,j}, v_{0}v_{1,j} \mid 1\leq i \leq n-1\, \&\,1\leq j \leq m \}\).
Definition 2. [5] The generalized theta graph \(\theta_{n,m}\) is a graph consisting of \(m\geq 2\) internal disjoint paths of length \(n\) with the same end points \(u_{0}\) & \(v_{0}\).
Definition 3. [6] The tunjung graph \(TJ_{n}\), \(n\geq 3\) is a helm graph \(H_{n}\) by adjoining a new pendent \(w_{i}\) at the pendent vertex \(v_{i}\) of \(H_{n}\), adding an edge \(v_{i}v_{i+1}\) where \(v_{n+1}=v_{1}\) and connecting \(v_{i}\) and \(w_{i}\) to central vertex \(v_{0}\) for \(i=1,2,\dots,n\).
The tunjung graph \(TJ_{4}\) is shown in Figure 1.
Definition 4. [4] The volcano graph \(V_{n}\), \(n\geq 3\) is a graph with the vertex set \(V(V_{n})=\{u_{1},u_{2},u_{3},v_{i} \mid 1\leq i \leq n\}\) and the edge set \(E(V_{n})=\{ u_{1}u_{2},u_{2}u_{3},u_{3}u_{1},u_{1}v_{i}\mid 1\leq i \leq n\}\).
Definition 5. [12] Let \(G=(V,E)\) be a \((p,q)\) graph. Define \[\begin{aligned} \rho =\left\{ \begin{array}{ccc} \frac {p} {2}&p\ \text{is even}, \\ \frac {p-1}{2} &p\ \text{is odd,}\end{array}\right. \end{aligned}\] and \(M=\{\pm 1,\pm 2,\dots \pm \rho\}\) called the set of labels. Consider a mapping \(\Lambda: V\rightarrow M\) by assigning different labels in \(M\) to the different elements of \(V\) when \(p\) is even and different labels in \(M\) to \(p-1\) elements of \(V\) and repeating a label for the remaining one vertex when \(p\) is odd. The labeling as defined above is said to be a pair mean cordial labeling (PMC-Labeling) if for each edge \(uv\) of \(G\), there exists a labeling \(\frac{\Lambda(u)+\Lambda(v)}{2}\) if \(\Lambda(u)+\Lambda(v)\) is even and \(\frac{\Lambda(u)+\Lambda(v)+1}{2}\)if \(\Lambda(u)+\Lambda(v)\) is odd such that \(|\bar {\mathbb{S}}_{\Lambda_{1}}-\bar{\mathbb{S}}_{\Lambda_{1}^{c}}|\leq 1\) where \(\bar{\mathbb{S}}_{\Lambda_{1}}\) and \(\bar{\mathbb{S}}_{\Lambda_{1}^{c}}\) respectively denote the number of edges labeled with 1 and the number of edges not labeled with 1. A graph \(G\) for which there exists a pair mean cordial labeling is called a pair mean cordial graph (PMC-Graph).
In this section, we prove that several classes of graphs, including \(m\) copies of paths, \(m\) copies of cycles, spider graphs, generalized theta graphs, Tunjung graphs, and volcano graphs, admit pair mean cordial labelings under the required conditions.
Theorem 1. For all integers \(m,n\geq 1\), the graph \(mP_n\), consisting of \(m\) copies of the path \(P_n\), is a PMC-graph.
Proof. Let \[V(mP_n) = \{v_{i,j}\mid 1\leq i\leq n,\; 1\leq j\leq m\}\] and \[E(mP_n) = \{v_{i,j}v_{i+1,j}\mid 1\leq i\leq n-1,\; 1\leq j\leq m\}\] denote the vertex set and edge set, respectively, of \(mP_n\). Therefore, \[|V(mP_n)|=mn \qquad\text{and}\qquad |E(mP_n)|=m(n-1).\]
We prove the result by considering the following cases.
Case 1. \(n=1\).
In this case, \[mP_1\cong \overline{K_m}.\] Since \(\overline{K_m}\) is a PMC-graph by [12], the result follows.
Case 2. \(n=2\).
Define \[\Lambda:V(mP_n) \longrightarrow \left\{ \pm1,\pm2,\ldots,\pm\frac{mn}{2} \right\}.\]
Subcase 2.1. \(m\) is odd.
Define \[\Lambda(v_{i,j}) = \begin{cases} -j, & i=1,\quad 1\leq j\leq m,\\[4pt] j+1, & i=2,\quad 1\leq j\leq \dfrac{m-1}{2},\\[6pt] 1, & i=2,\quad j=\dfrac{m+1}{2},\\[6pt] j, & i=2,\quad \dfrac{m+3}{2}\leq j\leq m. \end{cases}\]
Hence, \[\bar{\mathbb{S}}_{\Lambda_1^{c}} = \frac{(n-1)m+1}{2}\] and \[\bar{\mathbb{S}}_{\Lambda_1} = \frac{(n-1)m-1}{2}.\] Therefore, \[\left| \bar{\mathbb{S}}_{\Lambda_1^{c}} – \bar{\mathbb{S}}_{\Lambda_1} \right| =1.\]
Subcase 2.2. \(m\) is even.
Define \[\Lambda(v_{i,j}) = \begin{cases} -j, & i=1,\quad 1\leq j\leq m,\\[4pt] j+1, & i=2,\quad 1\leq j\leq \dfrac{m}{2},\\[6pt] 1, & i=2,\quad j=\dfrac{m+2}{2},\\[6pt] j, & i=2,\quad \dfrac{m+4}{2}\leq j\leq m. \end{cases}\]
Thus, \[\bar{\mathbb{S}}_{\Lambda_1^{c}} = \frac{(n-1)m}{2} = \bar{\mathbb{S}}_{\Lambda_1}.\]
Case 3. \(n=3\).
Subcase 3.1. \(m\) is odd.
Define \[\Lambda:V(mP_n) \longrightarrow \left\{ \pm1,\pm2,\ldots,\pm\frac{mn-1}{2} \right\}.\]
For \(i=1\), define \[\Lambda(v_{1,j}) = \begin{cases} \dfrac{3j-1}{2}, & 1\leq j\leq m,\quad j\text{ is odd},\\[6pt] \dfrac{3j}{2}, & 1\leq j\leq m,\quad j\text{ is even}. \end{cases}\]
For \(i=2\), define \[\Lambda(v_{2,j}) = \begin{cases} \dfrac{3j+1}{2}, & 1\leq j\leq m-1,\quad j\text{ is odd},\\[6pt] \dfrac{-3j-1}{2}, & 1\leq j\leq m-1,\quad j\text{ is even},\\[6pt] \dfrac{-3m+3}{2}, & j=m. \end{cases}\]
For \(i=3\), define \[\Lambda(v_{3,j}) = \begin{cases} \dfrac{-3j+1}{2}, & 1\leq j\leq m,\quad j\text{ is odd},\\[6pt] \dfrac{-3j}{2}, & 1\leq j\leq m,\quad j\text{ is even}. \end{cases}\]
Therefore, \[\bar{\mathbb{S}}_{\Lambda_1^{c}} = \frac{(n-1)m}{2} = \bar{\mathbb{S}}_{\Lambda_1}.\]
Subcase 3.2. \(m\) is even.
Set \[\Lambda(v_{2,m}) = \frac{-3m-1}{2}.\] Label the remaining vertices \(v_{i,j}\), where \(i=1,2,3\) and \(1\leq j\leq m\), in the same manner as in Subcase 3.1.
Hence, \[\bar{\mathbb{S}}_{\Lambda_1^{c}} = \frac{(n-1)m+1}{2}\] and \[\bar{\mathbb{S}}_{\Lambda_1} = \frac{(n-1)m-1}{2}.\] Thus, \[\left| \bar{\mathbb{S}}_{\Lambda_1^{c}} – \bar{\mathbb{S}}_{\Lambda_1} \right| =1.\]
Case 4. \(n\geq 4\).
We consider two subcases according to the parity of \(n\).
Subcase 4.1. \(n\) is even.
Define \[\Lambda:V(mP_n) \longrightarrow \left\{ \pm1,\pm2,\ldots,\pm\frac{mn}{2} \right\}.\]
(a) \(m\) is even.
For odd \(j\), define \[\Lambda(v_{i,j}) = \begin{cases} \dfrac{(j-1)n+i+3}{2}, & 1\leq i\leq n,\quad i\text{ and }j\text{ are odd},\\[8pt] \dfrac{(-j+1)n-i}{2}, & 1\leq i\leq n,\quad i\text{ is even and }j\text{ is odd}. \end{cases}\]
For even \(j\), define \[\Lambda(v_{i,j}) = \begin{cases} \dfrac{(-j+1)n-2i}{2}, & 1\leq i\leq \dfrac{n}{2},\\[8pt] \dfrac{(j+1)n-2i+2}{2}, & i=\dfrac{n+2}{2},\dfrac{n+4}{2},\ldots,n-1,\\[8pt] \dfrac{jn+2}{2}, & i=n,\quad 1\leq j\leq m-1,\quad j\text{ is even},\\[6pt] 1, & i=n,\quad j=m. \end{cases}\]
(b) \(m\) is odd.
Label the vertices \[v_{i,j}, \qquad 1\leq i\leq n,\quad 1\leq j\leq m-1,\] in the same manner as in part (a) of Subcase 4.1.
For the vertices corresponding to \(j=m\), define \[\Lambda(v_{i,m}) = \begin{cases} \dfrac{(-m+1)n-i-1}{2}, & 1\leq i\leq n-1,\quad i\text{ is odd},\\[8pt] \dfrac{(m-1)n+2i}{2}, & 1\leq i\leq n-1,\quad i\text{ is even},\\[8pt] 1, & i=n. \end{cases}\]
Subcase 4.2. \(n\) is odd.
(a) \(m\) is even.
Label the vertices \(v_{i,j}\) with \[1\leq i\leq n, \qquad 1\leq j\leq m-1, \qquad j\text{ odd},\] in the same manner as in part (a) of Subcase 4.1.
For even \(j\), define \[\Lambda(v_{i,j}) = \begin{cases} \dfrac{(-j+1)n-i}{2}, & i=1,2,\ldots,\dfrac{n+1}{2},\\[8pt] \dfrac{(j+1)n-2i+3}{2}, & i=\dfrac{n+3}{2}, \dfrac{n+5}{2}, \ldots,n-1,\\[8pt] \dfrac{jn+2}{2}, & i=n,\quad 1\leq j\leq m-1,\quad j\text{ is even},\\[6pt] 1, & i=n,\quad j=m. \end{cases}\]
(b) \(m\) is odd.
Set \[\Lambda(v_{n-1,m})=1.\] Label the remaining vertices \(v_{i,j}\), \(1\leq i\leq n\) and \(1\leq j\leq m\), in the same manner as in part (a) of Subcase 4.2.
The numbers of edges belonging to the two induced edge-label classes for \(n\geq 4\) are summarized in Table 1.
As shown in Table 1, in every case the numbers of edges in the two induced edge-label classes are either equal or differ by exactly one. Hence, \[\left| \bar{\mathbb{S}}_{\Lambda_1^{c}} – \bar{\mathbb{S}}_{\Lambda_1} \right| \leq 1.\] Therefore, \(\Lambda\) satisfies the pair mean cordial condition. Consequently, \(mP_n\) is a PMC-graph for all \(m,n\geq 1\). \(\square\)
| Parity conditions | \(\bar{\mathbb{S}}_{\Lambda_1^{c}}\) | \(\bar{\mathbb{S}}_{\Lambda_1}\) |
|---|---|---|
| \(n\) and \(m\) are even | \(\dfrac{(n-1)m}{2}\) | \(\dfrac{(n-1)m}{2}\) |
| \(n\) is even and \(m\) is odd | \(\dfrac{(n-1)m+1}{2}\) | \(\dfrac{(n-1)m-1}{2}\) |
| \(n\) is odd and \(m\) is even | \(\dfrac{(n-1)m}{2}\) | \(\dfrac{(n-1)m}{2}\) |
| \(n\) and \(m\) are odd | \(\dfrac{(n-1)m}{2}\) | \(\dfrac{(n-1)m}{2}\) |
Theorem 2. For all integers \(n\geq 4\) and \(m\geq 1\), the graph \(mC_n\), consisting of \(m\) copies of the cycle \(C_n\), is a PMC-graph.
Proof. Let \[V(mC_n) = \{v_{i,j}\mid 1\leq i\leq n,\; 1\leq j\leq m\}\] and \[E(mC_n) = \{v_{i,j}v_{i+1,j},\,v_{n,j}v_{1,j} \mid 1\leq i\leq n-1,\;1\leq j\leq m\}\] denote, respectively, the vertex set and edge set of \(mC_n\). Thus, \[|V(mC_n)|=mn \qquad\text{and}\qquad |E(mC_n)|=mn.\]
We establish the result by considering the following cases. Although the theorem concerns \(n\geq 4\), we first record the case \(n=3\) for completeness.
Case 1. \(n=3\).
Subcase 1.1. \(m\equiv 0,3\pmod 4\).
Define the labeling \(\Lambda\) as follows: \[\Lambda(v_{i,j}) = \begin{cases} \dfrac{(j-1)n+i+1}{2}, & i=1,3,\quad j=1,3,\ldots, \left\lfloor\dfrac{3m+3}{4}\right\rfloor,\\[8pt] \dfrac{(-j+1)n-i}{2}, & i=2,\quad j=1,3,\ldots, \left\lfloor\dfrac{3m+3}{4}\right\rfloor. \end{cases}\]
For \[j=\left\lfloor\dfrac{3m+7}{4}\right\rfloor,\] define \[\Lambda(v_{i,j}) = \begin{cases} \dfrac{(-j+1)n-2i+1}{2}, & i=1,2,\\[8pt] 1, & i=3. \end{cases}\]
For even \(j\) satisfying \[\left\lfloor\dfrac{3m+11}{4}\right\rfloor \leq j\leq m,\] define \[\Lambda(v_{i,j}) = \begin{cases} \dfrac{(-j+1)n-i-1}{2}, & i=1,3,\\[8pt] \dfrac{(j-1)n-i}{2}, & i=2. \end{cases}\]
For odd \(j\) satisfying \[\left\lfloor\dfrac{3m+11}{4}\right\rfloor \leq j\leq m,\] define \[\Lambda(v_{i,j}) = \begin{cases} \dfrac{(j-1)n+i}{2}, & i=1,3,\\[8pt] \dfrac{(-j+1)n-i-1}{2}, & i=2. \end{cases}\]
Subcase 1.2. \(m\equiv 1,2\pmod 4\).
Define \[\Lambda(v_{i,j}) = \begin{cases} \dfrac{(j-1)n+i+1}{2}, & i=1,3,\quad j=1,3,\ldots, \left\lfloor\dfrac{3m-2}{4}\right\rfloor,\\[8pt] \dfrac{(-j+1)n-i}{2}, & i=2,\quad j=1,3,\ldots, \left\lfloor\dfrac{3m+2}{4}\right\rfloor,\\[8pt] \dfrac{(-j+1)n-i-1}{2}, & i=3,\quad j=\left\lfloor\dfrac{3m+2}{4}\right\rfloor. \end{cases}\]
For odd \(j\) satisfying \[\left\lfloor\dfrac{3m+6}{4}\right\rfloor \leq j\leq m,\] define \[\Lambda(v_{i,j}) = \begin{cases} \dfrac{(-j+1)n-i-2}{2}, & i=1,3,\\[8pt] \dfrac{(j-1)n+i+1}{2}, & i=2. \end{cases}\]
For even \(j\) satisfying \[\left\lfloor\dfrac{3m+6}{4}\right\rfloor \leq j\leq m,\] define \[\Lambda(v_{i,j}) = \begin{cases} \dfrac{(j-1)n+i+1}{2}, & i=1,3,\\[8pt] \dfrac{(-j+1)n-i-2}{2}, & i=2,\quad j\leq m-1,\\[8pt] 1, & i=2,\quad j=m. \end{cases}\]
Consequently, when \(m\) is odd, \[\bar{\mathbb{S}}_{\Lambda_1^{c}} = \frac{nm+1}{2}, \qquad \bar{\mathbb{S}}_{\Lambda_1} = \frac{nm-1}{2},\] whereas, when \(m\) is even, \[\bar{\mathbb{S}}_{\Lambda_1^{c}} = \frac{nm}{2} = \bar{\mathbb{S}}_{\Lambda_1}.\]
Case 2. \(n=4\).
Define \[\Lambda:V(mC_n) \longrightarrow \left\{ \pm1,\pm2,\ldots,\pm\frac{mn}{2} \right\}.\]
Subcase 2.1. \(m\) is even.
For odd \(j\), define \[\Lambda(v_{i,j}) = \begin{cases} \dfrac{(j-1)n+i+3}{2}, & i=1,3,\quad 1\leq j\leq m,\\[8pt] \dfrac{(-j+1)n-i}{2}, & i=2,4,\quad 1\leq j\leq m. \end{cases}\]
For even \(j\), define \[\Lambda(v_{i,j}) = \begin{cases} \dfrac{(-j+1)n-2i}{2}, & i=1,2,\quad 1\leq j\leq m,\\[8pt] \dfrac{(j-1)n+2i-2}{2}, & i=3,4,\quad 1\leq j\leq m-1,\\[8pt] 1, & i=3,\quad j=m,\\[6pt] \dfrac{ij}{2}, & i=4,\quad j=m. \end{cases}\]
Subcase 2.2. \(m\) is odd.
Label the vertices \(v_{i,j}\), where \[i=1,2,3,4,\qquad 1\leq j\leq m,\qquad j\neq m-1,\] in the same manner as in Subcase 2.1. For \(j=m-1\), define \[\Lambda(v_{i,m-1}) = \begin{cases} \dfrac{(-m+1)n-2i}{2}, & i=1,2,\\[8pt] \dfrac{(m+1)n-2i+4}{2}, & i=3,4. \end{cases}\]
In both subcases, \[\bar{\mathbb{S}}_{\Lambda_1^{c}} = \frac{nm}{2} = \bar{\mathbb{S}}_{\Lambda_1}.\]
Case 3. \(n=5\).
Subcase 3.1. \(m\) is odd.
Define \[\Lambda:V(mC_n) \longrightarrow \left\{ \pm1,\pm2,\ldots,\pm\frac{mn-1}{2} \right\}.\]
Label the vertices \(v_{i,j}\) with \[i=1,2,3,\qquad j\neq m-1,\qquad j\text{ odd},\] in the same manner as in part (a) of Subcase 4.1 in Theorem 1.
For even \(j\), define \[\Lambda(v_{i,j}) = \begin{cases} \dfrac{(-j+1)n-2i+1}{2}, & i=1,2,\quad 1\leq j\leq m,\\[8pt] \dfrac{(j+1)n-2i+3}{2}, & i=3,4,\quad 1\leq j\leq m. \end{cases}\]
For \(j=m\), define \[\Lambda(v_{i,m}) = \begin{cases} \dfrac{(-m+1)n-i-1}{2}, & i=1,3,\\[8pt] \dfrac{(m+1)n-2i}{2}, & i=2,\\[8pt] 1, & i=4,5. \end{cases}\]
Therefore, \[\bar{\mathbb{S}}_{\Lambda_1^{c}} = \frac{nm+1}{2}, \qquad \bar{\mathbb{S}}_{\Lambda_1} = \frac{nm-1}{2}.\]
Subcase 3.2. \(m\) is even.
Define \[\Lambda:V(mC_n) \longrightarrow \left\{ \pm1,\pm2,\ldots,\pm\frac{mn}{2} \right\}.\]
Label the vertices \(v_{i,j}\) with \[i=1,2,3,4,5, \qquad 1\leq j\leq m-1,\] in the same manner as in Subcase 3.1. For \(j=m\), define \[\Lambda(v_{i,m}) = \begin{cases} \dfrac{(-m+1)n-2i+1}{2}, & i=1,2,\\[8pt] \dfrac{(m-1)n+i+3}{2}, & i=3,\\[8pt] \dfrac{(-m+1)n+1}{2}, & i=4,\\[8pt] 1, & i=5. \end{cases}\]
Therefore, \[\bar{\mathbb{S}}_{\Lambda_1^{c}} = \frac{nm}{2} = \bar{\mathbb{S}}_{\Lambda_1}.\]
Case 4. \(n\geq 6\).
We distinguish the cases according to the parity of \(n\).
Subcase 4.1. \(n\) is even.
Define \[\Lambda:V(mC_n) \longrightarrow \left\{ \pm1,\pm2,\ldots,\pm\frac{mn}{2} \right\}.\]
(a) \(m\) is even.
Label the vertices \(v_{i,j}\) with \[1\leq i\leq n,\qquad 1\leq j\leq m,\qquad j\text{ odd},\] in the same manner as in Subcase 4.1 of Theorem 1.
For even \(j\), define \[\Lambda(v_{i,j}) = \begin{cases} \dfrac{(j-1)n+i+3}{2}, & i=1,\quad 1\leq j\leq m,\\[8pt] \dfrac{(-j+1)n-2i+2}{2}, & i=2,3,\ldots,\dfrac{n+2}{2}, \quad 1\leq j\leq m,\\[10pt] \dfrac{(j+1)n-2i+4}{2}, & i=\dfrac{n+4}{2},\dfrac{n+6}{2}, \ldots,n-1,\quad 1\leq j\leq m,\\[10pt] \dfrac{jn+2}{2}, & i=n,\quad 1\leq j\leq m-1,\\[8pt] \dfrac{(-j-1)n+i}{2}, & i=5,\quad 1\leq j\leq m-1. \end{cases}\]
(b) \(m\) is odd.
Label the vertices \(v_{i,j}\) with \[1\leq i\leq n,\qquad 1\leq j\leq m-1,\] in the same manner as in part (a) of Subcase 4.1. For \(j=m\), define \[\Lambda(v_{i,m}) = \begin{cases} \dfrac{(m-1)n+i+3}{2}, & i=1,3,\\[8pt] \dfrac{(-m+1)n-i}{2}, & i=2,4,\\[8pt] \dfrac{(-m+1)n-i-1}{2}, & i=5,7,\ldots,n-1,\\[8pt] \dfrac{(m-1)n+i+2}{2}, & i=6,8,\ldots,n-2,\\[8pt] 1, & i=n. \end{cases}\]
Subcase 4.2. \(n\) is odd.
(a) \(m\) is even.
Label the vertices \(v_{i,j}\) with \[1\leq i\leq n,\qquad 1\leq j\leq m-1,\] in the same manner as in Subcase 4.1 of Theorem 1. Define \[\Lambda:V(mC_n) \longrightarrow \left\{ \pm1,\pm2,\ldots,\pm\frac{mn}{2} \right\}.\]
For even \(j\), define \[\Lambda(v_{i,j}) = \begin{cases} \dfrac{(j-1)n+i+4}{2}, & i=1,\quad 1\leq j\leq m,\\[8pt] \dfrac{(-j+1)n-2i+3}{2}, & i=2,3,\ldots,\dfrac{n+3}{2}, \quad 1\leq j\leq m,\\[10pt] \dfrac{(j+1)n-2i+5}{2}, & i=\dfrac{n+5}{2},\dfrac{n+7}{2}, \ldots,n-1,\quad 1\leq j\leq m,\\[10pt] \dfrac{jn+2}{2}, & i=n,\quad 1\leq j\leq m-1,\\[8pt] 1, & i=n,\quad j=m. \end{cases}\]
(b) \(m\) is odd.
Label the vertices \(v_{i,j}\) with \[1\leq i\leq n,\qquad 1\leq j\leq m-1,\] in the same manner as in part (a) of Subcase 4.2. Define \[\Lambda:V(mC_n) \longrightarrow \left\{ \pm1,\pm2,\ldots,\pm\frac{mn-1}{2} \right\}.\]
For \(j=m\), define \[\Lambda(v_{i,m}) = \begin{cases} \dfrac{(-m+1)n-i-1}{2}, & i=1,3,\ldots,n-2,\\[8pt] \dfrac{(m-1)n+i+2}{2}, & i=2,4,\ldots,n-3,\\[8pt] \dfrac{(m+1)n-2i+5}{2}, & i=n-1,n. \end{cases}\]
The numbers of edges in the two induced edge-label classes for \(n\geq 6\) are summarized in Table 2.
| Parity conditions | \(\bar{\mathbb{S}}_{\Lambda_1^{c}}\) | \(\bar{\mathbb{S}}_{\Lambda_1}\) |
|---|---|---|
| \(n\) and \(m\) are even | \(\dfrac{mn}{2}\) | \(\dfrac{mn}{2}\) |
| \(n\) is even and \(m\) is odd | \(\dfrac{mn}{2}\) | \(\dfrac{mn}{2}\) |
| \(n\) is odd and \(m\) is even | \(\dfrac{mn}{2}\) | \(\dfrac{mn}{2}\) |
| \(n\) and \(m\) are odd | \(\dfrac{mn+1}{2}\) | \(\dfrac{mn-1}{2}\) |
As shown in Table 2, the cardinalities of the two induced edge-label classes are either equal or differ by exactly one. Thus, \[\left| \bar{\mathbb{S}}_{\Lambda_1^{c}} – \bar{\mathbb{S}}_{\Lambda_1} \right| \leq 1.\] Hence, the prescribed labeling satisfies the pair mean cordial condition. Therefore, \(mC_n\) is a PMC-graph for all \(n\geq 4\) and \(m\geq 1\). \(\square\)
Theorem 3. For all integers \(n\geq 2\) and \(m\geq 1\), the spider graph \(SP_{n,m}\) is a PMC-graph.
Proof. Let \[V(SP_{n,m}) = \{v_{0},v_{i,j}\mid 1\leq i\leq n,\;1\leq j\leq m\}\] and \[E(SP_{n,m}) = \{v_{i,j}v_{i+1,j},\,v_{0}v_{1,j} \mid 1\leq i\leq n-1,\;1\leq j\leq m\}\] denote, respectively, the vertex set and edge set of the spider graph \(SP_{n,m}\). Thus, \[|V(SP_{n,m})|=mn+1 \qquad\text{and}\qquad |E(SP_{n,m})|=mn.\]
For completeness, if \(n=1\), then \[SP_{1,m}\cong K_{1,m}.\] It is known that the star graph \(K_{1,m}\) is a PMC-graph if and only if \(1\leq m\leq 5\) [12].
For \(n=2\), we have \[SP_{2,m}\cong S(K_{1,m}),\] where \(S(K_{1,m})\) denotes the subdivision of the star graph \(K_{1,m}\). Since \(S(K_{1,m})\) is a PMC-graph [12], the result holds for \(n=2\).
Hence, it remains to consider \(n\geq 3\). We distinguish two cases according to the parity of \(n\).
Case 1. \(n\) is even.
Define \[\Lambda:V(SP_{n,m}) \longrightarrow \left\{ \pm1,\pm2,\ldots,\pm\frac{mn}{2} \right\}.\]
Subcase 1.1. \(m\) is even.
Label the vertices \(v_{i,j}\) satisfying \[1\leq i\leq n,\qquad 1\leq j\leq m-1,\qquad j\text{ is odd},\] in the same manner as in Subcase 4.1 of Theorem 4.
For even \(j\), where \(1\leq j\leq m-1\), define \[\Lambda(v_{i,j}) = \begin{cases} \dfrac{(j+1)n-2i-2}{2}, & i=1,2,\ldots,\dfrac{n}{2},\\[10pt] \dfrac{(-j+2)n-2i}{2}, & i=\dfrac{n+2}{2}, \dfrac{n+4}{2},\ldots,n. \end{cases}\]
For the vertices corresponding to \(j=m\), define \[\Lambda(v_{i,m}) = \begin{cases} \dfrac{mn-2i+2}{2}, & i=1,2,\ldots,\dfrac{n-2}{2},\\[10pt] \dfrac{(-m+2)n-2i-2}{2}, & i=\dfrac{n}{2}, \dfrac{n+2}{2},\ldots,n-1,\\[10pt] 1, & i=n. \end{cases}\]
Subcase 1.2. \(m\) is odd.
Label the vertices \(v_{i,j}\) satisfying \[1\leq i\leq n,\qquad 1\leq j\leq m-1\] in the same manner as in Subcase 1.1.
For \(j=m\), define \[\Lambda(v_{i,m}) = \begin{cases} \dfrac{(-m+1)n-2i}{2}, & i=1,3,\ldots,n-2,\\[10pt] \dfrac{(m-1)n+i+2}{2}, & i=2,4,\ldots,n-3,\\[10pt] 1, & i=n-1,n. \end{cases}\]
Case 2. \(n\) is odd.
Subcase 2.1. \(m\) is even.
Define \[\Lambda:V(SP_{n,m}) \longrightarrow \left\{ \pm1,\pm2,\ldots,\pm\frac{mn}{2} \right\}.\]
Label the vertices \(v_{i,j}\) satisfying \[1\leq i\leq n,\qquad 1\leq j\leq m-1,\qquad j\text{ is odd},\] in the same manner as in Subcase 4.1 of Theorem 1.
For even \(j\), where \(1\leq j\leq m-1\), define \[\Lambda(v_{i,j}) = \begin{cases} \dfrac{(j+1)n-2i-3}{2}, & i=1,2,\ldots,\dfrac{n-1}{2},\\[10pt] \dfrac{(-j+2)n-2i}{2}, & i=\dfrac{n+1}{2}, \dfrac{n+3}{2},\ldots,n. \end{cases}\]
For \(j=m\), define \[\Lambda(v_{i,m}) = \begin{cases} \dfrac{mn-2i+2}{2}, & i=1,2,\ldots,\dfrac{n-3}{2},\\[10pt] \dfrac{(-m+2)n-2i-2}{2}, & i=\dfrac{n-1}{2}, \dfrac{n+1}{2},\ldots,n-1,\\[10pt] 1, & i=n. \end{cases}\]
Subcase 2.2. \(m\) is odd.
In this case, define \[\Lambda:V(SP_{n,m}) \longrightarrow \left\{ \pm1,\pm2,\ldots,\pm\frac{mn+1}{2} \right\}.\]
Label the vertices \(v_{i,j}\) satisfying \[1\leq i\leq n,\qquad 1\leq j\leq m-1\] in the same manner as in Subcase 1.1.
For \(j=m\), define \[\Lambda(v_{i,m}) = \begin{cases} \dfrac{(-m+1)n-2i}{2}, & i=1,3,\ldots,n-2,\\[10pt] \dfrac{(m-1)n+i+2}{2}, & i=2,4,\ldots,n-1,\\[10pt] 1, & i=n. \end{cases}\]
For the cases in which \(mn\) is even, the induced edge-label classes satisfy \[\bar{\mathbb{S}}_{\Lambda_1^{c}} = \frac{mn}{2} = \bar{\mathbb{S}}_{\Lambda_1}.\]
When both \(n\) and \(m\) are odd, \(mn\) is odd, and hence the two edge-label classes have cardinalities \[\left\{ \bar{\mathbb{S}}_{\Lambda_1^{c}}, \bar{\mathbb{S}}_{\Lambda_1} \right\} = \left\{ \frac{mn+1}{2}, \frac{mn-1}{2} \right\}.\]
Therefore, in every case, \[\left| \bar{\mathbb{S}}_{\Lambda_1^{c}} – \bar{\mathbb{S}}_{\Lambda_1} \right| \leq 1.\] Thus, the labeling \(\Lambda\) satisfies the pair mean cordial condition. Consequently, \(SP_{n,m}\) is a PMC-graph for all \(n\geq 2\) and \(m\geq 1\). \(\square\)
Example 1. A pair mean cordial labeling of the spider graph \(SP_{5,4}\) is illustrated in Figure 2.
Theorem 4. For all integers \(n\geq 3\) and \(m\geq 2\), the generalized theta graph \(\theta_{n,m}\) is a PMC-graph.
Proof. Let \[V(\theta_{n,m}) = \{u_0,v_0,v_{i,j} \mid 1\leq i\leq n,\;1\leq j\leq m\}\] and \[E(\theta_{n,m}) = \{v_{i,j}v_{i+1,j},\, u_0v_{1,j},\, v_0v_{n,j} \mid 1\leq i\leq n-1,\;1\leq j\leq m\}\] denote, respectively, the vertex set and edge set of \(\theta_{n,m}\). Hence, \[|V(\theta_{n,m})|=nm+2 \qquad\text{and}\qquad |E(\theta_{n,m})|=(n+1)m.\]
We assign \[\Lambda(u_0)=1, \qquad \Lambda(v_0)=-\frac{nm+2}{2}.\]
We now distinguish two cases according to the parity of \(n\).
Case 1. \(n\) is even.
Define \[\Lambda:V(\theta_{n,m}) \longrightarrow \left\{ \pm1,\pm2,\ldots,\pm\frac{nm+2}{2} \right\}.\]
Subcase 1.1. \(m\) is even.
Label the vertices \(v_{i,j}\) satisfying \[1\leq i\leq n,\qquad 1\leq j\leq m-1,\qquad j\text{ is odd},\] in the same manner as in Subcase 4.1 of Theorem 1.
For even \(j\), define \[\Lambda(v_{i,j}) = \begin{cases} \dfrac{(-j+1)n-2i}{2}, & i=1,\quad 1\leq j\leq m,\\[10pt] \dfrac{(j-1)n+2i}{2}, & i=2,3,\ldots,\dfrac{n+2}{2}, \quad 1\leq j\leq m,\\[10pt] \dfrac{(-j-1)n+2i-4}{2}, & i=\dfrac{n+4}{2}, \dfrac{n+6}{2},\ldots,n, \quad 1\leq j\leq m. \end{cases}\]
Subcase 1.2. \(m\) is odd.
Label the vertices \(v_{i,j}\) satisfying \[1\leq i\leq n,\qquad 1\leq j\leq m-1\] in the same manner as in Subcase 1.1.
For \(j=m\), define \[\Lambda(v_{i,m}) = \begin{cases} \dfrac{(-m+1)n-i-1}{2}, & i=1,3,\ldots,n-1,\\[10pt] \dfrac{(m-1)n+i+2}{2}, & i=2,4,\ldots,n. \end{cases}\]
Case 2. \(n\) is odd.
Subcase 2.1. \(m\) is even.
Define \[\Lambda:V(\theta_{n,m}) \longrightarrow \left\{ \pm1,\pm2,\ldots,\pm\frac{nm+2}{2} \right\}.\]
Label the vertices \(v_{i,j}\) satisfying \[1\leq i\leq n,\qquad 1\leq j\leq m-1,\qquad j\text{ is odd},\] in the same manner as in Subcase 4.1 of Theorem 1.
For even \(j\), define \[\Lambda(v_{i,j}) = \begin{cases} \dfrac{(-j+1)n-2i+1}{2}, & i=1,\quad 1\leq j\leq m,\\[10pt] \dfrac{(j-1)n+2i+1}{2}, & i=2,3,\ldots,\dfrac{n+1}{2}, \quad 1\leq j\leq m,\\[10pt] \dfrac{(-j-1)n+2i-3}{2}, & i=\dfrac{n+3}{2}, \dfrac{n+5}{2},\ldots,n, \quad 1\leq j\leq m. \end{cases}\]
Subcase 2.2. \(m\) is odd.
In this case, define \[\Lambda:V(\theta_{n,m}) \longrightarrow \left\{ \pm1,\pm2,\ldots,\pm\frac{nm+1}{2} \right\}.\]
Label the vertices \(v_{i,j}\) satisfying \[1\leq i\leq n,\qquad 1\leq j\leq m-1\] in the same manner as in Subcase 2.1.
For \(j=m\), define \[\Lambda(v_{i,m}) = \begin{cases} \dfrac{(-m+1)n-i-1}{2}, & i=1,3,\ldots,n-2,\\[10pt] \dfrac{(m-1)n+i+2}{2}, & i=2,4,\ldots,n-1,\\[10pt] mn, & i=n. \end{cases}\]
The resulting numbers of edges in the two induced edge-label classes are summarized in Table 3.
| Parity conditions | \(\bar{\mathbb{S}}_{\Lambda_1^{c}}\) | \(\bar{\mathbb{S}}_{\Lambda_1}\) |
|---|---|---|
| \(n\) and \(m\) are even | \(\dfrac{(n+1)m}{2}\) | \(\dfrac{(n+1)m}{2}\) |
| \(n\) is even and \(m\) is odd | \(\dfrac{(n+1)m+1}{2}\) | \(\dfrac{(n+1)m-1}{2}\) |
| \(n\) is odd and \(m\) is even | \(\dfrac{(n+1)m}{2}\) | \(\dfrac{(n+1)m}{2}\) |
| \(n\) and \(m\) are odd | \(\dfrac{(n+1)m}{2}\) | \(\dfrac{(n+1)m}{2}\) |
As shown in Table 3, the numbers of edges in the two induced edge-label classes are either equal or differ by exactly one. Consequently, \[\left| \bar{\mathbb{S}}_{\Lambda_1^{c}} – \bar{\mathbb{S}}_{\Lambda_1} \right| \leq 1.\] Therefore, the prescribed labeling satisfies the pair mean cordial condition, and hence \(\theta_{n,m}\) is a PMC-graph for all \(n\geq3\) and \(m\geq2\). \(\square\)
Example 2. A pair mean cordial labeling of the generalized theta graph \(\theta_{6,5}\) is illustrated in Figure 3.
Theorem 5. The generalized theta graph \(\theta_{2,m}\) is a PMC-graph if and only if \(2\leq m\leq 5\).
Proof. The generalized theta graph \(\theta_{2,m}\) has \[|V(\theta_{2,m})|=2m+2 \qquad\text{and}\qquad |E(\theta_{2,m})|=3m.\] Since \(|V(\theta_{2,m})|=2m+2\) is even, the corresponding label set is \[\{\pm1,\pm2,\ldots,\pm(m+1)\}.\]
We first show that \(\theta_{2,m}\) is a PMC-graph for \(2\leq m\leq5\), and then prove that no PMC-labeling exists when \(m\geq6\).
Case 1. \(m=2\).
In this case, \[\theta_{2,2}\cong C_6.\] Since the cycle \(C_6\) is a PMC-graph [12], it follows that \(\theta_{2,2}\) is also a PMC-graph.
Case 2. \(m=3\).
Define \[\Lambda:V(\theta_{2,3}) \longrightarrow \{\pm1,\pm2,\pm3,\pm4\}.\] Set \[\Lambda(u_0)=2, \qquad \Lambda(v_0)=-4.\] For the remaining vertices, define \[\Lambda(v_{i,j}) = \begin{cases} -j, & i=1,\quad j=1,2,3,\\[6pt] j+2, & i=2,\quad j=1,2,\\[6pt] 1, & i=2,\quad j=3. \end{cases}\]
Under the induced edge labeling, \[\bar{\mathbb{S}}_{\Lambda_1^{c}}=4 \qquad\text{and}\qquad \bar{\mathbb{S}}_{\Lambda_1}=5.\] Hence, \[\left| \bar{\mathbb{S}}_{\Lambda_1^{c}} – \bar{\mathbb{S}}_{\Lambda_1} \right| =1,\] and therefore \(\theta_{2,3}\) is a PMC-graph.
Case 3. \(m=4\).
Define \[\Lambda:V(\theta_{2,4}) \longrightarrow \{\pm1,\pm2,\ldots,\pm5\}.\] Set \[\Lambda(u_0)=2, \qquad \Lambda(v_0)=-2.\] For the remaining vertices, define \[\Lambda(v_{i,j}) = \begin{cases} -j, & i=1,\quad j=1,\\[6pt] -j-1, & i=1,\quad j=2,3,4,\\[6pt] j+2, & i=2,\quad j=1,2,3,\\[6pt] 1, & i=2,\quad j=4. \end{cases}\]
The induced edge labeling satisfies \[\bar{\mathbb{S}}_{\Lambda_1^{c}} = 6 = \bar{\mathbb{S}}_{\Lambda_1}.\] Thus, \[\left| \bar{\mathbb{S}}_{\Lambda_1^{c}} – \bar{\mathbb{S}}_{\Lambda_1} \right| =0,\] and hence \(\theta_{2,4}\) is a PMC-graph.
Case 4. \(m=5\).
Define \[\Lambda:V(\theta_{2,5}) \longrightarrow \{\pm1,\pm2,\ldots,\pm6\}.\] Set \[\Lambda(u_0)=2, \qquad \Lambda(v_0)=-2.\] For the remaining vertices, define \[\Lambda(v_{i,j}) = \begin{cases} -j, & i=1,\quad j=1,\\[6pt] -j-1, & i=1,\quad j=2,3,4,5,\\[6pt] j+2, & i=2,\quad j=1,2,3,4,\\[6pt] 1, & i=2,\quad j=5. \end{cases}\]
The resulting edge labeling yields \[\bar{\mathbb{S}}_{\Lambda_1^{c}}=7 \qquad\text{and}\qquad \bar{\mathbb{S}}_{\Lambda_1}=8.\] Consequently, \[\left| \bar{\mathbb{S}}_{\Lambda_1^{c}} – \bar{\mathbb{S}}_{\Lambda_1} \right| =1.\] Therefore, \(\theta_{2,5}\) is a PMC-graph.
Case 5. \(m\geq6\).
Suppose, to the contrary, that \(\theta_{2,m}\) is a PMC-graph for some \(m\geq6\). Let \[\Lambda:V(\theta_{2,m}) \longrightarrow \{\pm1,\pm2,\ldots,\pm(m+1)\}\] be a PMC-labeling.
By the definition of pair mean cordial labeling, an edge \(uv\in E(\theta_{2,m})\) receives the induced label \(1\) precisely when \[\Lambda(u)+\Lambda(v)\in\{1,2\}.\] Counting the edges that can satisfy this condition gives \[\bar{\mathbb{S}}_{\Lambda_1}\leq m+2,\] where \(\bar{\mathbb{S}}_{\Lambda_1}\) denotes the number of edges whose induced label is \(1\).
Since \[|E(\theta_{2,m})|=3m,\] we have \[\bar{\mathbb{S}}_{\Lambda_1^{c}} + \bar{\mathbb{S}}_{\Lambda_1} = 3m.\] Therefore, \[\bar{\mathbb{S}}_{\Lambda_1^{c}} = 3m-\bar{\mathbb{S}}_{\Lambda_1} \geq 3m-(m+2) = 2m-2.\] It follows that \[\begin{aligned} \bar{\mathbb{S}}_{\Lambda_1^{c}} – \bar{\mathbb{S}}_{\Lambda_1} &\geq (2m-2)-(m+2)\\ &= m-4. \end{aligned}\] Since \(m\geq6\), \[m-4\geq2,\] and hence \[\left| \bar{\mathbb{S}}_{\Lambda_1^{c}} – \bar{\mathbb{S}}_{\Lambda_1} \right| \geq2>1.\] This contradicts the defining condition of a PMC-labeling.
Therefore, \(\theta_{2,m}\) does not admit a pair mean cordial labeling for any \(m\geq6\). Combining this with Cases 1–4, we conclude that \[\theta_{2,m}\text{ is a PMC-graph} \quad\Longleftrightarrow\quad 2\leq m\leq5.\] \(\square\)
Theorem 6. The generalized theta graph \(\theta_{1,m}\) is a PMC-graph if and only if \(m=5\).
Proof. The generalized theta graph \(\theta_{1,m}\) has \[|V(\theta_{1,m})|=m+2 \qquad\text{and}\qquad |E(\theta_{1,m})|=2m.\]
We first show that \(\theta_{1,5}\) admits a pair mean cordial labeling, and then prove that no such labeling exists for \(m\neq5\).
Case 1. \(2\leq m\leq4\).
Suppose, to the contrary, that \(\theta_{1,m}\) admits a PMC-labeling. Let \[\Lambda:V(\theta_{1,m})\longrightarrow M,\] where \[M=\{\pm1,\pm2,\ldots,\pm\rho\},\] with \[\rho= \begin{cases} \dfrac{m+2}{2}, & m\text{ is even},\\[6pt] \dfrac{m+1}{2}, & m\text{ is odd}. \end{cases}\]
By the definition of pair mean cordial labeling, an edge \(uv\in E(\theta_{1,m})\) receives the induced label \(1\) precisely when \[\Lambda(u)+\Lambda(v)\in\{1,2\}.\] Counting all edges satisfying this condition gives \[\bar{\mathbb{S}}_{\Lambda_1}\leq m-1.\] Since \[\bar{\mathbb{S}}_{\Lambda_1^{c}} + \bar{\mathbb{S}}_{\Lambda_1} = |E(\theta_{1,m})| = 2m,\] we obtain \[\bar{\mathbb{S}}_{\Lambda_1^{c}} = 2m-\bar{\mathbb{S}}_{\Lambda_1} \geq 2m-(m-1) = m+1.\] Consequently, \[\begin{aligned} \bar{\mathbb{S}}_{\Lambda_1^{c}} – \bar{\mathbb{S}}_{\Lambda_1} &\geq (m+1)-(m-1)\\ &=2>1. \end{aligned}\] This contradicts the PMC-labeling condition. Therefore, \(\theta_{1,m}\) is not a PMC-graph for \(2\leq m\leq4\).
Case 2. \(m=5\).
Since \(\theta_{1,5}\) has seven vertices, consider the labeling \[\Lambda:V(\theta_{1,5}) \longrightarrow \{\pm1,\pm2,\pm3\}.\] Assign the labels \[-1,-2,-3,1,2,3,3\] to the vertices \[u_0,v_0,v_{1,1},v_{1,2},v_{1,3},v_{1,4},v_{1,5},\] respectively. Equivalently, \[\begin{aligned} \Lambda(u_0)&=-1, & \Lambda(v_0)&=-2, & \Lambda(v_{1,1})&=-3,\\ \Lambda(v_{1,2})&=1, & \Lambda(v_{1,3})&=2, & \Lambda(v_{1,4})&=3, & \Lambda(v_{1,5})&=3. \end{aligned}\]
The induced edge labeling satisfies \[\bar{\mathbb{S}}_{\Lambda_1^{c}} = 5 = \bar{\mathbb{S}}_{\Lambda_1}.\] Hence, \[\left| \bar{\mathbb{S}}_{\Lambda_1^{c}} – \bar{\mathbb{S}}_{\Lambda_1} \right| =0,\] and therefore \(\theta_{1,5}\) is a PMC-graph.
Case 3. \(m\geq6\).
We distinguish two subcases according to the parity of \(m\).
Subcase 3.1. \(m\) is odd.
Since \(m\geq6\) and \(m\) is odd, we have \(m\geq7\). Let \[\Lambda:V(\theta_{1,m}) \longrightarrow \left\{ \pm1,\pm2,\ldots,\pm\frac{m+1}{2} \right\}\] be a PMC-labeling.
An edge \(uv\in E(\theta_{1,m})\) receives the induced label \(1\) if and only if \[\Lambda(u)+\Lambda(v)\in\{1,2\}.\] Counting all such edges yields \[\bar{\mathbb{S}}_{\Lambda_1}\leq6.\] Since \[\bar{\mathbb{S}}_{\Lambda_1^{c}} + \bar{\mathbb{S}}_{\Lambda_1} = 2m,\] it follows that \[\bar{\mathbb{S}}_{\Lambda_1^{c}} \geq 2m-6.\] Therefore, \[\begin{aligned} \bar{\mathbb{S}}_{\Lambda_1^{c}} – \bar{\mathbb{S}}_{\Lambda_1} &\geq (2m-6)-6\\ &= 2m-12. \end{aligned}\] Since \(m\geq7\), \[2m-12\geq2>1,\] which contradicts the PMC-labeling condition.
Subcase 3.2. \(m\) is even.
Let \[\Lambda:V(\theta_{1,m}) \longrightarrow \left\{ \pm1,\pm2,\ldots,\pm\frac{m+2}{2} \right\}\] be a PMC-labeling.
Again, an edge \(uv\) receives the induced label \(1\) only when \[\Lambda(u)+\Lambda(v)\in\{1,2\}.\] Counting all such edges gives \[\bar{\mathbb{S}}_{\Lambda_1}\leq4.\] Hence, \[\bar{\mathbb{S}}_{\Lambda_1^{c}} = 2m-\bar{\mathbb{S}}_{\Lambda_1} \geq 2m-4.\] Consequently, \[\begin{aligned} \bar{\mathbb{S}}_{\Lambda_1^{c}} – \bar{\mathbb{S}}_{\Lambda_1} &\geq (2m-4)-4\\ &= 2m-8. \end{aligned}\] Since \(m\geq6\), \[2m-8\geq4>1,\] which again contradicts the PMC-labeling condition.
Thus, \(\theta_{1,m}\) does not admit a pair mean cordial labeling for \(m\neq5\). Since \(\theta_{1,5}\) admits such a labeling, we conclude that \[\theta_{1,m}\text{ is a PMC-graph} \quad\Longleftrightarrow\quad m=5.\] \(\square\)
Theorem 7. The Tunjung graph \(TJ_n\) is not a PMC-graph for any integer \(n\geq3\).
Proof. Consider the Tunjung graph \(TJ_n\). Let \[V(TJ_n) = \{v_0,u_i,v_i,w_i\mid1\leq i\leq n\}\] and \[\begin{aligned} E(TJ_n) ={}& \{v_0u_i,v_0v_i,v_0w_i,u_iv_i,v_iw_i \mid1\leq i\leq n\}{}\cup \{u_iu_{i+1},v_iv_{i+1} \mid1\leq i\leq n-1\}{}\cup \{u_nu_1,v_nv_1\}. \end{aligned}\] Thus, \[|V(TJ_n)|=3n+1 \qquad\text{and}\qquad |E(TJ_n)|=7n.\]
Suppose, to the contrary, that \(TJ_n\) admits a PMC-labeling \(\Lambda\). We consider the following cases.
Case 1. \(n=3\).
Since \(3n+1\) is even, let \[\Lambda:V(TJ_n) \longrightarrow \left\{ \pm1,\pm2,\ldots,\pm\frac{3n+1}{2} \right\}.\]
By the pair mean cordial labeling rule, an edge \(uv\in E(TJ_n)\) receives the induced label \(1\) only when \[\Lambda(u)+\Lambda(v)\in\{1,2\}.\] Counting all such edges yields \[\bar{\mathbb{S}}_{\Lambda_1}\leq2n+1.\] Since \[\bar{\mathbb{S}}_{\Lambda_1^{c}} + \bar{\mathbb{S}}_{\Lambda_1} = 7n,\] we obtain \[\bar{\mathbb{S}}_{\Lambda_1^{c}} \geq 7n-(2n+1) = 5n-1.\] Therefore, \[\begin{aligned} \bar{\mathbb{S}}_{\Lambda_1^{c}} – \bar{\mathbb{S}}_{\Lambda_1} &\geq (5n-1)-(2n+1)\\ &= 3n-2. \end{aligned}\] For \(n=3\), \[3n-2=7>1.\] This contradicts the PMC-labeling condition.
Case 2. \(n=4\).
Since \(3n+1=13\) is odd, the corresponding label set is \[\{\pm1,\pm2,\ldots,\pm6\},\] with one label repeated as required by the definition of a PMC-labeling.
The same counting argument gives \[\bar{\mathbb{S}}_{\Lambda_1}\leq2n+3.\] Therefore, \[\bar{\mathbb{S}}_{\Lambda_1^{c}} \geq 7n-(2n+3) = 5n-3,\] and hence \[\begin{aligned} \bar{\mathbb{S}}_{\Lambda_1^{c}} – \bar{\mathbb{S}}_{\Lambda_1} &\geq (5n-3)-(2n+3)\\ &= 3n-6. \end{aligned}\] For \(n=4\), \[3n-6=6>1,\] again contradicting the PMC-labeling condition.
Case 3. \(n\geq5\) and \(n\) is odd.
Since \(3n+1\) is even, consider \[\Lambda:V(TJ_n) \longrightarrow \left\{ \pm1,\pm2,\ldots,\pm\frac{3n+1}{2} \right\}.\] Counting the edges whose induced label is \(1\) yields \[\bar{\mathbb{S}}_{\Lambda_1}\leq2n+3.\] Thus, \[\bar{\mathbb{S}}_{\Lambda_1^{c}} \geq 7n-(2n+3) = 5n-3.\] Consequently, \[\begin{aligned} \bar{\mathbb{S}}_{\Lambda_1^{c}} – \bar{\mathbb{S}}_{\Lambda_1} &\geq (5n-3)-(2n+3)\\ &= 3n-6. \end{aligned}\] Since \(n\geq5\), \[3n-6\geq9>1,\] which contradicts the PMC-labeling condition.
Case 4. \(n\geq6\) and \(n\) is even.
Since \(3n+1\) is odd, let \[\Lambda:V(TJ_n) \longrightarrow \left\{ \pm1,\pm2,\ldots,\pm\frac{3n}{2} \right\},\] where one label is repeated in accordance with the definition of a PMC-labeling.
An edge \(uv\in E(TJ_n)\) can receive the induced label \(1\) only when \[\Lambda(u)+\Lambda(v)\in\{1,2\}.\] Counting all such edges gives \[\bar{\mathbb{S}}_{\Lambda_1}\leq2n+4.\] Hence, \[\bar{\mathbb{S}}_{\Lambda_1^{c}} \geq 7n-(2n+4) = 5n-4.\] It follows that \[\begin{aligned} \bar{\mathbb{S}}_{\Lambda_1^{c}} – \bar{\mathbb{S}}_{\Lambda_1} &\geq (5n-4)-(2n+4)\\ &= 3n-8. \end{aligned}\] Since \(n\geq6\), \[3n-8\geq10>1.\] This contradicts the PMC-labeling condition.
Thus, in every possible case, \[\left| \bar{\mathbb{S}}_{\Lambda_1^{c}} – \bar{\mathbb{S}}_{\Lambda_1} \right| >1,\] which is incompatible with the definition of pair mean cordial labeling. Therefore, the Tunjung graph \(TJ_n\) is not a PMC-graph for any \(n\geq3\). \(\square\)
Theorem 8. The volcano graph \(V_n\) is a PMC-graph if and only if \(n\in\{3,4,6\}\).
Proof. Let \[V(V_n) = \{u_1,u_2,u_3,v_i\mid 1\leq i\leq n\}\] and \[E(V_n) = \{u_1u_2,u_2u_3,u_3u_1,u_1v_i \mid 1\leq i\leq n\}\] denote, respectively, the vertex set and edge set of the volcano graph \(V_n\). Thus, \[|V(V_n)|=n+3 \qquad\text{and}\qquad |E(V_n)|=n+3.\]
We first exhibit pair mean cordial labelings for \(n=3,4,6\) and then show that no such labeling exists for the remaining values of \(n\).
Case 1. \(n=3\).
Assign the labels \[3,-1,2\] to the vertices \[u_1,u_2,u_3,\] respectively, and assign \[-2,-3,1\] to the vertices \[v_1,v_2,v_3,\] respectively. Equivalently, \[\begin{aligned} \Lambda(u_1)&=3, & \Lambda(u_2)&=-1, & \Lambda(u_3)&=2,\\ \Lambda(v_1)&=-2, & \Lambda(v_2)&=-3, & \Lambda(v_3)&=1. \end{aligned}\]
Under the induced edge labeling, \[\bar{\mathbb{S}}_{\Lambda_1^{c}} = 3 = \bar{\mathbb{S}}_{\Lambda_1}.\] Hence, \[\left| \bar{\mathbb{S}}_{\Lambda_1^{c}} – \bar{\mathbb{S}}_{\Lambda_1} \right| =0,\] and therefore \(V_3\) is a PMC-graph.
Case 2. \(n=4\).
Assign the labels \[3,-1,2\] to \(u_1,u_2,u_3\), respectively, and assign \[-2,-3,1,1\] to \(v_1,v_2,v_3,v_4\), respectively. Thus, \[\begin{aligned} \Lambda(u_1)&=3, & \Lambda(u_2)&=-1, & \Lambda(u_3)&=2,\\ \Lambda(v_1)&=-2, & \Lambda(v_2)&=-3, & \Lambda(v_3)&=1, & \Lambda(v_4)&=1. \end{aligned}\]
The resulting edge labeling satisfies \[\bar{\mathbb{S}}_{\Lambda_1^{c}}=4 \qquad\text{and}\qquad \bar{\mathbb{S}}_{\Lambda_1}=3.\] Consequently, \[\left| \bar{\mathbb{S}}_{\Lambda_1^{c}} – \bar{\mathbb{S}}_{\Lambda_1} \right| =1.\] Hence, \(V_4\) is a PMC-graph.
Case 3. \(n=6\).
Assign the labels \[3,-1,2\] to \(u_1,u_2,u_3\), respectively, and assign \[-2,-3,-4,1,4,-2\] to \(v_1,v_2,\ldots,v_6\), respectively. In other words, \[\begin{aligned} \Lambda(u_1)&=3, & \Lambda(u_2)&=-1, & \Lambda(u_3)&=2,\\ \Lambda(v_1)&=-2, & \Lambda(v_2)&=-3, & \Lambda(v_3)&=-4,\\ \Lambda(v_4)&=1, & \Lambda(v_5)&=4, & \Lambda(v_6)&=-2. \end{aligned}\]
Under the induced edge labeling, \[\bar{\mathbb{S}}_{\Lambda_1^{c}}=5 \qquad\text{and}\qquad \bar{\mathbb{S}}_{\Lambda_1}=4.\] Therefore, \[\left| \bar{\mathbb{S}}_{\Lambda_1^{c}} – \bar{\mathbb{S}}_{\Lambda_1} \right| =1,\] and hence \(V_6\) is a PMC-graph.
Thus, \(V_n\) admits a pair mean cordial labeling for \(n=3,4,6\).
Case 4. \(n\geq5\) and \(n\) is odd.
Suppose, to the contrary, that \(V_n\) is a PMC-graph. Since \(n+3\) is even, consider a PMC-labeling \[\Lambda:V(V_n) \longrightarrow \left\{ \pm1,\pm2,\ldots,\pm\frac{n+3}{2} \right\}.\]
By the definition of pair mean cordial labeling, an edge \(uv\in E(V_n)\) receives the induced label \(1\) only when \[\Lambda(u)+\Lambda(v)\in\{1,2\}.\] Counting all edges satisfying this condition gives \[\bar{\mathbb{S}}_{\Lambda_1}\leq3.\]
Since \[\bar{\mathbb{S}}_{\Lambda_1^{c}} + \bar{\mathbb{S}}_{\Lambda_1} = |E(V_n)| = n+3,\] we have \[\bar{\mathbb{S}}_{\Lambda_1^{c}} = n+3-\bar{\mathbb{S}}_{\Lambda_1} \geq n+3-3 = n.\] Consequently, \[\begin{aligned} \bar{\mathbb{S}}_{\Lambda_1^{c}} – \bar{\mathbb{S}}_{\Lambda_1} &\geq n-3. \end{aligned}\] Since \(n\geq5\), \[n-3\geq2>1,\] which contradicts the PMC-labeling condition. Therefore, \(V_n\) is not a PMC-graph for odd \(n\geq5\).
Case 5. \(n\geq8\) and \(n\) is even.
Suppose, to the contrary, that \(V_n\) admits a PMC-labeling. Since \(n+3\) is odd, let \[\Lambda:V(V_n) \longrightarrow \left\{ \pm1,\pm2,\ldots,\pm\frac{n+2}{2} \right\}\] be a PMC-labeling, with one label repeated in accordance with the definition.
Again, an edge \(uv\in E(V_n)\) receives the induced label \(1\) only when \[\Lambda(u)+\Lambda(v)\in\{1,2\}.\] Counting all such edges gives \[\bar{\mathbb{S}}_{\Lambda_1}\leq4.\] Since \[\bar{\mathbb{S}}_{\Lambda_1^{c}} + \bar{\mathbb{S}}_{\Lambda_1} = n+3,\] it follows that \[\bar{\mathbb{S}}_{\Lambda_1^{c}} = n+3-\bar{\mathbb{S}}_{\Lambda_1} \geq n+3-4 = n-1.\] Hence, \[\begin{aligned} \bar{\mathbb{S}}_{\Lambda_1^{c}} – \bar{\mathbb{S}}_{\Lambda_1} &\geq (n-1)-4\\ &= n-5. \end{aligned}\] Since \(n\geq8\), \[n-5\geq3>1.\] This contradicts the PMC-labeling condition. Therefore, \(V_n\) is not a PMC-graph for even \(n\geq8\).
Combining Cases 1–5, we conclude that \[V_n\text{ is a PMC-graph} \quad\Longleftrightarrow\quad n\in\{3,4,6\}.\] \(\square\)
Example 3. A pair mean cordial labeling of the volcano graph \(V_4\) is illustrated in Figure 4.
In this paper, we investigated pair mean cordial labelings for several classes of graphs, including \(m\) copies of paths, \(m\) copies of cycles, spider graphs, generalized theta graphs, Tunjung graphs, and volcano graphs. Explicit labeling constructions were provided for graph families that admit pair mean cordial labelings, while nonexistence results were established for the remaining cases by analyzing the distribution of induced edge labels.
In particular, the results characterize the pair mean cordial behavior of the graph families considered in this work. The study can be extended to several other graph classes, including generalized prism graphs, kayak paddle graphs, double kayak paddle graphs, generalized friendship graphs, generalized flower graphs, step-ladder graphs, palm trees, honeycomb graphs, lollipop graphs, Christmas trees, olive trees, caterpillar trees, and lobster trees. Determining the existence of PMC-labelings for these graph families, characterizing the corresponding parameter ranges, and developing systematic labeling constructions remain interesting problems for future investigation.
