The Full m Index Sets of P2×Pn

Abstract

Shiu and Kwong (2008) studied the full friendly index set of $P_2\times P_n$, which only addressed the cases where $m=0$ or 1. In this paper, we significantly extend their work by determining the full $m$ index set $M{P}_2\times P_n$ for all values of $m$. Our key approach is to utilize graph embedding and recursion methods to deduce $M{P}_2\times P_n$ for general $m$. In particular, we embed small graphs like $C_4$ and $K_2$ into $P_2\times P_n$ and apply recursive techniques to prove the main results. This work expands the scope of previous graph labeling studies and provides new insights into determining the full $m$ index set of product graphs. Given the broad range of applications for labeled graphs, this research can potentially impact fields like coding theory, communication network design, and more.

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

A graph labeling is an assignment of integers to the vertices or edges, or both. Motivated by different settings and conditions, the problems of labeling various types of graphs were raised and studied. We refer the readers to the survey paper, A dynamic survey of graph labelings by Gallian [1], in which the sheer number of research papers regarding different graph labeling methods in graph theory has been reviewed.

Let $G=VG,EG$ be a simple connected graph with the vertex set $VG$ and the edge set $EG$. Let $f$ be a function from $VG$ to ${\mathbb{Z}}_2$. For each edge $v_1{v}_2$, we assign the label $f^{\prime }{v}_1{v}_2$, where $f^{\prime }{v}_1{v}_2=f{v}_1+f{v}_2$. For $i\in {\mathbb{Z}}_2$, a vertex $u\in VG$ is called an $i$ vertex if $fu=i$. And we let $v_{f}i$ denote the number of $i$ vertices in $G$ under labeling $f$. The concepts of $i$ edge and $e_{f^{\prime }}i$ can be defined similarly. Chartrand et al. [2] introduced the concept of friendly index set. And a vertex labeling $f$ is said to be friendly if $v_{f}1-v_{f}0\le 1$.

Definition 1.

The friendly index set of $G$ is defined as$$\begin{array}{}\text{(1)}& \text{FI}G=e_{f^{\prime }}1-e_{f^{\prime }}0:f\text{\hspace{0.17em}is\hspace{0.17em}friendly\hspace{0.17em}labeling\hspace{0.17em}of\hspace{0.17em}}G.\end{array}$$

Readers can refer to the literature [3, 4] for the friendly index set of graphs if interested. Shiu and Ling [5] extended this concept to the full friendly index set.

Definition 2.

The set $\text{FFI}G=e_{f^{\prime }}1-e_{f^{\prime }}0:f\text{\hspace{0.17em}is\hspace{0.17em}friendly\hspace{0.17em}labeling\hspace{0.17em}of\hspace{0.17em}}G$ is called the full friendly index set of $G$.

A friendly labeling of a graph $G$ is also known as a bisection of $G$, which has been studied widely in the theory of graph partitions [6, 7]. According to the algorithm [8], it is NP-hard to find the maximum or minimum bisection (namely, friendly labeling with maximum or minimum 1 edge) of an arbitrary graph. There were many interesting results focusing on some specific graphs. For example, Sinha and Kaur [9] studied the full friendly index sets of $K_n,C_n,F_n,F_{2,m}$, and $P_3\times P_n$. Shiu and his coauthors determined the full friendly index sets of cylinder graphs [10], some permutation Petersen graphs [11], slender and flat cylinder graphs [12], and $P_2\times P_n$ [13]. Gao et al. [14] deduced $\text{FFI}G$ of a family of cubic graphs, which are full vertices blow-up of $C_m$ with $K_{\mathrm{1,1,2}}$.

In this paper, we generalize the concept of the full friendly index set to the following, which we call the full $m$ index set.

Definition 3.

The full $m$ index set of $G,MG$ is defined as the set$$\begin{array}{}\text{(2)}& MG=e_{f^{\prime }}1-e_{f^{\prime }}0:v_{f}1-v_{f}0=m,0\le m<VG.\end{array}$$

According to the above definition, when $m=0$ or $m=1$, the full $m$ index set of a graph is its full friendly index set.

Lemma 4.

Let $a_{m}G=e_{f^{\prime }}1:v_{f}1-v_{f}0=m,0\le m<VG$. Then, the full $m$ index set of $G$ is defined as$$\begin{array}{}\text{(3)}& MG=2i-EG:i\in a_{m}G.\end{array}$$

Proof.

Note that the conditions $v_{f}1-v_{f}0=m$ and $v_{f}0-v_{f}1=m$ are symmetric, we find that $e_{f^{\prime }}1$ is equal under both conditions. Then, $e_{f^{\prime }}1-e_{f^{\prime }}0=2e_{f^{\prime }}1-EG$. Then, we have $MG=2e_{f^{\prime }}1-EG:v_{f}1-v_{f}0=m,0\le m<VG$. According to the definition of $a_{m}G$, we know that $MG=2i-EG:i\in a_{m}G$. □

Thus, we only need to compute the value of $e_{f^{\prime }}1$.

2. Preliminaries

We now discuss the full $m$ index set of $P_2\times P_k$ for some specific values of $k$. We name the vertices on the two paths as $u_1,u_2,\dots ,u_k$ and $v_1,v_2,\dots ,v_k$, and Figure 1 represent the graph $P_2\times P_{2n}$. We shall call the square $u_i{v}_i{v}_{i+1}{u}_{i+1}$ the $i$ th square, the edge $u_i{v}_i$ the $i$ th vertical edge.

[figure(s) omitted; refer to PDF]

We omit the subscripts in $v_{f}i$ and $e_{f^{\prime }}i$ for simplicity without causing confusion. In the remaining of the paper, if not specifically stated, only the vertices labeled 1 are listed and those not listed are labeled 0. For $v1-v0=m$, we denote $ei$ as $e_{m}i$.

Consider the graph $P_2\times P_k$. Let $f$ be any vertex labeling such that $v1-v0=m$, since $v1+v0=2k$. Thus, we know $v1=k+m/2$. Note that $v1$ is a positive integer, which implies that $m$ is an even integer.

First, we give some examples of $P_2\times P_k$ in order to prove the following theorem.

Example 1.

Consider the graph $P_2\times P_{2n}$, where $v1-v0=2$.

(1) For $f{u}_i=\mathrm{1,1}\le i\le n,f{v}_j=\mathrm{1,1}\le j\le n+1,e_{2}1=3$

(2) For $f{u}_i=f{v}_j=\mathrm{1,1}\le i,j\le n,f{v}_{2n}=1,e_{2}1=4$

