# Product Cordial and Total Product Cordial Labelings ofP

Authors: Zhen-Bin Gao; Guang-Yi Sun; Yuan-Ning Zhang; Yu Meng; Gee-Choon Lau
Journal: Journal of Discrete Mathematics
 (2015)

---

## Abstract

We proved thatP
n
+
1
m is total product cordial. We also give sufficient conditions for the graph to admit (or not admit) a product cordial labeling.


---

## Body

## 1. Introduction

LetG
(
V
,
E
) denote a simple and finite connected graph G with vertex set V and edge set E. Suppose f and f
* denote a vertex and an edge labeling of a graph, respectively. Let v
f
(
i
) and e
f
*
(
i
) denote the number of vertices and edges labeled with i
∈
{
0,1
}. In 2004, Sundaram et al. [1] introduced the notion of product cordial labelings.Definition 1.
Letf
:
V
→
{
0,1
} be a vertex labeling of a graph G that induces an edge labelings f
*
:
E
→
{
0,1
} such that f
*
(
u
v
)
=
f
(
u
)
f
(
v
). One says f is a product cordial labeling if |
v
f
(
0
)
-
v
f
(
1
)
|
≤
1 and |
e
f
*
(
0
)
-
e
f
*
(
1
)
|
≤
1. A graph G is called a product cordial graph if it admits a product cordial labeling.Sundaram et al. [1] proved that many graphs are product cordial: trees; unicyclic graphs of odd order; triangular snakes; dragons; helms; P
m
∪
P
n; C
m
∪
P
n if and only if m
+
n is odd; P
m
∪
K
1
,
n; W
m
∪
F
n; K
1
,
m
∪
K
1
,
n; W
m
∪
K
1
,
n; W
m
∪
P
n; W
m
∪
C
n; P
n
2 if and only if n is odd; C
n if and only if n
<
4. Kwong et al. [2] discussed product cordial index sets of 2 regular graphs. Kwong et al. [3] discussed product cordial index sets of cylinders.In 2006, Sundaram et al. [4] introduced the notion of total product cordial labelings.Definition 2.
Letf
:
V
→
{
0,1
} be a vertex labeling of a graph G that induces edge labelings f
*
:
E
→
{
0,1
} such that f
*
(
u
v
)
=
f
(
u
)
f
(
v
). We say f is a total product cordial labeling if |
(
v
f
(
0
)
+
e
f
*
(
0
)
)
-
(
v
f
(
1
)
+
e
f
*
(
1
)
)
|
≤
1. A graph G is called a total product cordial graph if it admits a total product cordial labeling.Sundaram et al. [4, 5] also proved that graphs are total product cordial: every product cordial graph of even order or odd order and even size; trees; all cycles except C
4; K
n
,
2
n
-
1; C
n with m edges appended at each vertex; fans; wheels; helms. In [6], Ramanjaneyulu et al. proved that a family of planar graphs for which each face is a 4-cycle admit a total product cordial labeling.In this paper, we determine the product cordiality and total product cordiality of themth power of the path P
n
+
1, denoted by P
n
+
1
m, which is defined as follows [7].Definition 3.
LetP
n
+
1 denote a path of length n. The graph P
n
+
1
m is obtained from P
n
+
1 by adding edges that join all vertices u and v whose distance is m. The graph P
n
+
1
m is illustrated in Figure 1. P
n
+
1
m has (
2
n
-
m
+
1
) edges.Figure 1
GraphP
n
+
1
m.In [5], the authors prove that all cycles except C
4 are total product cordial. Interested readers may refer to [8] for more results on product cordial labeling and total product cordial labeling.Definition 4.
The degree of a vertexu, denoted by d
(
u
) (or simply d), is the number of edges incident to u.


## 2. Total Product Cordial Labeling