(3) For $f{u}_1=f{u}_3=\cdots =f{u}_{2n-1}=f{u}_{2n}=1$, $f{v}_2=f{v}_4=\cdots =f{v}_{2n}=1,e_{2}1=6n-4$

(4) For $f{u}_1=f{u}_3=\cdots =f{u}_{2n-3}=f{u}_{2n}=1$, $f{v}_2=f{v}_4=\cdots =f{v}_{2n-2}=f{v}_{2n-1}=f{v}_{2n}=1$

For Example 1, we only give the specific notation of (4).

The labeled graph of Example 1 (4) is shown in the following, where the solid points represent vertices labeled 1, the hollow points represent vertices labeled 0, the thick line represents 1 edge, and the thin line represents 0 edge.

Thus, from Figure 1, it is clearly to see that $e_{2}1=6n-6$.

Example 2.

Consider the graph $P_2\times P_{2n}$, where $v1-v0=4$.

(1) For $f{u}_i=f{v}_j=1$, $1\le i,j\le n+1,e_{4}1=2$

(2) For $f{u}_1=f{u}_3=\cdots =f{u}_{2n-1}=f{u}_{2n}=1$, $f{v}_1=f{v}_2=f{v}_4=\cdots =f{v}_{2n}=1,e_{4}1=6n-6$

Example 3.

Consider the graph $P_2\times P_{2n}$, where $v1-v0=6$.

(1) For $f{u}_i=1,i\in n-\mathrm{1,2}n,f{v}_j=1,j\in n-\mathrm{1,2}n-1,e_{6}1=4$

Example 4.

Consider the graph $P_2\times P_{2n}$, where $v1-v0=4n-2$.

(1) For $f{u}_i=f{v}_j=\mathrm{1,1}\le i\le 2n-\mathrm{1,1}\le j\le 2n,e_{4n-2}1=2$

(2) For $f{u}_i=f{v}_j=\mathrm{1,1}\le i\le 2n,3\le j\le 2n;f{v}_1=1,e_{4n-2}1=3$

Example 5.

Consider the graph $P_2\times P_{2n}$, where $v1-v0=4n-4$.

(1) For $f{u}_i=f{v}_j=\mathrm{1,1}\le i,j\le 2n-1,e_{4n-4}1=2$

(2) For $f{u}_i=f{v}_j=\mathrm{1,3}\le i\le 2n,1\le j\le 2n,e_{4n-4}1=3$

(3) For $f{u}_i=f{v}_j=\mathrm{1,3}\le i,j\le 2n;f{u}_1=f{v}_1=1,e_{4n-4}1=4$

(4) For $f{u}_i=f{v}_j=\mathrm{1,4}\le i\le 2n,1\le j\le 2n;f{u}_2=1,e_{4n-4}1=5$

(5) For $f{u}_i=f{v}_j=\mathrm{1,4}\le i\le 2n,3\le j\le 2n;f{u}_1=f{u}_2=f{v}_1=1,e_{4n-4}1=6$

Example 6.

Consider the graph $P_2\times P_{2n+1}$, where $v1-v0=4n$.

(1) For $f{u}_i=f{v}_j=\mathrm{1,1}\le i\le 2n,1\le j\le 2n+1,e_{4n}1=2$

(2) For $f{u}_i=f{v}_j=\mathrm{1,1}\le i\le 2n+\mathrm{1,1}\le j\le 2n-1;f{v}_{2n+1}=1,e_{4n}1=3$

Example 7.

Consider the graph $P_2\times P_{2n+1}$, where $v1-v0=4n-2$.

(1) For $f{u}_i=f{v}_j=\mathrm{1,1}\le i,j\le 2n,e_{4n-2}1=2$

(2) For $f{u}_i=f{v}_j=\mathrm{1,3}\le i\le 2n+\mathrm{1,1}\le j\le 2n+1,e_{4n-2}1=3$

(3) For $f{u}_i=f{v}_j=\mathrm{1,3}\le i,j\le 2n+1;f{u}_1=f{v}_1=1,e_{4n-2}1=4$

(4) For $f{u}_i=f{v}_j=\mathrm{1,4}\le i\le 2n+\mathrm{1,1}\le j\le 2n+1;f{u}_2=1,e_{4n-2}1=5$

(5) For $f{u}_i=f{v}_j=\mathrm{1,4}\le i\le 2n+\mathrm{1,3}\le j\le 2n+1;f{u}_1=f{u}_2=f{v}_1=1,e_{4n-2}1=6$

Next, we introduce some relevant definitions.

Definition 5.

Let $a$ be an integer, if $e1=a$ under the vertex labeling $f$ of the graph $G$, we denote the labeled graph as $Ga$. For convenience, we use $\begin{array}{c}fu\\ fv\end{array}$ and $\begin{array}{cc}f{u}_i& f{u}_{i+1}\\ f{v}_i& f{v}_{i+1}\end{array}$ to denote the labeled subgraphs $K_2=\text{uv}$ and $C_4=u_i{v}_i{v}_{i+1}{u}_{i+1}{u}_i$, respectively. Define $u_i{v}_i{v}_{i+1}{u}_{i+1}{u}_i$ as a $C_4$ square of $P_2\times P_n$, where $1\le i\le n-1$.

Definition 6.

$K_2-\text{embedding}$. Given the labeled graph $Ga$ of $P_2\times P_n$, we can replace the two edges $u_i{u}_{i+1}$ and $v_i{v}_{i+1}$ with paths $u_i\mathrm{x}{\mathrm{u}}_{i+1}$ and $v_i\mathrm{y}{\mathrm{v}}_{i+1}$ of length 2 and joint $x$ and $y$. This process is called a $K_2$-embedding, which results in a new labeled graph $Gb=Ga\oplus K_2$.

Definition 7.

$C_4-\text{embedding}$. Given the labeled graph $Ga$ of $P_2\times P_n$, we can replace the two edges $u_i{u}_{i+1}$ and $v_i{v}_{i+1}$ with paths $u_i\text{xy}{\mathrm{u}}_{i+1}$ and $v_i{x}^{\prime }{y}^{\prime }{v}_{i+1}$ of length 3 and jointing $x,x^{\prime }$ and $y,y^{\prime }$. This process is called a $C_4$-embedding, which results in a new labeled graph $Gb=Ga\oplus C_4$.

In the following discussion, all $K_2$-embeddings or $C_4$-embeddings on $P_2\times P_n$ are embeddings for edges $u_i{u}_{i+1}$ and $v_i{v}_{i+1}$ of $P_2\times P_n$, where $i\in 1,\dots ,n-1$.

For the convenience of description, some substructures are given below.

Let $A_i$ denote a labeled $C_4$-square, where $A_1=\begin{array}{cc}1& 1\\ 1& 1\end{array},A_2=\begin{array}{cc}1& 1\\ 1& 0\end{array},A_3=\begin{array}{cc}1& 1\\ 0& 0\end{array},A_4=\begin{array}{cc}1& 0\\ 0& 1\end{array},A_5=\begin{array}{cc}0& 1\\ 0& 1\end{array}$. And let $e^{\prime }1$ represent the number of 1 edge changes after the square is embedded. Write the different labels of $C_4$ as $B_1=\begin{array}{cc}0& 1\\ 1& 1\end{array}$, $B_2=\begin{array}{cc}1& 0\\ 1& 1\end{array}$, $B_3=\begin{array}{cc}1& 1\\ 0& 1\end{array}$, and $B_4=\begin{array}{cc}1& 1\\ 1& 0\end{array}$.

We make a $B_j$-embedding in $A_i$, denoted by $A_i\oplus B_j$, where $i\in \mathrm{1,2,3,4,5},j\in \mathrm{1,2,3,4}$. $e^{\prime }{A}_i\oplus B_j$ represents the number of 1 edge changes after embedding.

Thus, $e^{\prime }{A}_i\oplus B_j$ obtained after embedding is shown in Table 1.

Table 1

$e^{\prime }{A}_i\oplus B_j$ after embedding.

	$B_1$	$B_2$	$B_3$	$B_4$
$A_1$	3	3	3	3
$A_2$	3	3	3	1
$A_3$	5	5	3	3
$A_4$	3	1	3	3
$A_5$	1	3	1	3

From the results of Table 1, the Lemmas 8 and 9 are obtained.

Lemma 8.

Given $i\in \mathrm{1,2,3,4,5}$, there must exist some value $j\in \mathrm{1,2,3,4}$ such that $e^{\prime }{A}_i\oplus B_j=3$.

Lemma 9.

Given $i\in \mathrm{2,4,5}$, there must exist some value $j\in \mathrm{1,2,3,4}$ such that $e^{\prime }{A}_i\oplus B_j=1$.

Lemma 10.

Let $M$ be the maximum value in $a_m{P}_2\times P_k$, then we have$$\begin{array}{}\text{(4)}& M\le \min 3k-\mathrm{2,3}k-\frac{3m}{2}.\end{array}$$

Proof.

Let $f$ be any vertex labeling of $P_2\times P_k$ such that $v1-v0=m$. From $v1-v0=m,v1+v0=2k$, we obtain $v0=k-m/2$. Additionally, the maximum degree of the vertex of $P_2\times P_k$ is 3 and $e{P}_2\times P_k=3k-2$, so $M\le \min 3k-\mathrm{2,3}k-3m/2$.

Lemma 11.

When $i\ge 4$ and $k\le m+2/2$, we have $i\notin a_m{P}_2\times P_k$.

Proof.

Let $f$ be any vertex labeling of $P_2\times P_k$ such that $v1-v0=m$. Then, $v1+v0=2k$ and $v1\ge 1,v0\ge 1$, which implies that $v0=2k-m/2\ge 1$. Then, $k\ge m+2/2$. Thus, we can know $k<m+2/2$ does not hold. When $k=m+2/2,v0=1$ is the only possibility, note that a 0 vertex can lead to the number of 1 edge at most 3, and $i\ge 4$, so $i\notin a_m{P}_2\times P_k$. □

Given Lemma 11, we shall always assume in the following discussion that $m<4n-2$ in $P_2\times P_{2n}$, when $i\ge 4$ is an integer.

Lemmas 12 and 14 are some of the early results of Shiu and Kwong [13] on the cartesian product $P_2\times P_n$.

Lemma 12 (see [13]).

Let $f$ be a labeling of a graph $G$ that contains a subgraph cycle $C$. If $C$ contains at least a 1 edge, then the number of 1 edges in $C$ must be a positive even number.

Corollary 13.

For $k>1$, there exists no labeling $f$ of $P_2\times P_k$ such that $\mathrm{0,1,3}k-3\in a_m{P}_2\times P_k$.

Proof.

Let $f$ be any vertex labeling of $P_2\times P_k$ such that $v1-v0=m$. Since $m<VG$, $0\notin a_m{P}_2\times P_k$. From Lemma 12, it is easy to get $\mathrm{1,3}k-3\notin a_m{P}_2\times P_k$. The corollary follows immediately.

Lemma 14 (see [13]).

We have$$\begin{array}{c}\text{(5)}& a_0{P}_2\times P_{2n}=i:i\in \frac{\mathrm{2,6}n-2}{\mathrm{3,6}n-3},a_0{P}_2\times P_{2n+1}=i:i\in \frac{\mathrm{3,6}n+1}{6n}.\end{array}$$

3. The Full $m$ Index Sets of $P_2\times P_{2n}$

In this section, we give the full $m$ index set of $P_2\times P_{2n}$ by the embedding method and recursive method.

Theorem 15.

In $P_2\times P_{2n},m\equiv 0\mathrm{mod}4,m\ge \mathrm{4,3}\in a_m{P}_2\times P_{2n}$ holds only when $m=4n-4$, and in all other cases, $3\notin a_m{P}_2\times P_{2n}$.

Proof.

Suppose there exists a labeling of $P_2\times P_{2n}$ with $3\in a_m{P}_2\times P_{2n}$, when $m\equiv 0\mathrm{mod}4$ and $m\ge 4$. In accordance with Lemma 12, the three 1 edges must occur in two adjacent squares, say the $i$th and the $i+1\text{th}$ squares, and at least one of the three 1 edges is vertical. All possibilities can be divided into the following three cases:

  Case 1. There is only one vertical 1 edge, which must be $u_i{v}_i$. If $u_{i-1}{u}_i$ and $u_i{u}_{i+1}$ are the other 1 edges, then $f{u}_i=0$ and all other vertices are labeled 1. At this point, $v1-v0=4n-2$ contradicts $m\equiv 0\mathrm{mod}4$. If $u_i{u}_{i+1}$ and $v_{i-1}{v}_i$ are the other 1 edges, then $f{u}_x=1$ for $i+1\le x\le 2n$ and $f{v}_y=1$ for $i\le y\le 2n$. At this point, $v1-v0=4n-4i+2$ contradicts $m\equiv 0\mathrm{mod}4$. Neither of the subcases can exist. The other two cases are similar.

  Case 2. There are two vertical 1 edges, both of which belong to the $u_1{v}_1{v}_2{u}_2$ or $u_{2n-1}{v}_{2n-1}{v}_{2n}{u}_{2n}$ square. Due to symmetry, we may assume the vertical 1 edge is $u_1{v}_1$ and $u_2{v}_2$ and the other 1 edge is $u_2{u}_3$, and then $u_1$ and $u_2$ are labeled 0 and all other vertices are labeled 1. At this point, $m=4n-4$ holds. The other two cases are similar.

  Case 3. All three vertical edges are 1 edges. This situation does not exist because $m\ge 4$.