Whenm
=
n, P
n
+
1
n is the cycle C
n
+
1 and is total product cordial except C
4 [4, 5]. Hence, we discuss the total product cordial labelings of P
n
+
1
m for 2
≤
m
<
n. We will let g
(
i
)
=
v
f
(
i
)
+
e
f
*
(
i
) for i
=
0,1.Lemma 5.
For2
≤
m
≤
[
n
+
1
/
2
], P
n
+
1
m is a total product cordial graph.Proof.
Observe thatd
(
u
1
)
=
d
(
u
n
+
1
)
=
2, d
(
u
i
)
=
3 for i
∈
{
2,3
,
…
,
m
,
n
-
m
+
2
,
n
-
m
+
3
,
…
,
n
} and d
(
u
i
)
=
4 for i
∈
{
m
+
1
,
m
+
2
,
…
,
n
-
m
+
1
}. Also |
V
|
+
|
E
|
=
3
n
-
m
+
2. Suppose n
-
m
/
2
+
n
+
1
=
3
k when n
-
m is even (or n
-
m
+
1
/
2
+
n
+
1
=
3
k when n
-
m is odd).
Case
1 (
n
-
m
is even). A total product cordial labeling gives g
(
0
)
=
g
(
1
)
=
3
k. Define f
(
u
i
)
=
0 for i
∈
{
1,2
,
…
,
k
} and f
(
u
i
)
=
1 for i
∈
{
k
+
1
,
k
+
2
,
…
,
n
+
1
} such that 3
k
-
2
≤
g
(
0
)
≤
3
k.
If3
k
=
g
(
0
), we get g
(
0
)
=
g
(
1
)
=
3
k. So f is a total product cordial labeling.
If3
k
-
1
≠
g
(
0
), we consider the following cases.
Suppose3
k
=
g
(
0
)
+
1. If k
≤
m, we change the label of u
1 to 1 and the label of u
n
+
1 to 0. If k
≥
m
+
1, we change the label of u
k to 1 and the label of u
k
+
1 to 0. In both possibilities, we get g
(
0
)
=
g
(
1
), and f is a total product cordial labeling.
Suppose3
k
=
g
(
0
)
+
2. If k
≤
m, we change the label of u
1 to 1 and the label of u
n to 0. If k
≥
m
+
1, we change the label of u
1 to 1 and the label of u
n
+
1 to 0. In both possibilities above, we get g
(
0
)
=
g
(
1
), and f is a total product cordial labeling.
Case
2 (
n
-
m
is odd). A total product cordial labeling gives 3
k
-
1
≤
g
(
0
)
≠
g
(
1
)
=
3
k. Define f
(
u
i
)
=
0 for i
∈
{
1,2
,
…
,
k
} and f
(
u
i
)
=
1 for i
∈
{
k
+
1
,
k
+
2
,
…
,
n
+
1
} such that 3
k
-
1
≤
g
(
0
)
≤
3
k
+
1.
If3
k
-
1
=
g
(
0
) (or 3
k
=
g
(
0
)), then 3
k
=
g
(
1
) (or 3
k
-
1
=
g
(
1
)), and f is a total product cordial labeling.
If3
k
+
1
=
g
(
0
). We change the label of u
1 to 1 so that g
(
0
) reduces by 1 or by 2. We then get 3
k
-
1
≤
g
(
0
)
≤
3
k, and f is a total product cordial labeling.
The proof is thus complete.Lemma 6.
For[
n
+
1
/
2
]
<
m
≤
n
-
1, P
n
+
1
m is a total product cordial graph.Proof.
Observe thatd
(
u
i
)
=
2 for i
∈
{
1
,
n
-
m
+
2
,
n
-
m
+
3
,
…
,
m
,
n
+
1
} and d
(
u
i
)
=
3 for i
∈
{
2,3
,
…
,
n
-
m
+
1
,
m
+
1
,
m
+
2
,
…
,
n
}. Note that if n
+
1
=
2
m, then d
(
u
i
)
=
2 if and only if i
=
1
,
n
+
1.
Case
1 (
n
-
m
is even). A total product cordial labeling gives g
(
0
)
=
g
(
1
)
=
3
k. Define f
(
u
i
)
=
0 for i
∈
{
1,2
,
…
,
k
} and f
(
u
i
)
=
1 for i
∈
{
k
+
1
,
k
+
2
,
…
,
n
+
1
} such that 3
k
-
2
≤
g
(
0
)
≤
3
k.
If3
k
=
g
(
0
), we get g
(
0
)
=
g
(
1
); then f is a total product cordial labeling.
If3
k
-
1
=
g
(
0
), then we consider the following cases.(1)
Ifd
(
u
k
)
=
2, we change the label of u
k
+
1 to 0 and the label of u
k to 1; g
(
0
) is increased by 1; then g
(
0
)
=
3
k
=
g
(
1
); then f is a total product cordial labeling.
(2)
Ifd
(
u
k
)
=
3, consider the following.
(a)
Ifd
(
u
k
+
1
)
=
2. We change the label of u
k to 1, because vertex u
k is adjacent to vertex u
n
+
1, so we define f
(
u
n
+
1
)
=
0, f
(
u
i
)
=
1 for k
+
1
≤
i
≤
n; g
(
0
) is increased by 1; then g
(
0
)
=
3
k
=
g
(
1
); then f is a total product cordial labeling.
(b)
Ifd
(
u
k
+
1
)
=
3, use the procedure in the proof of Lemma 5; we can obtain a total product cordial labeling.
If3
k
-
1
=
g
(
0
)
+
1, we consider the following cases.(1)
Ifd
(
u
k
)
=
2, we change the label of u
k
+
1 to 0; g
(
0
) is increased by 2; then g
(
0
)
=
3
k
=
g
(
1
). Hence, f is a total product cordial labeling.
(2)
Ifd
(
u
k
)
=
3, consider the following.
(a)
Ifd
(
u
k
+
1
)
=
2, we change the label of u
k
+
1 to 0; then g
(
0
)
=
3
k
=
g
(
1
).
(b)
Ifd
(
u
k
+
1
)
=
3, use the procedure in the proof of Lemma 5, and we can obtain a total product cordial labeling.
Case
2 (
n
-
m
is odd). A total product cordial labeling gives 3
k
-
1
≤
g
(
0
)
≠
g
(
1
)
=
3
k. Define f
(
u
i
)
=
0 for for i
∈
{
1,2
,
…
,
k
} and f
(
u
i
)
=
1 for i
∈
{
k
+
1
,
k
+
2
,
…
,
n
+
1
} such that 3
k
-
1
≤
g
(
0
)
≤
3
k
+
1.
If3
k
-
1
=
g
(
0
) (or 3
k
=
g
(
0
)), then 3
k
=
g
(
1
) (or 3
k
-
1
=
g
(
1
)), and f is a total product cordial labeling.
If3
k
+
1
=
g
(
0
), we change the label of u
1 to 1 so that g
(
0
) reduces by 1 or by 2. We then get 3
k
-
1
≤
g
(
0
)
≤
3
k, and f is a total product cordial labeling.
The proof is thus complete.Overall, we have the following.Theorem 7.
P
n
+
1
m
(
2
≤
m
≤
n
) is a total product cordial graph.