This completes the proof.

Theorem 16.

In $P_2\times P_{2n},m\equiv 2\mathrm{mod}4,2\in a_m{P}_2\times P_{2n}$ holds only when $m=4n-2$, and in all other cases, $2\notin a_m{P}_2\times P_{2n}$.

Proof.

Suppose there exists a labeling of $P_2\times P_{2n}$ with $2\in a_m{P}_2\times P_{2n}$, when $m\equiv 2\mathrm{mod}4$. In accordance to Lemma 12, the two 1 edges must occur in a square of $P_2\times P_{2n}$.

  Case 1. The two 1 edges are in a square $u_i{v}_i{v}_{i+1}{u}_{i+1}$. In this case, there must be $f^{\prime }{u}_i{u}_{i+1}=f^{\prime }{v}_i{v}_{i+1}=1$. Then, there must be $f{u}_x=f{v}_y=1$, for $i+1\le x,y\le 2n$. At this point, $m=4n-i$ contradicts $m\equiv 2\mathrm{mod}4$.

  Case 2. Both 1 edges are either in square $u_1{v}_1{v}_2{u}_2$ or $u_{2n-1}{v}_{2n-1}{v}_{2n}{u}_{2n}$. We assume that the two 1 edge are in square $u_1{v}_1{v}_2{u}_2$. Then, there must be $f^{\prime }{u}_1{u}_2=f^{\prime }{u}_1{v}_1=1$ or $f^{\prime }{u}_1{v}_1=f^{\prime }{v}_1{v}_2=1$. In either of the two cases, we have $m=4n-1-1=4n-2$. The other case is similar.

This completes the proof.

Theorem 17.

For $n>1$,$a_2{P}_2\times P_{2n}=i:i\in \mathrm{3,6}n-4$.

Proof.

From Lemma 14, we know $a_0{P}_2\times P_{2n-1}=i:i\in \mathrm{2,6}n-8/\mathrm{3,6}n-9$. Under any friendly label of $P_2\times P_{2n-1}$, there exists at least one square belonging type $A_1$, $A_2$, $A_3$, $A_4$ or $A_5$, in which $B_j$ can be embedded, where $j\in \mathrm{1,2,3,4}$. That is, three of the embedded vertices are labeled 1 and one is labeled 0. Thus, we observe that $v1-v0=2$ in $P_2\times P_{2n}$ after making a $C_4$-embedding in $P_2\times P_{2n-1}$. By Lemma 8, we have $\mathrm{5,7,8},\dots ,6n-\mathrm{8,6}n-\mathrm{7,6}n-5\subseteq a_2{P}_2\times P_{2n}$.

Under some friendly label of $P_2\times P_{2n-1}$, when the number of 1 edge is 2 or 5, there exist at least one of the squares $A_2$, $A_4$, and $A_5$, where $B_j$ can be embedded. $\mathrm{3,6}\subseteq a_2{P}_2\times P_{2n}$ is obtained from Lemma 9. It follows from Corollary 13 that 0, 1, $6n-3\notin a_2{P}_2\times P_{2n}$. Since $n>1$, we find $2\notin a_2{P}_2\times P_{2n}$ by Theorem 16. From Lemma 10, we know the maximum value of $a_2{P}_2\times P_{2n}$ is $6n-3$. Combined with (2), (3), and (4) in Example 1, we conclude that $a_2{P}_2\times P_{2n}=i:i\in \mathrm{3,6}n-4$.

Theorem 18.

For $n>2$,$a_4{P}_2\times P_{2n}=i:i\in \mathrm{2,6}n-6/3$.

Proof.

From Theorem 17, we know $i:i\in \mathrm{3,6}n-10\subseteq a_2{P}_2\times P_{2n-1}$. Under any label that satisfies $v1-v0=2$ in $P_2\times P_{2n-1}$, there is at least one of the squares in which $A_1$, $A_2$, $A_3$, $A_4$, $A_5$, and $B_j$ can be embedded, where $j\in \mathrm{1,2,3,4}$. That is, 3 of the embedded 4 vertices are labeled with 1 and 1 with 0. Thus, $v1-v0=4$ in $P_2\times P_{2n}$; by Lemma 8, we have $\mathrm{6,7,8},\dots ,6n-\mathrm{8,6}n-7\subseteq a_4{P}_2\times P_{2n}$.

Under a label that satisfies $v1-v0=2$ in $P_2\times P_{2n-1}$, when the number of 1 edge is 3 or 4, there must be a square $A_2$, $A_4$, and $A_5$, where $B_j$ can be embedded. $\mathrm{4,5}\subseteq a_4{P}_2\times P_{2n}$ is obtained from Lemma 9. Since $n>2$, we find $3\notin a_4{P}_2\times P_{2n}$ by Theorem 15. Corollary 13 implies that $\mathrm{0,1}\notin a_4{P}_2\times P_{2n}$. According to Lemma 10, we have $M\le \min 6n-\mathrm{2,6}n-6$. Combined with (1) and (2) in Example 2, we conclude that $a_4{P}_2\times P_{2n}=i:i\in \mathrm{2,6}n-6/3$.

Theorem 19.

For $n>2$,$a_6{P}_2\times P_{2n}=i:i\in \mathrm{3,6}n-9$.

Proof.

From Theorem 18, we know $i:i\in \mathrm{2,6}n-12/3\subseteq a_4{P}_2\times P_{2n-1}$. Under any label that satisfies $v1-v0=4$ in $P_2\times P_{2n-1}$, there is at least one of the squares $A_1$, $A_2$, $A_3$, $A_4$, $A_5$, and $B_j$ can be embedded, where $j\in \mathrm{1,2,3,4}$. That is, 3 out of the embedded 4 vertices are labeled with 1 and the other vertex is labeled with 0. By Lemma 8, we have $\mathrm{5,7,8},\dots ,6n-\mathrm{10,6}n-9\subseteq a_6{P}_2\times P_{2n}$.

Under a label that satisfies $v1-v0=4$ in $P_2\times P_{2n-1}$, when the number of 1 edge is 2 or 5, there must be a square in $A_2$, $A_4$, and $A_5$, embedded in $B_j$. $\mathrm{3,6}\subseteq a_6{P}_2\times P_{2n}$ is obtained from Lemma 9. Since $n>2$, we find $2\notin a_6{P}_2\times P_{2n}$ by Theorem 16. Corollary 13 implies that $\mathrm{0,1}\notin a_6{P}_2\times P_{2n}$. According to Lemma 10, we have $M\le \min 6n-\mathrm{2,6}n-9$. Combined with (7) in Example 3, we conclude that $a_6{P}_2\times P_{2n}=i:i\in \mathrm{3,6}n-9$.

Theorem 20.

For $m\equiv 0\mathrm{mod}4,4\le m\le 4n-8$, we have$$\begin{array}{}\text{(6)}& a_m{P}_2\times P_{2n}=i:i\in \frac{\mathrm{2,6}n-3m/2}{3}.\end{array}$$

For $m\equiv 2\mathrm{mod}4,6\le m\le 4n-6$, we have$$\begin{array}{}\text{(7)}& a_m{P}_2\times P_{2n}=i:i\in \mathrm{3,6}n-\frac{3m}{2}.\end{array}$$

Proof.

  Case 1. $m\equiv 0\mathrm{mod}4,4\le m\le 4n-8$.

  We will prove by induction. By Theorem 18, we have $i:i\in \mathrm{2,6}n-6/3\subseteq a_4{P}_2\times P_{2n}$. Suppose $i:i\in \mathrm{2,6}n-3k/2/3\subseteq a_k{P}_2\times P_{2n}$ for $k\equiv 0\mathrm{mod}4$, $4\le k\le 4n-8$ in $P_2\times P_{2n}$, then $i:i\in \mathrm{2,6}n-3k/2-6/3\subseteq a_k{P}_2\times P_{2n-1}$. Under any label that satisfies $v1-v0=k$ in $P_2\times P_{2n-1}$, there is at least one of the squares $A_1$, $A_2$, $A_3$, $A_4$, $A_5$, and $B_j$ can be embedded in this square, where $j\in \mathrm{1,2,3,4}$. That is, 3 out of the 4 vertices of the embedding are labeled 1 and the other vertex is labeled 0. Thus, we observe that $v1-v0=k+2$ in $P_2\times P_{2n}$ after the square is embedded. By Lemma 8, we have $\mathrm{5,7,8,9,11},\dots ,6n-3k/2-\mathrm{4,6}n-3k/2-3\subseteq a_{k+2}{P}_2\times P_{2n}$. Under a label that satisfies $v1-v0=k$ in $P_2\times P_{2n-1}$, when the number of 1 edge is 2 or 5, there must be a square $A_2$, $A_4$, $A_5$, and $B_j$ can be embedded. $\mathrm{3,6}\subseteq a_{k+2}{P}_2\times P_{2n}$ is obtained from Lemma 9. For $i+1\le x\le 2n$, let $f{u}_x=1$, and for $i+1\le y\le 2n-1$, let $f{v}_y=1$. This implies that $v1-v0=4n-i-1+2\equiv 2\mathrm{mod}4$. Thus, we know that $4\in a_{k+2}{P}_2\times P_{2n}$ holds. Since $m<4n-2$, we find $2\notin a_{k+2}{P}_2\times P_{2n}$ by Theorem 16. By Corollary 13, we have $\mathrm{0,1}\notin a_{k+2}{P}_2\times P_{2n}$. By Lemma 10, we find the maximum value of $a_{k+2}{P}_2\times P_{2n}$ is $6n-3k/2-3$. Therefore, we have $i:i\in \mathrm{3,6}n-3k/2-3\subseteq a_{k+2}{P}_2\times P_{2n}$.

  In $P_2\times P_{2n-1}$, $i:i\in \mathrm{3,6}n-3k/2-9\subseteq a_{k+2}{P}_2\times P_{2n-1}$. Under any labeling in $P_2\times P_{2n-1}$ which satisfies $v1-v0=k+2$, there exists at least one of the squares $A_1$, $A_2$, $A_3$, $A_4$, and $A_5$ in which $B_j$ can be embedded, where $j\in \mathrm{1,2,3,4}$. That is, 3 out of the 4 vertices of the embedding are labeled 1 and the other vertex is labeled 0. Thus, by Lemma 8, $\mathrm{6,7,8,9},\dots ,6n-3k/2-6\subseteq a_{k+4}{P}_2\times P_n$ holds when $v1-v0=k+4$ in $P_2\times P_{2n}$. Under any labeling in $P_2\times P_{2n}$ satisfying $v1-v0=k+2$ and when the number of its 1 edges is 3 or 4, there must exist a square similar as $A_2$, $A_4$, $A_5$, and $B_j$ can be embedded. By Lemma 9, we have $\mathrm{4,5}\subseteq a_{k+4}{P}_2\times P_{2n}$. In $P_2\times P_{2n}$, for $1\le x\le i$, let $f{u}_x=1$, and for $1\le y\le i$, let $f{v}_y=1$. Clearly, $v1-v0=4n-i\equiv 0\mathrm{mod}4$. Thus, we know that $2\in a_{k+4}{P}_2\times P_{2n}$ holds. Since $m<4n-4$, we find $3\notin a_{k+4}{P}_2\times P_{2n}$ by Theorem 15. By Corollary 13, we observe that $\mathrm{0,1}\notin a_{k+4}{P}_2\times P_{2n}$. According to Lemma 10, the maximum value of $a_{k+4}{P}_2\times P_{2n}$ is $6n-3k/2-6$. Therefore, we have $i:i\in \mathrm{2,6}n-3k/2-6/3\subseteq a_{k+4}{P}_2\times P_{2n}$.

  To conclude, when $m\equiv 0\mathrm{mod}4,4\le m\le 4n-8$, we have$$\begin{array}{}\text{(8)}& a_m{P}_2\times P_{2n}=i:i\in \frac{\mathrm{2,6}n-3m/2}{3}.\end{array}$$

  Case 2.$m\equiv 2\mathrm{mod}4$.

  Similarly, we can obtain $a_m{P}_2\times P_{2n}=i:i\in \mathrm{3,6}n-3m/2$ at $m\equiv 2\mathrm{mod}4,6\le m\le 4n-6$.

This completes the proof.

Theorem 21.

For $n>1$, $a_{4n-4}{P}_2\times P_{2n}=\mathrm{2,3,4,5,6}$.

Proof.

According to Lemma 10, we have $M{P}_2\times P_{2n}\le 6n-34n-4/2=6$. Corollary 13 implies that $\mathrm{0,1}\notin a_{4n-4}{P}_2\times P_{2n}$. Combined with Example 5, we know $a_{4n-4}{P}_2\times P_{2n}=\mathrm{2,3,4,5,6}$.