## 3. Product Cordial Labeling

Whenm
=
n, P
n
+
1
n is cycle C
n
+
1 and is product cordial if and only if n
<
4; and P
n
+
1
2 if and only if n is even is product cordial [1]. Hence, we discuss the product cordiality of P
n
+
1
m for 3
≤
m
<
n.Lemma 8.
InP
n
+
1
m, if d
(
u
i
)
=
2 for i
≠
1
,
n
+
1, then the number of these vertices has the same parity with n
+
1, and these vertices induce a path P
2
m
-
n
-
1 in the subgraph P
n
+
1.Proof.
Supposed
(
u
i
)
=
2 for i
≠
1
,
n
+
1; then m
>
[
n
+
1
/
2
]. This implies that n
-
m
+
2
≤
i
≤
m. So, the number of these vertices is 2
m
-
n
-
1 which has the same parity with n
+
1 and induce a path P
2
m
-
n
-
1 in the subgraph P
n
+
1.
The proof is thus complete.Lemma 9.
In a product cordial labeling ofP
n
+
1
m, if min
⁡
{
e
f
*
(
0
)
} is attained, then one has that all the 0-vertices induce a path or are a disjoint union of two paths in the subgraph P
n
+
1.Proof.
Note that if a vertex is labeled 0, then all the incident edges must be labeled 0. Supposemin
⁡
{
e
f
*
(
0
)
} has been attained. Let v
f
(
0
)
=
k; it is clear that the minimum number of 0-edges in the path P
n
+
1 is k or k
+
1 if and only if the 0-vertices induced a path or are a disjoint union of two paths in the subgraph P
n
+
1.
The proof is thus complete.Lemma 10.
When2
<
m
≤
[
n
+
1
/
2
], P
n
+
1
m is not product cordial.Proof.
From Lemma9 we know if P
n
+
1
m is product cordial, when v
f
(
0
) is got, then we get min
⁡
{
e
f
*
(
0
)
} only when all the 0-vertices induce a path or are a disjoint union of two paths in the subgraph P
n
+
1. Now, we prove that P
n
+
1
m is not product cordial when 2
<
m
≤
[
n
+
1
/
2
]. Because d
(
u
i
)
>
2 for i
≠
1
,
n
+
1, we consider the following two cases.(1)
n is odd; suppose P
n
+
1
m is product cordial; then v
f
(
0
)
=
n
+
1
/
2; begin with u
1 (or u
n
+
1), and we choose n
+
1
/
2 vertices and define their labels with 0 successively such that e
f
*
(
0
) is minimum; min
⁡
{
e
f
*
(
0
)
}
=
2
+
2
+
⋯
+
2
=
n
+
1, but max
⁡
{
e
f
*
(
1
)
}
<
n
-
1, e
f
*
(
0
)
≠
e
f
*
(
1
), a contradiction. Hence, f is not a product cordial labeling.
(2)
n is even; suppose P
n
+
1
m is product cordial, and then min
⁡
{
v
f
(
0
)
}
=
n
/
2; similarly, we can get min
⁡
{
e
f
*
(
0
)
}
=
n, but max
⁡
{
e
f
*
(
1
)
}
<
n
-
1, contradiction. Hence, f is not a product cordial labeling.
The proof is thus complete.When[
n
+
1
/
2
]
<
m
<
n, in P
n
+
1
m, there exist vertices u
i such that i
≠
1
,
n
+
1 and d
(
u
i
)
=
2. Let the number of such vertices be l
-
2, and then l
=
2
m
-
n
+
1
>
2.Lemma 11.
When[
n
+
1
/
2
]
<
m
<
n, P
n
+
1
m is not product cordial in the follow cases.(1)
n is odd:
(a)
m is even satisfying
(i)
l
=
n
+
1
/
2, n
=
11, m
=
8;
(ii)
n
+
1
/
2
-
l
≡
0,2
(
m
o
d
4
)
(
n
+
1
/
2
-
l
>
0
), n
+
1
/
2
<
m
<
min
⁡
{
n
+
5
/
2
,
3
n
-
1
/
4
};
(iii)
n
+
1
/
2
-
l
≡
1,3
(
m
o
d
4
)
(
n
+
1
/
2
-
l
>
0
), n
+
1
/
2
<
m
<
min
⁡
{
n
+
7
/
2
,
3
n
-
1
/
4
};
(iv)
l
-
n
+
1
/
2
>
0, n
=
5, m
=
4.
(b)
m is odd satisfying
(i)
l
=
n
+
1
/
2, n
=
7, m
=
5; n
=
15, m
=
11;
(ii)
n
+
1
/
2
-
l
≡
0,2
(
m
o
d
4
)
(
n
+
1
/
2
-
l
>
0
), n
+
1
/
2
<
m
<
min
⁡
{
n
+
7
/
2
,
3
n
-
1
/
4
};
(iii)
n
+
1
/
2
-
l
≡
1,3
(
m
o
d
4
)
(
n
+
1
/
2
-
l
>
0
), n
+
1
/
2
<
m
<
min
⁡
{
n
+
9
/
2
,
3
n
-
1
/
4
};
(iv)
l
-
n
+
1
/
2
>
0, n
=
9, m
=
7.
(2)
n is even:
(a)
m is even satisfying
(i)
l
=
n
/
2, n
=
6, m
=
4;
(ii)
n
/
2
-
l
≡
0,2
(
m
o
d
4
)
(
n
+
1
/
2
-
l
>
0
), n
/
2
<
m
<
min
⁡
{
n
+
2
/
2
,
3
n
-
2
/
4
};
(iii)
n
/
2
-
l
≡
1,3
(
m
o
d
4
)
(
n
+
1
/
2
-
l
>
0
), n
/
2
<
m
<
min
⁡
{
n
+
4
/
2
,
3
n
-
2
/
4
}.
(b)
m is odd:
(i)
l
=
n
/
2, n
=
10, m
=
7;
(ii)
n
/
2
-
l
≡
0,2
(
m
o
d
4
)
(
n
+
1
/
2
-
l
>
0
), n
/
2
<
m
<
min
⁡
{
n
+
4
/
2
,
3
n
-
2
/
4
};
(iii)
n
/
2
-
l
≡
1,3
(
m
o
d
4
)
(
n
+
1
/
2
-
l
>
0
), n
/
2
<
m
<
min
⁡
{
n
+
6
/
2
,
3
n
-
2
/
4
}.Proof.
In Figure2, the hollow circles denote the vertices that d
=
2; the solid circles denote the vertices that d
=
3. In any product cordial labeling, if v
(
0
)
≤
l
-
2, we first label vertices u
i
,
n
-
m
+
2
≤
i
≤
m consecutively. Otherwise, we first label vertices u
1 and u
n
+
1 before labeling the remaining vertices according to the order given by the numeral 1,2
,
3
,
…. The value min
⁡
{
e
f
*
(
0
)
} is then attained.
Case
1 (
n
is odd)
Subcase
1.1 (
m
is even). We consider three cases.(1)
Considerl
=
n
+
1
/
2. Since l
=
2
m
-
n
+
1, we have m
=
3
n
-
1
/
4, m
>
n
+
1
/
2, and we get n
>
3. We label all the n
+
1
/
2 vertices with d
=
2 by 0; then min
⁡
{
e
f
*
(
0
)
}
=
l
+
3. If l
+
3
>
n
-
m
/
2
+
1, we get m
>
n
-
5 so that 3
<
n
<
19. Since l is even, we must have n
=
11, m
=
8. Consequently, P
12
8 is not product cordial. Hence, (i) holds.
(2)
Considern
+
1
/
2
-
l
=
k
>
0, and then m
<
3
n
-
1
/
4. We consider the following four subcases.
(2.1)
k
≡
0
(
mod
⁡
4
). We let the labels of n
+
1
/
2 vertices be 0, and then min
⁡
{
e
f
*
(
0
)
}
=
l
+
2
+
6
×
k
/
4. If l
+
2
+
6
×
k
/
4
>
n
-
m
/
2
+
1, then m
<
n
+
5
/
2. Hence, when n
+
1
/
2
<
m
<
min
⁡
{
n
+
5
/
2
,
3
n
-
1
/
4
}, P
n
+
1
m is not product cordial.
(2.2)
k
≡
1
(
mod
⁡
4
). We let the labels of n
+
1
/
2 vertices be 0, and then min
⁡
{
e
f
*
(
0
)
}
=
l
+
4
+
6
×
k
-
1
/
4. If l
+
4
+
6
×
k
-
1
/
4
>
n
-
m
/
2
+
1, then m
<
n
+
7
/
2. Hence, when n
+
1
/
2
<
m
<
min
⁡
{
n
+
7
/
2
,
3
n
-
1
/
4
}, P
n
+
1
m is not product cordial.
(2.3)
k
≡
2
(
mod
⁡
4
). We let the labels of n
+
1
/
2 vertices be 0, and then min
⁡
{
e
f
*
(
0
)
}
=
l
+
5
+
6
×
k
-
2
/
4. If l
+
5
+
6
×
k
-
2
/
4
>
n
-
m
/
2
+
1, then m
<
n
+
5
/
2. Hence, when n
+
1
/
2
<
m
<
min
⁡
{
n
+
5
/
2
,
3
n
-
1
/
4
}, P
n
+
1
m is not product cordial.
(2.4)
k
≡
3
(
mod
⁡
4
). We let the labels of n
+
1
/
2 vertices be 0, and then min
⁡
{
e
f
*
(
0
)
}
=
l
+
7
+
6
×
k
-
3
/
4. If l
+
7
+
6
×
k
-
3
/
4
>
n
-
m
/
2
+
1, then m
<
n
+
7
/
2. Hence, when n
+
1
/
2
<
m
<
min
⁡
{
n
+
7
/
2
,
3
n
-
1
/
4
}, P
n
+
1
m is not product cordial.
Hence, (ii) and (iii) hold.(3)
Considern
+
1
/
2
-
l
<
0. If l
-
n
+
1
/
2
=
1, then we let the labels of n
+
1
/
2 vertices be 0, and min
⁡
{
e
f
*
(
0
)
}
=
n
+
1
/
2
+
2; suppose n
+
1
/
2
+
2
>
n
-
m
-
2
/
2, then we have m
>
n
-
3, according to the parity of n
,
m, have m
=
n
-
1, because l
-
n
+
1
/
2
=
1 and l
=
2
m
-
n
+
1, and have n
=
5, m
=
4. If l
-
n
+
1
/
2
>
1, then let the labels of n
+
1
/
2 vertices be 0; min
⁡
{
e
f
*
(
0
)
}
=
n
+
1
/
2
+
1, and suppose n
+
1
/
2
+
2
>
n
-
m
-
1
/
2, m
>
n
-
1, contradiction.
Hence, (iv) holds.
Subcase
1.2 (
m
is odd). We consider three cases.(1)
Considerl
=
n
+
1
/
2. Since l
=
2
m
-
n
+
1, we have m
=
3
n
-
1
/
4, m
>
n
+
1
/
2; hence, we get n
>
3. We let the labels of n
+
1
/
2 vertices be 0, and then min
⁡
{
e
f
*
(
0
)
}
=
l
+
3. If l
+
3
>
n
-
m
-
1
/
2, then m
>
n
-
6. Hence, 3
<
n
<
23. Since l is even, hence, only n
=
7, m
=
5; n
=
15, m
=
11 satisfy conditions that n is odd, 3
<
n
<
13, m
=
3
n
-
1
/
4, and m is odd. Hence, (i) holds.
(2)
Considern
+
1
/
2
-
l
=
k
>
0. We have m
<
3
n
-
1
/
4, and we consider the following four subcases.
(2.1)
k
≡
0
(
mod
⁡
4
). We let the labels of n
+
1
/
2 vertices be 0; then min
⁡
{
e
f
*
(
0
)
}
=
l
+
2
+
6
×
k
/
4. If l
+
2
+
6
×
k
/
4
>
n
-
m
-
1
/
2, then m
<
n
+
7
/
2. Hence, when n
+
1
/
2
<
m
<
min
⁡
{
n
+
7
/
2
,
3
n
-
1
/
4
}, P
n
+
1
m is not product cordial.
(2.2)
k
≡
1
(
mod
⁡
4
). We let the labels of n
+
1
/
2 vertices be 0; then min
⁡
{
e
f
*
(
0
)
}
=
l
+
4
+
6
×
k
-
1
/
4. If l
+
4
+
6
×
k
-
1
/
4
>
n
-
m
-
1
/
2, then m
<
n
+
9
/
2. Hence, when n
+
1
/
2
<
m
<
min
⁡
{
n
+
9
/
2
,
3
n
-
1
/
4
}, P
n
+
1
m is not product cordial.
(2.3)
k
≡
2
(
mod
⁡
4
). We let the labels of n
+
1
/
2 vertices be 0; then min
⁡
{
e
f
*
(
0
)
}
=
l
+
5
+
6
×
k
-
2
/
4. If l
+
5
+
6
×
k
-
2
/
4
>
n
-
m
-
1
/
2, then m
<
n
+
7
/
2. Hence, when n
+
1
/
2
<
m
<
min
⁡
{
n
+
7
/
2
,
3
n
-
1
/
4
}, P
n
+
1
m is not product cordial.
(2.4)
k
≡
3
(
mod
⁡
4
). We let the labels of n
+
1
/
2 vertices be 0; then min
⁡
{
e
f
*
(
0
)
}
=
l
+
7
+
6
×
k
-
3
/
4. If l
+
7
+
6
×
k
-
3
/
4
>
n
-
m
-
1
/
2, then m
<
n
+
9
/
2. Hence, when n
+
1
/
2
<
m
<
min
⁡
{
n
+
9
/
2
,
3
n
-
1
/
4
}, P
n
+
1
m is not product cordial.
Hence, (ii) and (iii) hold.(3)
Considern
+
1
/
2
-
l
<
0. If l
-
n
+
1
/
2
=
1, then we let n
+
1
/
2 vertex labels be 0, and min
⁡
{
e
f
*
(
0
)
}
=
n
+
1
/
2
+
2; suppose n
+
1
/
2
+
2
>
n
-
m
-
1
/
2, then we have m
>
n
-
4, according to the odd-even parity of n
,
m, have m
=
n
-
2, because l
-
n
+
1
/
2
=
1 and l
=
2
m
-
n
+
1, and have m
=
3
n
+
1
/
4, and therefore, n
=
9, m
=
7; if l
-
n
+
1
/
2
>
1, then let the labels of n
+
1
/
2 vertices be 0, and min
⁡
{
e
f
*
(
0
)
}
=
n
+
1
/
2
+
1; suppose n
+
1
/
2
+
1
>
n
-
m
-
1
/
2, m
>
n
-
2, contradiction.
Hence, (iv) holds.
Case
2 (
n
is even)
Subcase
2.1 (
m
is even)
(1)
Considerl
=
n
/
2. Since l
=
2
m
-
n
+
1, we have m
=
3
n
-
2
/
4, m
>
n
/
2 and hence have n
>
4. We let n
/
2 vertices be labeled by 0; then min
⁡
{
e
f
*
(
0
)
}
=
l
+
3. If l
+
3
>
n
-
m
/
2
+
1, m
>
n
-
4, then 4
<
n
<
14. Since l is even, hence, only n
=
6, m
=
4 satisfy conditions that n is odd, 4
<
n
<
14, m
=
3
n
-
2
/
4, and m is even. Hence, (i) holds.
(2)
Considern
/
2
-
l
=
k
>
0. We have m
<
3
n
-
2
/
4, and we consider the following four cases.
(2.1)
k
≡
0
(
mod
⁡
4
). We let the labels of n
/
2 vertices be 0, and then min
⁡
{
e
f
*
(
0
)
}
=
l
+
2
+
6
×
k
/
4. If l
+
2
+
6
×
k
/
4
>
n
-
m
/
2
+
1, then m
<
n
+
2
/
2. Hence, when n
/
2
<
m
<
min
⁡
{
n
+
2
/
2
,
3
n
-
2
/
4
}, P
n
+
1
m is not product cordial.
(2.2)
k
≡
1
(
mod
⁡
4
). We let the labels of n
/
2 vertices be 0, and then min
⁡
{
e
f
*
(
0
)
}
=
l
+
4
+
6
×
k
-
1
/
4. If l
+
4
+
6
×
k
-
1
/
4
>
n
-
m
/
2
+
1, then m
<
n
+
4
/
2. Hence, when n
/
2
<
m
<
min
⁡
{
n
+
4
/
2
,
3
n
-
2
/
4
}, P
n
+
1
m is not product cordial.
(2.3)
k
≡
2
(
mod
⁡
4
). We let the labels of n
/
2 vertices be 0, and then min
⁡
{
e
f
*
(
0
)
}
=
l
+
5
+
6
×
k
-
2
/
4. If l
+
5
+
6
×
k
-
2
/
4
>
n
-
m
/
2
+
1, then m
<
n
+
2
/
2. Hence, when n
/
2
<
m
<
min
⁡
{
n
+
2
/
2
,
3
n
-
2
/
4
}, P
n
+
1
m is not product cordial.
(2.4)
k
≡
3
(
mod
⁡
4
). We let the labels of n
/
2 vertices be 0, and then min
⁡
{
e
f
*
(
0
)
}
=
l
+
7
+
6
×
k
-
3
/
4. If l
+
7
+
6
×
k
-
3
/
4
>
n
-
m
/
2
+
1, then m
<
n
+
4
/
2. Hence, when n
/
2
<
m
<
min
⁡
{
n
+
4
/
2
,
3
n
-
2
/
4
}, P
n
+
1
m is not product cordial.
Hence, (ii) and (iii) hold.(3)
Considern
/
2
-
l
<
0. If l
-
n
/
2
=
1, we let n
/
2 vertices be labeled by 0, and min
⁡
{
e
f
*
(
0
)
}
=
n
/
2
+
2; suppose n
/
2
+
2
>
n
-
m
-
2
/
2, m
>
n
-
2, according to the odd-even parity of n
,
m, contradiction; if l
-
n
+
1
/
2
>
1, let n
/
2 vertices be labeled by 0; min
⁡
{
e
f
*
(
0
)
}
=
n
/
2
+
1; suppose n
/
2
+
1
>
n
-
m
-
2
/
2, m
>
n, contradiction.
Hence, (iv) holds.
Subcase
2.2 (
m
is odd)
(1)
Considerl
=
n
/
2. Since l
=
2
m
-
n
+
1, then m
=
3
n
-
2
/
4, m
>
n
/
2, and hence n
>
4. We let n
/
2 vertices be labeled by 0; then min
⁡
{
e
f
*
(
0
)
}
=
l
+
3. If l
+
3
>
n
-
m
-
1
/
2, m
>
n
-
5, so 4
<
n
<
18, because l is odd; hence, only n
=
10, m
=
7 satisfy conditions that n is odd, 3
<
n
<
13, m
=
3
n
-
1
/
4, and m is odd. Hence, (i) holds.
(2)
Considern
/
2
-
l
=
k
>
0. We have m
<
3
n
-
2
/
4, and we consider the following four cases.
(2.1)
k
≡
0
(
mod
⁡
4
). We let n
/
2 vertices be labeled by 0; then min
⁡
{
e
f
*
(
0
)
}
=
l
+
2
+
6
×
k
/
4. If l
+
2
+
6
×
k
/
4
>
n
-
m
-
1
/
2, then m
<
n
+
4
/
2. Hence, when n
/
2
<
m
<
min
⁡
{
n
+
4
/
2
,
3
n
-
2
/
4
}, P
n
+
1
m is not product cordial.
(2.2)
k
≡
1
(
mod
⁡
4
). We let n
/
2 vertices be labeled by 0; then min
⁡
{
e
f
*
(
0
)
}
=
l
+
4
+
6
×
k
-
1
/
4. If l
+
4
+
6
×
k
-
1
/
4
>
n
-
m
-
1
/
2, then m
<
n
+
6
/
2. Hence, when n
/
2
<
m
<
min
⁡
{
n
+
6
/
2
,
3
n
-
2
/
4
}, P
n
+
1
m is not product cordial.
(2.3)
k
≡
2
(
mod
⁡
4
). We let n
/
2 vertices be labeled by 0; then min
⁡
{
e
f
*
(
0
)
}
=
l
+
5
+
6
×
k
-
2
/
4. If l
+
5
+
6
×
k
-
2
/
4
>
n
-
m
-
1
/
2, then m
<
n
+
4
/
2. Hence, when n
/
2
<
m
<
min
⁡
{
n
+
4
/
2
,
3
n
-
2
/
4
}, P
n
+
1
m is not product cordial.
(2.4)
k
≡
3
(
mod
⁡
4
). We let n
/
2 vertices be labeled by 0; then min
⁡
{
e
f
*
(
0
)
}
=
l
+
7
+
6
×
k
-
3
/
4. If l
+
7
+
6
×
k
-
3
/
4
>
n
-
m
-
1
/
2, then m
<
n
+
6
/
2. Hence, when n
/
2
<
m
<
min
⁡
{
n
+
6
/
2
,
3
n
-
2
/
4
}, P
n
+
1
m is not product cordial.
Hence, (ii) and (iii) hold.(3)
Considern
/
2
-
l
<
0. If l
-
n
/
2
=
1, we let n
/
2 vertices be labeled by 0; min
⁡
{
e
f
*
(
0
)
}
=
n
/
2
+
2; suppose n
/
2
+
2
>
n
-
m
-
1
/
2, and then m
>
n
-
3, according to the parity of n
,
m, contradiction; if l
-
n
/
2
>
1, we let n
/
2 vertices be labeled by 0; then min
⁡
{
e
f
*
(
0
)
}
=
n
/
2
+
1, and suppose n
/
2
+
1
>
n
-
m
-
1
/
2, m
>
n
-
1, contradiction. Hence, (iv) holds.
The proof is thus complete.Figure 2
1, 2, 3, and so forth denote the order of vertices withd
=
3 being labeled 0.Lemma 12.
When[
n
+
1
/
2
]
<
m
<
n and n
,
m do not belong to the cases of Lemma 11, P
n
+
1
m is product cordial.Proof.
We prove the conclusion is right whenn is odd and m is even, and the proofs of the other cases are similar to the proof of the facts that n is odd and m is even. Suppose n
,
m do not belong to the conditions of Lemma 11; let n
+
1
/
2 vertices be labeled by 0, and then min
⁡
{
e
f
*
(
0
)
}
≤
n
-
m
-
2
/
2. If min
⁡
{
e
f
*
(
0
)
}
=
n
-
m
-
2
/
2, then the conclusion is right. So, we discuss the conclusion when min
⁡
{
e
f
*
(
0
)
}
<
n
-
m
-
2
/
2. First, we define f
(
u
i
)
=
0 for 1
≤
i
≤
n
+
1
/
2 right now; e
f
*
(
0
)
>
n
-
m
-
2
/
2. From Lemma 8, we know that u
i exist for i
≠
1
,
n
+
1 with d
=
2; suppose the number of these vertices is l
-
2 and satisfy l
=
2
m
-
n
+
1
>
2. We consider the following three cases.
Case
1. Consider l
=
n
+
1
/
2, and then m
=
3
n
-
1
/
4; let the labels of vertices that d
=
2 be 0 and the labels of vertices with d
=
3 be 1; then e
f
*
(
0
)
=
n
+
1
/
2
+
3
<
n
-
m
-
2
/
2, exchanging the labels of u
m
,
u
2; then e
f
*
(
0
) is increased by 1, if e
f
*
(
0
)
<
n
-
m
-
2
/
2, exchanging the labels of u
m
-
1
,
u
3; then e
f
*
(
0
) is increased by 1, after that, because e
f
*
(
0
)
>
n
-
m
-
2
/
2 when f
(
u
i
)
=
0 for 1
≤
i
≤
n
+
1
/
2. Hence, after the above some exchanging step, e
f
*
(
0
)
=
n
-
m
-
2
/
2.
Case
2. Consider n
+
1
/
2
-
l
>
0; then m
<
3
n
-
1
/
4, and suppose n
+
1
/
2
-
l
=
k, then let the labels of vertices with d
=
2 be 0, according to the sequence illustrated by Figure 2, the k vertices with d
=
3 labeled with 0, and other vertices labeled with 1; then e
f
*
(
0
)
<
n
-
m
-
2
/
2. First exchanging the labels of u
i
,
u
j with d
=
3, the rules are(1)
i
<
n
+
1
/
2
<
j;
(2)
f
(
u
i
)
=
f
(
u
i
+
1
)
=
1, f
(
u
s
)
=
0 for s
<
i, f
(
u
j
-
1
)
=
f
(
u
j
)
=
0, f
(
u
t
)
=
1 for j
<
t
<
n
+
1.
After each exchange,e
f
*
(
0
) is increased by 1, if some exchanging is completed; e
f
*
(
0
)
=
n
-
m
-
2
/
2, and then exchange stops; when the above exchanges all are completed, e
f
*
(
0
)
<
n
-
m
-
2
/
2, and then according to the exchanges of Case 1, we can get e
f
*
(
0
)
=
n
-
m
-
2
/
2.
Case
3. Consider n
+
1
/
2
-
l
<
0, if l
=
n
+
1
/
2
+
1; let the vertices (except u
n
+
1) with d
=
2 be labeled by 0 and other vertices labeled by 1; then e
f
*
(
0
)
<
n
-
m
-
2
/
2, and according to exchanges of Case 1, we can get e
f
*
(
0
)
=
n
-
m
-
2
/
2; if l
>
n
+
1
/
2
+
1, let f
(
u
1
)
=
0, f
(
u
i
)
=
0 for i
∈
{
m
-
n
+
1
/
2
+
2
,
m
-
n
+
1
/
2
+
3
,
…
,
m
}, and according to the exchanges of Case 1, we can get e
f
*
(
0
)
=
n
-
m
-
2
/
2.
The proof is thus complete.Overall, we can get the following.Theorem 13.
P
n
+
1
m is total product cordial when n
,
m do not belong to the cases of Lemmas 10 and 11.



---

*Source: 512696-2015-01-05.xml*