Theorem 22.

$a_{4n-2}{P}_2\times P_{2n}=\mathrm{2,3}$

Proof.

According to Lemma 10, we have $M{P}_2\times P_{2n}\le 6n-34n-2/2=3$. Corollary 13 implies that $\mathrm{0,1}\notin a_{4n-2}{P}_2\times P_{2n}$. Combined with Example 4, we know $a_{4n-2}{P}_2\times P_{2n}=\mathrm{2,3}$. □

Therefore, according to Lemma 14 and Theorems 15–17 and 20–22, we get the full $m$ index set of $P_2\times P_{2n}$ as follows:

(1) $a_0{P}_2\times P_{2n}=i:i\in \mathrm{2,6}n-2/\mathrm{3,6}n-3$

(2) For $n=1$, $a_2{P}_2\times P_2=2$

(3) For $n>1$, $a_2{P}_2\times P_{2n}=i:i\in \mathrm{3,6}n-4$

(4) For $m\equiv 0\mathrm{mod}4,4\le m\le 4n-8$, $a_m{P}_2\times P_{2n}=i:i\in \mathrm{2,6}n-3m/2/3$

(5) For $m\equiv 2\mathrm{mod}4,6\le m\le 4n-6$, $a_m{P}_2\times P_{2n}=i:i\in \mathrm{3,6}n-3m/2$

(6) For $n>1$, $a_{4n-4}{P}_2\times P_{2n}=\mathrm{2,3,4,5,6}$

(7) $a_{4n-2}{P}_2\times P_{2n}=\mathrm{2,3}$

4. The Full $m$ Index Sets of $P_2\times P_{2n+1}$

In a similar way, we embed the labeled graph $K_2$ in $P_2\times P_{2n}$ to obtain the full $m$ index set of $P_2\times P_{2n+1}$.

Lemma 23.

For $m\equiv 0\mathrm{mod}4,0\le m\le 4n-4$, we have $4\in a_m{P}_2\times P_{2n+1}$.

Proof.

Suppose that $m=4k$. In $P_2\times P_{2n+1}$, let $f{u}_i=f{v}_i=1$ for $1\le i\le k+n$, $f{u}_{2n+1}=1$, then $e1=4$. Therefore, we have $4\in a_m{P}_2\times P_{2n+1}$.

Lemma 24.

For $m\equiv 2\mathrm{mod}4,2\le m\le 4n-6$, we have $2\in a_m{P}_2\times P_{2n+1}$.

Proof.

Suppose that $m=4k+2$. In $P_2\times P_{2n+1}$, let $f{u}_i=f{v}_i=1$ for $1\le i\le k+n+1$, then $e1=2$. Therefore, we have $2\in a_m{P}_2\times P_{2n+1}$.

Lemma 25.

For $m\equiv 0\mathrm{mod}2,4\le m\le 4n-4$, we have $6n-3m/2+\mathrm{2,6}n-3m/2+3\subseteq a_m{P}_2\times P_{2n+1}$.

Proof.

For $m\equiv 0\mathrm{mod}4,4\le m\le 4n-4$, suppose that $m=4k$. In $P_2\times P_{2n+1}$, let $f{u}_i=1$ when $i=\mathrm{1,3,5},\dots ,2n-2k+\mathrm{1,2}n-2k+\mathrm{2,2}n-2k+3,\dots ,2n+1$; $f{v}_j=1$ when $j=\mathrm{2,4,6},\dots ,2n-2k,2n-2k+\mathrm{2,2}n-2k+3,\dots ,2n+1$. Then, $e1=6n-3m/2+2$. Similarity, let $f{u}_i=1$ when $i=\mathrm{1,3,5},\dots ,2n-2k+\mathrm{1,2}n-2k+\mathrm{3,2}n-2k+4,\dots ,2n+1$; $f{v}_j=1$ when $j=\mathrm{1,2,4,6},\dots ,2n-2k,2n-2k+\mathrm{2,2}n-2k+3,\dots ,2n+1$. Then, $e1=6n-3m/2+3$. Therefore, we have $6n-3m/2+\mathrm{2,6}n-3m/2+3\subseteq a_m{P}_2\times P_{2n+1}$.

For $m\equiv 2\mathrm{mod}4,6\le m\le 4n-6$.

In $P_2\times P_{2n+1}$, let $f{u}_i=1$ when $i=\mathrm{1,3,5},\dots ,2n-m/2,2n-m/2+\mathrm{2,2}n-m/2+3,\dots ,2n+1$; $f{v}_j=1$ when $j=\mathrm{2,4,6},\dots ,2n-m/2+\mathrm{1,2}n-m/2+\mathrm{2,2}n-m/2+3,\dots ,2n+1$. Then, $e1=6n-3m/2+2$. Let $f{u}_i=1$ when $i=\mathrm{1,3,5},\dots ,2n-m/2,2n-m/2+\mathrm{2,2}n-m/2+3,\dots ,2n+1$; $f{v}_j=1$ when $j=\mathrm{1,2,4,6},\dots ,2n-m/2+\mathrm{1,2}n-m/2+\mathrm{3,2}n-m/2+4,\dots ,2n+1$. Then, $e1=6n-3m/2+3$. Thus, $6n-3m/2+\mathrm{2,6}n-3m/2+3\subseteq a_m{P}_2\times P_{2n+1}$.

Lemma 26.

Given $i\in \mathrm{2,3,4,5}$, there must exist $K_2=\begin{array}{c}1\\ 0\end{array}$ such that $e^{\prime }{A}_i\oplus K_2=1$.

Proof.

Let $A_2=\begin{array}{cc}1& 1\\ 1& 0\end{array},A_3=\begin{array}{cc}1& 1\\ 0& 0\end{array},A_4=\begin{array}{cc}1& 0\\ 0& 1\end{array},A_5=\begin{array}{cc}0& 1\\ 0& 1\end{array}$, we make a $K_2$-embedding in $A_i$, where $i\in \mathrm{2,3,4,5}$. Then, $e^{\prime }1=1$. Therefore, we have $e^{\prime }{A}_i\oplus K_2=1$. □

In $P_2\times P_{2n+1}$, there exist a vertex labeling $f$ such that $v1-v0=m$. From $v1+v0=4n+2,v1\ge 1,v0\ge 1$, we get $m\le 4n$. Thus, we shall always assume that $m\le 4n$ in the following discussion.

Theorem 27.

In $P_2\times P_{2n+1},m\equiv 0\mathrm{mod}4,m>\mathrm{0,2}\in a_m{P}_2\times P_{2n+1}$ holds only when $m=4n$, and in all other cases, $2\notin a_m{P}_2\times P_{2n+1}$.

Proof.

Suppose there exists a labeling of $P_2\times P_{2n+1}$ with $2\in a_m{P}_2\times P_{2n+1}$, when $m\equiv 0\mathrm{mod}4$. In accordance to Lemma 12, the two 1 edges must occur in a square of $P_2\times P_{2n+1}$.

  Case 1. Both 1 edges are in a square $u_i{v}_i{v}_{i+1}{u}_{i+1}$. In this case, there must be $f^{\prime }{u}_i{u}_{i+1}=f^{\prime }{v}_i{v}_{i+1}=1$. Then, there must be $f{u}_x=f{v}_y=1$, for $i+1\le x,y\le 2n+1$. At this point, $m=4n-i+2$ contradicts $m\equiv 0\mathrm{mod}4$.

  Case 2. Both 1 edges are either in square $u_1{v}_1{v}_2{u}_2$ or $u_{2n}{v}_{2n}{v}_{2n+1}{u}_{2n+1}$. We assume that both 1 edges are in square $u_1{v}_1{v}_2{u}_2$. Then, there must be $f^{\prime }{u}_1{u}_2=f^{\prime }{u}_1{v}_1=1$ or $f^{\prime }{u}_1{v}_1=f^{\prime }{v}_1{v}_2=1$. In either of the two cases, we have $m=4n+1-1=4n$. The other case is similar.

This completes the proof.

Theorem 28.

In $P_2\times P_{2n+1},m\equiv 2\mathrm{mod}4,3\in a_m{P}_2\times P_{2n+1}$ holds only when $m=4n-2$, and in all other cases, $3\notin a_m{P}_2\times P_{2n+1}$.

Proof.

Suppose there exists a labeling of $P_2\times P_{2n+1}$ with $3\in a_m{P}_2\times P_{2n+1}$, when $m\equiv 2\mathrm{mod}4$. In accordance with Lemma 12, the three 1 edges must occur in two adjacent squares, say the $i$th and the $i+1\text{th}$ squares, and at least one of the three 1 edges is vertical. All possibilities can be divided into the following three cases.

  Case 1. There is only one vertical 1 edge, which must be $u_i{v}_i$. If $u_{i-1}{u}_i$ and $u_i{u}_{i+1}$ are the other 1 edges, then $f{u}_i=0$ and all other vertices are labeled 1. At this point, $v1-v0=4n+1-1=4n$ contradicts $m\equiv 2\mathrm{mod}4$. If $u_i{u}_{i+1}$ and $v_{i-1}{v}_i$ are the other 1 edges, then $f{u}_x=1$ for $i+1\le x\le 2n+1$ and $f{v}_y=1$ for $i\le y\le 2n+1$. At this point, $v1-v0=4n-4i+4=4n-i+1$ contradicts $m\equiv 2\mathrm{mod}4$. Neither of the subcases can exist. The other two cases are similar.

  Case 2. There are two vertical 1 edges, both of which belong to the $u_1{v}_1{v}_2{u}_2$ or $u_{2n}{v}_{2n}{v}_{2n+1}{u}_{2n+1}$ square. Due to symmetry, we may assume the vertical 1 edge are $u_1{v}_1$ and $u_2{v}_2$, and the other 1 edge is $u_2{u}_3$, and then $u_1$ and $u_2$ are labeled 0 and all other vertices labeled 1. At this point, $m=4n-2$ holds. The other two cases are similar.

  Case 3. All three vertical edges are 1 edge. This situation does not exist because $m\ge 2$.

This completes the proof.

Theorem 29.

The followings hold true:

(1) For $n>1$, we have $a_2{P}_2\times P_{2n+1}=i:i\in \mathrm{2,6}n-1/3$

(2) For $m\equiv 0\mathrm{mod}4,4\le m\le 4n-4,a_m{P}_2\times P_{2n+1}=i:i\in \mathrm{3,6}n-3m/2+3$

(3) For $m\equiv 2\mathrm{mod}4,6\le m\le 4n-6,a_m{P}_2\times P_{2n+1}=i:i\in \mathrm{2,6}n-3m/2+3/3$

(4) $a_{4n-2}{P}_2\times P_{2n+1}=\mathrm{2,6}$

(5) $a_{4n}{P}_2\times P_{2n+1}=\mathrm{2,3}$

Proof.

  For (1), according to Theorem 17, we know $i:i\in \mathrm{3,6}n-4\subseteq a_2{P}_2\times P_{2n}$. Under any friendly label of $P_2\times P_{2n}$, there exist at least one square belonging type $A_2,A_3,A_4$, or $A_5$, in which $K_2$ can be embedded. That is, one of the embedded vertices is labeled 1 and other one is labeled 0. Thus, we note that $v1-v0=2$ does not change after $K_2$ is embedded. From Lemma 26, we know $\mathrm{4,6}n-3\subseteq a_2{P}_2\times P_{2n+1}$. By Lemma 24, we find $2\in a_2{P}_2\times P_{2n+1}$. Suppose that $f{u}_1=f{u}_3=\cdots =f{u}_{2n-1}=f{u}_{2n}=f{u}_{2n+1}=1$, $f{v}_2=f{v}_4=\cdots =f{v}_{2n}=1$, then we have $e_{2}1=6n-2$. Let $f{u}_1=f{u}_3=\cdots =f{u}_{2n-1}=f{u}_{2n+1}=1$, $f{v}_2=f{v}_4=\cdots =f{v}_{2n}=f{v}_{2n+1}=1$, then we have $e_{2}1=6n-1$. From Corollary 13, we find $\mathrm{0,1,6}n\notin a_m{P}_2\times P_{2n+1}$. Since $m<4n-2$, we find $3\notin a_2{P}_2\times P_{2n+1}$ by Theorem 28. Using Lemma 10, we know $M\le \min 6n+\mathrm{1,6}n$. Thus, we conclude that $a_2{P}_2\times P_{2n+1}=i:i\in \mathrm{2,6}n-3/3$.

  For (2), from Theorem 20, we have $i:i\in \mathrm{2,6}n-3m/2/3\subseteq a_2{P}_2\times P_{2n}$. Under any friendly label of $P_2\times P_{2n}$, there exist at least one square belonging type $A_2,A_3,A_4$, or $A_5$, in which $K_2$ can be embedded. That is, one of the embedded vertices is labeled 1 and other one is labeled 0. Thus, by Lemma 26, we get $i:i\in \mathrm{3,6}n-3m/2+1/4\subseteq a_2{P}_2\times P_{2n+1}$. It follows from Lemmas 23 and 25 that $\mathrm{4,6}n-3m/2+\mathrm{2,6}n-3m/2+3\subseteq a_m{P}_2\times P_{2n+1}$. Since $m<4n$, we find $2\notin a_m{P}_2\times P_{2n+1}$ by Theorem 27. In accordance with Lemma 10, we find $M\le \min 6n+\mathrm{1,6}n-3m/2+3$. Thus, we conclude that $a_m{P}_2\times P_{2n+1}=i:i\in \mathrm{3,6}n-3m/2+3$.

  For (3), from Theorem 20, we have $i:i\in \mathrm{3,6}n-3m/2\subseteq a_2{P}_2\times P_{2n}$. Under any friendly label of $P_2\times P_{2n}$, there exists at least one square belonging type $A_2,A_3,A_4$, or $A_5$, in which $K_2$ can be embedded. That is, one of the embedded vertices is labeled 1 and other one is labeled 0. From Lemma 26, we get $i:i\in \mathrm{4,6}n-3m/2+1\subseteq a_2{P}_2\times P_{2n+1}$. It follows from Lemmas 23 and 25 that $\mathrm{2,6}n-3m/2+\mathrm{2,6}n-3m/2+3\subseteq a_m{P}_2\times P_{2n+1}$. Since $m<4n-2$, we find $3\notin a_m{P}_2\times P_{2n+1}$ by Theorem 28. Thus, combined with Lemma 10, we conclude that $i:i\in \mathrm{2,6}n-3m/2+3/3\subseteq a_m{P}_2\times P_{2n+1}$.

  For (4), according to Lemma 10, we have $M{P}_2\times P_{2n+1}\le \min 6n+\mathrm{1,6}n-3m/2+3\le 6n-34n-2/2+3=6$. Corollary 13 implies that $\mathrm{0,1}\notin a_{4n-2}{P}_2\times P_{2n+1}$. Combined with Example 7, we know $a_{4n-2}{P}_2\times P_{2n+1}=\mathrm{2,6}$.

  For (5), according to Lemma 10, we have $M{P}_2\times P_{2n+1}\le \min 6n+\mathrm{1,6}n-3m/2+3\le 6n-34n/2+3=3$. Corollary 13 implies that $\mathrm{0,1}\notin a_{4n}{P}_2\times P_{2n+1}$. Combined with Example 6, we know $a_{4n}{P}_2\times P_{2n+1}=\mathrm{2,3}$. □

This completes the proof.

5. Conclusions

In this paper, we obtained the full $m$ index set of $P_2\times P_n$ by embedding and recursion methods. We can also use this method to consider the full $m$ index set of other graphs.

The characterization of full $m$ index sets for various graph families lays the mathematical groundwork for a wide range of applications involving labeled graphs. Labeled graphs have been applied across diverse fields including coding theory, circuit layout, network design, and more. By expanding theoretical knowledge on balanced labelings and index sets of key graph classes like $P_2\times P_n$, this work provides fundamental insights that can inform labeled graph models in any application domain. Though the specific results focus on index sets, the techniques like embedding and recursion have broad implications for constructing balanced graph partitions. Overall, this research on graph labelings and index sets furthers a mathematical foundation that enables diverse real-world applications. The methods and labeled graph constructions can be extended to other graph families, complementing existing literature and providing a springboard for future studies. By elucidating balanced labelings of modular graph units, the work broadly enhances our ability to design and analyze application-oriented labeled graph models.

References

[1] J. A. Gallian, "A dynamic survey of graph labeling," Electronic Journal of Combinatorics, vol. 19, 2009.

[2] G. Chartrand, S. M. Lee, P. Zhang, "Uniformly cordial graphs," Discrete Mathematics, vol. 306 no. 8-9, pp. 726-737, DOI: 10.1016/j.disc.2005.11.025, 2006.

[3] H. Kwong, S. M. Lee, H. K. Ng, "On friendly index sets of 2-regular graphs," Discrete Mathematics, vol. 308 no. 23, pp. 5522-5532, DOI: 10.1016/j.disc.2007.10.018, 2008.

[4] S. M. Lee, H. K. Ng, G. C. Lau, "On friendly index sets of spiders," Bulletin of the Malaysian Mathematical Sciences Society, vol. 8 no. 1, pp. 47-68, 2014.

[5] W. C. Shiu, M. H. Ling, "Full friendly index sets of Cartesian products of two cycles," Acta Mathematica Sinica-English Series, vol. 26 no. 7, pp. 1233-1244, DOI: 10.1007/s10114-010-8517-5, 2010.

[6] J. F. Hou, S. F. Wu, "On bisections of graphs without complete bipartite graphs," Journal of Graph Theory, vol. 98 no. 4, pp. 630-641, DOI: 10.1002/jgt.22717, 2021.

[7] J. F. Hou, J. Yan, "Max-Bisections of H-free graphs," Discrete Mathematics, vol. 343 no. 1, pp. 111590-111595, DOI: 10.1016/j.disc.2019.07.006, 2020.

[8] B. G. Xu, "Graph partitions: recent progresses and some open problems," Advances in Mathematics, vol. 45, 2016.

[9] D. Sinha, J. Kaur, "Full friendly index set-I," Discrete Applied Mathematics, vol. 161 no. 9, pp. 1262-1274, DOI: 10.1016/j.dam.2012.10.028, 2013.

[10] W. C. Shiu, F. S. Wong, "Full friendly index sets of cylinder graphs," Australasian Journal of Combinatorics, vol. 52, pp. 141-162, 2012.

[11] W. C. Shiu, M. H. Ho, "Full friendly index sets and full product-cordial index sets of some permutation Petersen graphs," Journal of Combinatorics and Number Theory, vol. 5 no. 3, pp. 227-244, 2013.

[12] W. C. Shiu, M. H. Ho, "Full friendly index sets of slender and flat cylinder graphs," Transactions on Combinatorics, vol. 2 no. 4, pp. 63-80, 2013.

[13] W. C. Shiu, H. Kwong, "Full friendly index sets of P2×Pn," Discrete Mathematics, vol. 308 no. 16, pp. 3688-3693, DOI: 10.1016/j.disc.2007.07.002, 2008.

[14] Z. B. Gao, H. N. Ren, S. Lee, R. Han, G. Lau, "A new approach in finding full friendly indices," Bulletin of the Malaysian Mathematical Sciences Society, vol. 41 no. 1, pp. 443-453, DOI: 10.1007/s40840-016-0373-8, 2018.