Menu
A sum divisor cordial labeling of a graph \(G\) with vertex set \(V(G)\) is a bijection \(f\) from \(V(G)\) to \(\{1,2,\cdots,|V(G)|\}\) such that an edge \(uv\) is assigned the label \(1\) if \(2\) divides \(f(u)+f(v)\) and \(0\) otherwise; and the number of edges labeled with \(1\) and the number of edges labeled with \(0\) differ by at most \(1\). A graph with a sum divisor cordial labeling is called a sum divisor cordial graph. In this paper, we discuss the sum divisor cordial labeling of transformed tree related graphs.
All graphs considered here are simple, finite, connected and
undirected. The vertex set and the edge set of a graph are denoted by
\(V(G)\) and \(E(G)\) respectively. We follow the basic
notations and terminology of graph theory as in [1]. A labeling of a graph is a map that carries the
graph elements to the set of numbers, usually to the set of non-negative
or positive integers. If the domain is the set of vertices then the
labeling is called vertex labeling. If the domain is the set of edges
then the labeling is called edge labeling. If the labels are assigned to
both vertices and edges then the labeling is called total labeling. A
detailed survey of graph labeling is available in [2]. The concept of cordial labeling was introduced
by Cahit in [3].
Lourdusamy et al. introduced the concept of sum divisor cordial labeling
in [4]. They prove that
paths, combs, stars, complete bipartite, \(K_{2}+mK_{1}\), bistars, jewels, crowns,
flowers, gears, subdivisions of stars, the graph obtained from \(K_{1,3}\) by attaching the root of \(K_{1,n}\) at each pendent vertex of \(K_{1,3}\), and the square \(B_{n,n}\) are sum divisor cordial graphs.
Also they discussed the sum divisor labeling of star related graphs,
path related graphs and cycle related graphs in [5,6, 7].
In [8, 9, 10, 11],
Sugumaran et al. investigated the behaviour of sum divisor cordial
labeling of swastiks, path unions of finite number of copies of
swastiks, cycles of \(k\) copies of
swastiks, when \(k\) is odd, jelly
fish, Petersen graphs, theta graphs, the fusion of any two vertices in
the cycle of swastiks, duplication of any vertex in the cycle of
swastiks, the switchings of a central vertex in swastiks, the path
unions of two copies of a swastik, the star graph of the theta graphs,
the Herschel graph, the fusion of any two adjacent vertices of degree 3
in Herschel graphs, the duplication of any vertex of degree 3 in the
Herschel graph, the switching of central vertex in Herschel graph, the
path union of two copies of the Herschel graph, \(H\)-graph \(H_{n}\), when \(n\) is odd, \(C_{3} @ K_{1,n}\), \(<F_{n}^{1} \Delta F_{n}^{2}>\) and
open star of swastik graphs \(S(t.Sw_{n})\), when \(t\) is odd.
In [12, 13, 14, 15] Sugumaran
et al. proved that the following graphs are sum divisor cordial graphs:
\(H\)-graph \(H_{n}\), when \(n\) is even, duplication of all edges of
the \(H\)-graph \(H_{n}\), when \(n\) is even, \(H_{n} \odot K_{1}\), \(P(r.H_{n})\), \(C(r.H_{n})\), plus graphs, umbrella graphs,
path unions of odd cycles, kites, complete binary trees, drums graph,
twigs, fire crackers of the form \(P_{n} \odot
S_{n}\), where \(n\) is even,
and the double arrow graph \(DA^{n}_{m}\), where \(|m-n| \leq 1\) and \(n\) is even. Further results on sum divisor
cordial labeling are given in [16, 17].
In this paper, we discuss the sum divisor cordial labeling of
transformed tree related graphs like \(T
\widehat{O} P_{n}\), \(T \widehat{O}
C_{n} \ (n \equiv 1,3,0 \ (mod \ 4))\), \(T \widehat{O} K_{1,n}\), \(T \widehat{O} \bar{K_{n}}\), \(T \widehat{O} Q_{n}\), \(T \widetilde{O} C_{n} \ (n \equiv 1,3,0 \ (mod \
4))\) and \(T \widetilde{O}
Q_{n}\). We use the following definitions in the subsequent
sections.
Definition 1. Let \(G=(V(G),E(G))\) be a simple graph and \(f:V(G) \rightarrow \{1,2,\cdots,|V(G)|\}\) be a bijection. For each edge \(uv\), assign the label \(1\) if \(2|(f(u)+f(v))\) and the label \(0\) otherwise. The function \(f\) is called a sum divisor cordial labeling if \(|e_{f}(1)-e_{f}(0)| \leq 1\). A graph which admits a sum divisor cordial labeling is called a sum divisor cordial graph.
Definition 2. [18] Let \(T\) be a tree and \(u_{0}\) and \(v_{0}\) be two adjacent vertices in \(T\). Let there be two pendant vertices \(u\) and \(v\) in \(T\) such that the length of \(u_{0}-u\) path is equal to the length of \(v_{0}-v\) path. If the edge \(u_{0}v_{0}\) is deleted from \(T\) and \(u, v\) are joined by an edge \(uv\), then such a transformation of \(T\) is called an elementary parallel transformation (or an ept) and the edge \(u_{0}v_{0}\) is called transformable edge.
If by the sequence of ept’s, \(T\) can be reduced to a path, then \(T\) is called a \(T_{p}\)-tree (transformed tree) and such a sequence regarded as a composition of mappings (ept’s) denoted by \(P\), is called a parallel transformation of \(T\). The path, the image of \(T\) under \(P\) is denoted as \(P(T)\).
Definition 3. The corona \(G_{1} \odot G_{2}\) of two graphs \(G_{1}(p_{1},q_{1})\) and \(G_{2}(p_{2},q_{2})\) is defined as the graph obtained by taking one copy of \(G_{1}\) and \(p_{1}\) copies of \(G_{2}\) and joining the \(i^{th}\) vertex of \(G_{1}\) with an edge to every vertex in the \(i^{th}\) copy of \(G_{2}\).
Definition 4. [19] Let \(G_{1}\) be a graph with \(p\) vertices and \(G_{2}\) be any graph. A graph \(G_{1}\hat{O}G_{2}\) is obtained from \(G_{1}\) and \(p\) copies of \(G_{2}\) by identifying one vertex of \(i^{th}\) copy of \(G_{2}\) with \(i^{th}\) vertex of \(G_{1}\).
Definition 5. [19] Let \(G_{1}\) be a graph with \(p\) vertices and \(G_{2}\) be any graph. A graph \(G_{1}\tilde{O}G_{2}\) is obtained from \(G_{1}\) and \(p\) copies of \(G_{2}\) by joining one vertex of \(i^{th}\) copy of \(G_{2}\) with \(i^{th}\) vertex of \(G_{1}\) by an edge.
Theorem 1. [7] Every \(T_{p}\)-tree is sum divisor cordial graph.
Theorem 2. If \(T\) be a \(T_{p}\)-tree on \(m\) vertices, then the graph \(T \widehat{O} P_{n}\) is sum divisor cordial graph.
Proof. Let \(T\) be a \(T_{p}\)-tree with \(m\) vertices. By the definition of a
transformed tree there exists a parallel transformation \(P\) of \(T\) such that for the path \(P(T)\), we have \((i) \ V(P(T))=V(T)\) and \((ii) \ E(P(T))=(E(T)-E_{d}) \bigcup
E_{p}\), where \(E_{d}\) is the
set of edges deleted from \(T\) and
\(E_{p}\) is the set of edges newly
added through the sequence \(P=(P_{1},P_{2},\cdots,P_{k})\) of the
epts \(P\) used to arrive at
the path \(P(T)\). Clearly, \(E_{d}\) and \(E_{p}\) have the same number of edges.
Denote the vertices of \(P(T)\)
successively as \(v_{1},v_{2},\cdots,v_{m}\) starting from
one pendant vertex of \(P(T)\) right up
to the other. Let \(u^{j}_{1},u^{j}_{2},\cdots,u^{j}_{n}(1 \leq j \leq
m)\) be the vertices of \(j^{th}\) copy of \(P_{n}\) with \(u^{j}_{1}=v_{j}\). Then \(V(T \widehat{O} P_{n})=\{v_{j},u^{j}_{i}: 1 \leq i
\leq n, 1 \leq j \leq m \ \text{with} \ u^{j}_{1}=v_{j}\}\) and
\(E(T \widehat{O} P_{n})=E(T) \bigcup
\{u^{j}_{i}u^{j}_{i+1}: 1 \leq i \leq n-1, 1 \leq j \leq m
\}\).
Define \(f:V(T \widehat{O} P_{n})\rightarrow
\{1,2,\dots,mn\}\) as follows:
Case 1.1] \(n\) is even.
For \(1 \leq j \leq m\) and \(1 \leq i \leq n\),
\(f(u^{j}_{i})=\begin{cases}n(j-1)+i+1 &
\text{ if } \ i \equiv 1 \ (mod \ 4) \\ n(j-1)+i-1 & \text{ if } \ i
\equiv 2 \ (mod \ 4) \\ n(j-1)+i & \text{ if } \ i \equiv 3,0 \ (mod
\ 4) \ . \end{cases}\)
Let \(v_{i}v_{j}\) be a transformed edge in \(T\), \(1 \leq i<j \leq m\) and let \(P_{1}\) be the ept obtained by deleting the edge \(v_{i}v_{j}\) and adding the edge \(v_{i+t}v_{j-t}\) where \(t\) is the distance of \(v_{i}\) from \(v_{i+t}\) and the distance of \(v_{j}\) from \(v_{j-t}\). Let \(P\) be a parallel transformation of \(T\) that contains \(P_{1}\) as one of the constituent epts.
Since \(v_{i+t}v_{j-t}\) is an edge
in the path \(P(T)\), it follows that
\(i+t+1=j-t\) which implies \(j=i+2t+1\). Therefore, \(i\) and \(j\) are of opposite parity.
The induced edge label of \(v_{i}v_{j}\) is given by \[\begin{aligned}
f^{*}(v_{i}v_{j}) & = f^{*}(v_{i}v_{i+2t+1})\\ & =
2|(f(v_{i})+f(v_{i+2t+1}))\\ & = 1.
\end{aligned}\] The induced edge label of \(v_{i+t}v_{j-t}\) is given by \[\begin{aligned}
f^{*}(v_{i+t}v_{j-t}) & = f^{*}(v_{i+t}v_{i+t+1})\\ & =
2|(f(v_{i+t})+f(v_{i+t+1}))\\ & = 1.
\end{aligned}\] Therefore, \(f^{*}(v_{i}v_{j})=f^{*}(v_{i+t}v_{j-t})\).
The induced edge labels are as follows:
\(f^{*}(v_{j}v_{j+1})=1, \ 1 \leq j \leq
m-1;\)
for \(1 \leq i \leq n-1\) and \(1 \leq j \leq m\),
\(f^{*}(u^{j}_{i}u^{j}_{i+1})=\begin{cases}0
& \text{ if } \ i \ \text{is odd} \\ 1 & \text{ if } \ i \
\text{is even} \ . \end{cases}\)
Case 2.1] \(n\) is odd.
For \(1 \leq j \leq m\),
choose ‘if \(j \equiv 1,2 \ (mod \
4)\)’,
\(f(u^{j}_{i})=\begin{cases}n(j-1)+i &
\text{ if } \ i \equiv 1,0 \ (mod \ 4) \ \text{and} \ 1 \leq i \leq n\\
n(j-1)+i+1 & \text{ if } \ i \equiv 2 \ (mod \ 4) \ \text{and} \ 1
\leq i \leq n\\ n(j-1)+i-1 & \text{ if } \ i \equiv 3 \ (mod \ 4) \
\text{and} \ 1 \leq i \leq n \ ; \end{cases}\)
choose ‘if \(j \equiv 3,0 \ (mod \
4)\)’ and \(n \equiv 3 \ (mod \
4)\),
\(f(u^{j}_{i})=\begin{cases}n(j-1)+i+1 &
\text{ if } \ i \equiv 1 \ (mod \ 4) \ \text{and} \ 1 \leq i \leq n \\
n(j-1)+i-1 & \text{ if } \ i \equiv 2 \ (mod \ 4) \ \text{and} \ 1
\leq i \leq n\\ n(j-1)+i & \text{ if } \ i \equiv 3,0 \ (mod \ 4) \
\text{and} \ 1 \leq i \leq n \ ; \end{cases}\)
choose ‘if \(j \equiv 3,0 \ (mod \
4)\)’ and \(n \equiv 1 \ (mod \
4)\),
\(f(u^{j}_{i})=\begin{cases}n(j-1)+i+1 &
\text{ if } \ i \equiv 1 \ (mod \ 4) \ \text{and} \ 1 \leq i \leq n-2 \\
n(j-1)+i-1 & \text{ if } \ i \equiv 2 \ (mod \ 4) \ \text{and} \ 1
\leq i \leq n-2 \\ n(j-1)+i & \text{ if } \ i \equiv 3,0 \ (mod \ 4)
\ \text{and} \ 1 \leq i \leq n-2 \\ n(j-1)+i+1 & \text{ if } \ i=n-1
\\ n(j-1)+i-1 & \text{ if } \ i=n \ . \end{cases}\)
Let \(v_{i}v_{j}\) be a transformed edge in \(T\), \(1 \leq i<j \leq m\) and let \(P_{1}\) be the ept obtained by deleting the edge \(v_{i}v_{j}\) and adding the edge \(v_{i+t}v_{j-t}\) where \(t\) is the distance of \(v_{i}\) from \(v_{i+t}\) and the distance of \(v_{j}\) from \(v_{j-t}\). Let \(P\) be a parallel transformation of \(T\) that contains \(P_{1}\) as one of the constituent epts.
Since \(v_{i+t}v_{j-t}\) is an edge
in the path \(P(T)\), it follows that
\(i+t+1=j-t\) which implies \(j=i+2t+1\). Therefore, \(i\) and \(j\) are of opposite parity.
The induced edge label of \(v_{i}v_{j}\) is given by \[\begin{aligned}
f^{*}(v_{i}v_{j}) & = f^{*}(v_{i}v_{i+2t+1})\\ & =
\begin{cases}0 & \text{ if } \ i \ \text{is odd} \\ 1 & \text{
if } \ i \ \text{is even} . \end{cases}
\end{aligned}\] The induced edge label of \(v_{i+t}v_{j-t}\) is given by \[\begin{aligned}
f^{*}(v_{i+t}v_{j-t}) & = f^{*}(v_{i+t}v_{i+t+1})\\ & =
\begin{cases}0 & \text{ if } \ i \ \text{is odd} \\ 1 & \text{
if } \ i \ \text{is even} . \end{cases}
\end{aligned}\] Therefore, \(f^{*}(v_{i}v_{j})=f^{*}(v_{i+t}v_{j-t})\).
The induced edge labels are as follows:
\(f^{*}(v_{j}v_{j+1})=\begin{cases}0 &
\text{ if } \ i \ \text{is odd and} \ 1 \leq j \leq m-1 \\ 1 &
\text{ if } \ i \ \text{is even and} \ 1 \leq j \leq m-1 \ ;
\end{cases}\)
for \(1 \leq j \leq m\),
choose ‘if \(j \equiv 1,2 \ (mod \
4)\)’,
\(f^{*}(u^{j}_{i}u^{j}_{i+1})=\begin{cases}1
& \text{ if } \ i \ \text{is odd and} \ 1 \leq i \leq n-1 \\ 0 &
\text{ if } \ i \ \text{is even and} \ 1 \leq i \leq n-1 \ ;
\end{cases}\)
choose ‘if \(j \equiv 3,0 \ (mod \
4)\)’ and \(n \equiv 3 \ (mod \
4)\),
\(f^{*}(u^{j}_{i}u^{j}_{i+1})=\begin{cases}0
& \text{ if } \ i \ \text{is odd and} \ 1 \leq i \leq n-1 \\ 1 &
\text{ if } \ i \ \text{is even and} \ 1 \leq i \leq n-1 \ ;
\end{cases}\)
choose ‘if \(j \equiv 3,0 \ (mod \
4)\)’ and \(n \equiv 1 \ (mod \
4)\),
\(f^{*}(u^{j}_{i}u^{j}_{i+1})=\begin{cases}0
& \text{ if } \ i \ \text{is odd and} \ 1 \leq i \leq n-3 \\ 1 &
\text{ if } \ i \ \text{is even and} \ 1 \leq i \leq n-3 \\ 1 &
\text{ if } \ i=n-2 \\ 1 & \text{ if } \ i=n-1 \ .
\end{cases}\)
In the above two cases,
when \(m\) is odd and \(n\) is odd,
\(e_{f}(0)=e_{f}(1)=\frac{mn-1}{2}\);
when \(m\) is odd and \(n\) is even,
\(e_{f}(0)=\left\lceil
\frac{mn-1}{2}\right\rceil\) and \(e_{f}(1)=\left\lfloor \frac{mn-1}{2}
\right\rfloor\);
when \(m\) is even and \(n\) is odd or even,
\(e_{f}(0)=\left\lceil
\frac{mn-1}{2}\right\rceil\) and \(e_{f}(1)=\left\lfloor \frac{mn-1}{2}
\right\rfloor\).
Clearly \(|e_{f}(0)-e_{f}(1)| \leq 1\).
Hence \(T \widehat{O} P_{n}\) is sum
divisor cordial graph. ◻
Example 1. Sum divisor cordial labeling of \(T \widehat{O} P_{5}\) where \(T\) is a \(T_{p}\)-tree with 11 vertices is shown in Figure 2.
Theorem 3. If \(T\) be a \(T_{p}\)-tree on \(m\) vertices, then the graph \(T \widehat{O} C_{n}\) is sum divisor cordial graph if \(n \equiv 0,3,1 \ (mod \ 4)\).
Proof. Let \(T\) be a \(T_{p}\)-tree with \(m\) vertices. By the definition of a
transformed tree there exists a parallel transformation \(P\) of \(T\) such that for the path \(P(T)\), we have \((i) \ V(P(T))=V(T)\) and \((ii) \ E(P(T))=(E(T)-E_{d}) \bigcup
E_{p}\), where \(E_{d}\) is the
set of edges deleted from \(T\) and
\(E_{p}\) is the set of edges newly
added through the sequence \(P=(P_{1},P_{2},\cdots,P_{k})\) of the
epts \(P\) used to arrive at
the path \(P(T)\). Clearly, \(E_{d}\) and \(E_{p}\) have the same number of edges.
Denote the vertices of \(P(T)\)
successively as \(v_{1},v_{2},\cdots,v_{m}\) starting from
one pendant vertex of \(P(T)\) right up
to the other. Let \(u^{j}_{1},u^{j}_{2},\cdots,u^{j}_{n} \ (1 \leq j
\leq m)\) be the vertices of \(j^{th}\) copy of \(C_{n}\) with \(u^{j}_{1}=v_{j}\). Then \(V(T \widehat{O} C_{n})=\{u^{j}_{i} : 1 \leq i \leq
n, 1 \leq j \leq m \}\) and \(E(T
\widehat{O} C_{n})=E(T) \bigcup E(C_{n})\). Define
\(f:V(T \widehat{O} C_{n})\rightarrow
\{1,2,3,\dots,mn\}\) as follows:
Case 1. \(n \equiv 0 \ (mod \
4)\).
Choose ‘if \(j \equiv 1,2 \ (mod \
4)\)’ and \(1 \leq j \leq
m\),
\(f(u^{j}_{i})=\begin{cases}n(j-1)+i &
\text{ if } \ i \equiv 1,0 \ (mod \ 4) \ \text{and} \ 1 \leq i \leq n \\
n(j-1)+i+1 & \text{ if } \ i \equiv 2 \ (mod \ 4) \ \text{and} \ 1
\leq i \leq n \\ n(j-1)+i-1 & \text{ if } \ i \equiv 3 \ (mod \ 4) \
\text{and} \ 1 \leq i \leq n ;\end{cases}\)
choose ‘if \(j \equiv 3,0 \ (mod \
4)\)’ and \(1 \leq j \leq
m\),
\(f(u^{j}_{i})=\begin{cases}n(j-1)+i+1 &
\text{ if } \ i \equiv 1 \ (mod \ 4) \ \text{and} \ 1 \leq i \leq n \\
n(j-1)+i-1 & \text{ if } \ i \equiv 2 \ (mod \ 4) \ \text{and} \ 1
\leq i \leq n \\ n(j-1)+i & \text{ if } \ i \equiv 3,0 \ (mod \ 4) \
\text{and} \ 1 \leq i \leq n . \end{cases}\)
Let \(v_{i}v_{j}\) be a transformed edge in \(T\), \(1 \leq i<j \leq m\) and let \(P_{1}\) be the ept obtained by deleting the edge \(v_{i}v_{j}\) and adding the edge \(v_{i+t}v_{j-t}\) where \(t\) is the distance of \(v_{i}\) from \(v_{i+t}\) and the distance of \(v_{j}\) from \(v_{j-t}\). Let \(P\) be a parallel transformation of \(T\) that contains \(P_{1}\) as one of the constituent epts.
Since \(v_{i+t}v_{j-t}\) is an edge
in the path \(P(T)\), it follows that
\(i+t+1=j-t\) which implies \(j=i+2t+1\). Therefore, \(i\) and \(j\) are of opposite parity.
The induced edge label of \(v_{i}v_{j}\) is given by \[\begin{aligned}
f^{*}(v_{i}v_{j}) & = f^{*}(v_{i}v_{i+2t+1})\\ & = \begin{cases}
1 & \text{ if } \ i \ \text{is odd} \\ 0 & \text{ if } \ i \
\text{is even} .\end{cases}
\end{aligned}\] The induced edge label of \(v_{i+t}v_{j-t}\) is given by \[\begin{aligned}
f^{*}(v_{i+t}v_{j-t}) & = f^{*}(v_{i+t}v_{i+t+1})\\ & =
\begin{cases} 1 & \text{ if } \ i \ \text{is odd} \\ 0 & \text{
if } \ i \ \text{is even}. \end{cases}
\end{aligned}\] Therefore, \(f^{*}(v_{i}v_{j})=f^{*}(v_{i+t}v_{j-t})\).
The induced edge labels are as follows:
\(f^{*}(v_{j}v_{j+1})=\begin{cases} 1 &
\text{ if } \ j \ \text{is odd and} \ 1 \leq j \leq m-1 \\ 0 &
\text{ if } \ j \ \text{is even and} \ 1 \leq j \leq m-1 ;
\end{cases}\)
for \(1 \leq j \leq m\) and \(1 \leq i \leq n-1\),
\(f^{*}(u^{j}_{n}u^{j}_{1})=\begin{cases} 0
& \text{ if } \ j \equiv 1,2 \ (mod \ 4)\\ 1 & \text{ if } \ j
\equiv 3,0 \ (mod \ 4) ;\end{cases}\)
\(f^{*}(u^{j}_{i}u^{j}_{i+1})=\begin{cases} 1
& \text{ if } \ i \ \text{is odd and} \ j \equiv 1,2 \ (mod \ 4)\\ 0
& \text{ if } \ i \ \text{is even and} \ j \equiv 1,2 \ (mod \ 4) \\
0 & \text{ if } \ i \ \text{is odd and} \ j \equiv 3,0 \ (mod \ 4)\\
1 & \text{ if } \ i \ \text{is even and} \ j \equiv 3,0 \ (mod \ 4)
.\end{cases}\)
Case 2. \(n \equiv 3 \ (mod \
4)\).
Choose ‘if \(j \equiv 1,3 \ (mod \
4)\)’ and \(1 \leq j \leq
m\),
\(f(u^{j}_{i})=\begin{cases}n(j-1)+i &
\text{ if } \ i \equiv 1,0 \ (mod \ 4) \ \text{and} \ 1 \leq i \leq n \\
n(j-1)+i+1 & \text{ if } \ i \equiv 2 \ (mod \ 4) \ \text{and} \ 1
\leq i \leq n \\ n(j-1)+i-1 & \text{ if } \ i \equiv 3 \ (mod \ 4) \
\text{and} \ 1 \leq i \leq n ;\end{cases}\)
choose ‘if \(j \equiv 2,0 \ (mod \
4)\)’ and \(1 \leq j \leq
m\),
\(f(u^{j}_{i})=\begin{cases}n(j-1)+i+1 &
\text{ if } \ i \equiv 1 \ (mod \ 4) \ \text{and} \ 1 \leq i \leq n \\
n(j-1)+i-1 & \text{ if } \ i \equiv 2 \ (mod \ 4) \ \text{and} \ 1
\leq i \leq n \\ n(j-1)+i & \text{ if } \ i \equiv 3,0 \ (mod \ 4) \
\text{and} \ 1 \leq i \leq n .\end{cases}\)
Let \(v_{i}v_{j}\) be a transformed edge in \(T\), \(1 \leq i<j \leq m\) and let \(P_{1}\) be the ept obtained by deleting the edge \(v_{i}v_{j}\) and adding the edge \(v_{i+t}v_{j-t}\) where \(t\) is the distance of \(v_{i}\) from \(v_{i+t}\) and the distance of \(v_{j}\) from \(v_{j-t}\). Let \(P\) be a parallel transformation of \(T\) that contains \(P_{1}\) as one of the constituent epts.
Since \(v_{i+t}v_{j-t}\) is an edge
in the path \(P(T)\), it follows that
\(i+t+1=j-t\) which implies \(j=i+2t+1\). Therefore, \(i\) and \(j\) are of opposite parity.
The induced edge label of \(v_{i}v_{j}\) is given by \[\begin{aligned}
f^{*}(v_{i}v_{j}) & = f^{*}(v_{i}v_{i+2t+1})\\ & =
2|(f(v_{i})+f(v_{i+2t+1}))\\ & = 1.
\end{aligned}\] The induced edge label of \(v_{i+t}v_{j-t}\) is given by \[\begin{aligned}
f^{*}(v_{i+t}v_{j-t}) & = f^{*}(v_{i+t}v_{i+t+1})\\ & =
2|(f(v_{i+t})+f(v_{i+t+1}))\\ & = 1.
\end{aligned}\] Therefore, \(f^{*}(v_{i}v_{j})=f^{*}(v_{i+t}v_{j-t})\).
The induced edge labels are as follows:
\(f^{*}(v_{j}v_{j+1})=1, \ 1 \leq j \leq
m-1;\)
for \(1 \leq j \leq m\) and \(1 \leq i \leq n-1\),
\(f^{*}(u^{j}_{n}u^{j}_{1})=0;\)
\(f^{*}(u^{j}_{i}u^{j}_{i+1})=\begin{cases} 1
& \text{ if } \ i \ \text{is odd and} \ j \equiv 1,3 \ (mod \ 4)\\ 0
& \text{ if } \ i \ \text{is even and} \ j \equiv 1,3 \ (mod \ 4) \\
0 & \text{ if } \ i \ \text{is odd and} \ j \equiv 2,0 \ (mod \ 4)\\
1 & \text{ if } \ i \ \text{is even and} \ j \equiv 2,0 \ (mod \ 4)
.\end{cases}\)
Case 3. \(n \equiv 1 \ (mod \
4)\).
For \(1 \leq j \leq m\),
\(f(u^{j}_{i})=\begin{cases}n(j-1)+i &
\text{ if } \ i \equiv 1,0 \ (mod \ 4) \ \text{and} \ 1 \leq i \leq n \\
n(j-1)+i+1 & \text{ if } \ i \equiv 2 \ (mod \ 4) \ \text{and} \ 1
\leq i \leq n \\ n(j-1)+i-1 & \text{ if } \ i \equiv 3 \ (mod \ 4) \
\text{and} \ 1 \leq i \leq n . \end{cases}\)
Let \(v_{i}v_{j}\) be a transformed edge in \(T\), \(1 \leq i<j \leq m\) and let \(P_{1}\) be the ept obtained by deleting the edge \(v_{i}v_{j}\) and adding the edge \(v_{i+t}v_{j-t}\) where \(t\) is the distance of \(v_{i}\) from \(v_{i+t}\) and the distance of \(v_{j}\) from \(v_{j-t}\). Let \(P\) be a parallel transformation of \(T\) that contains \(P_{1}\) as one of the constituent epts.
Since \(v_{i+t}v_{j-t}\) is an edge
in the path \(P(T)\), it follows that
\(i+t+1=j-t\) which implies \(j=i+2t+1\). Therefore, \(i\) and \(j\) are of opposite parity.
The induced edge label of \(v_{i}v_{j}\) is given by \[\begin{aligned}
f^{*}(v_{i}v_{j}) & = f^{*}(v_{i}v_{i+2t+1})\\ & = 0.
\end{aligned}\] The induced edge label of \(v_{i+t}v_{j-t}\) is given by \[\begin{aligned}
f^{*}(v_{i+t}v_{j-t}) & = f^{*}(v_{i+t}v_{i+t+1})\\ & = 0.
\end{aligned}\] Therefore, \(f^{*}(v_{i}v_{j})=f^{*}(v_{i+t}v_{j-t})\).
The induced edge labels are as follows:
\(f^{*}(v_{j}v_{j+1})=0, \ 1 \leq j \leq
m-1;\)
for \(1 \leq j \leq m\) and \(1 \leq i \leq n-1\),
\(f^{*}(u^{j}_{n}u^{j}_{1})=1;\)
\(f^{*}(u^{j}_{i}u^{j}_{i+1})=\begin{cases} 1
& \text{ if } \ i \ \text{is odd and} \ j \equiv 1,3 \ (mod \
4)\\ 0 & \text{ if } \ i \ \text{is even and} \ j \equiv 1,3 \ (mod
\ 4)\\
1 & \text{ if } \ i \ \text{is odd and} \ j \equiv 2,0 \ (mod \ 4)\\
0 & \text{ if } \ i \ \text{is even and} \ j \equiv 2,0 \ (mod \ 4)
.\end{cases}\)
In the above three cases, it can be verified that \(|e_{f}(0)-e_{f}(1)| \leq 1\). Hence \(T \widehat{O} C_{n}\) is sum divisor
cordial graph. ◻
Example 2. Sum divisor cordial labeling of \(T \widehat{O} C_{7}\) where \(T\) is a \(T_{p}\)-tree with 8 vertices is shown in Figure 3.
Theorem 4. If \(T\) be a \(T_{p}\)-tree on \(m\) vertices, then the graph \(T \widehat{O} K_{1,n}\) is sum divisor cordial graph.
Proof. Let \(T\) be a \(T_{p}\)-tree with \(m\) vertices. By the definition of a
transformed tree there exists a parallel transformation \(P\) of \(T\) such that for the path \(P(T)\), we have \((i) \ V(P(T))=V(T)\) and \((ii) \ E(P(T))=(E(T)-E_{d}) \bigcup
E_{p}\), where \(E_{d}\) is the
set of edges deleted from \(T\) and
\(E_{p}\) is the set of edges newly
added through the sequence \(P=(P_{1},P_{2},\cdots,P_{k})\) of the
epts \(P\) used to arrive at
the path \(P(T)\). Clearly, \(E_{d}\) and \(E_{p}\) have the same number of edges.
Denote the vertices of \(P(T)\)
successively as \(v_{1},v_{2},\cdots,v_{m}\) starting from
one pendant vertex of \(P(T)\) right up
to the other. Let \(u^{j}_{0},u^{j}_{1},\cdots,u^{j}_{n}(1 \leq j \leq
m)\) be the vertices of \(j^{th}\) copy of \(K_{1,n}\) with \(u^{j}_{n}=v_{j}\). Then \(V(T \widehat{O}
K_{1,n})=\{v_{j},u^{j}_{0},u^{j}_{i} : 1 \leq i \leq n, 1 \leq j \leq m
\ \text{with} \ v_{j}=u^{j}_{n}\}\) and \(E(T \widehat{O} K_{1,n})=E(T) \bigcup
\{u^{j}_{0}u^{j}_{i} : \ 1 \leq j \leq m, \ 1 \leq i \leq n
\}\).
Define \(f:V(T \widehat{O} K_{1,n})
\rightarrow \{1,2,\cdots,mn+m \}\) as follows:
For \(1 \leq j \leq m\),
\(f(v_{j})=2j;\)
\(f(u^{j}_{0})=2j-1;\)
\(f(u^{j}_{i})=2m+(n-1)(j-1)+i, \ 1 \leq i
\leq n-1.\)
Let \(v_{i}v_{j}\) be a transformed
edge in \(T\), \(1 \leq i<j \leq m\) and let \(P_{1}\) be the ept obtained by
deleting the edge \(v_{i}v_{j}\) and
adding the edge \(v_{i+t}v_{j-t}\)
where \(t\) is the distance of \(v_{i}\) from \(v_{i+t}\) and the distance of \(v_{j}\) from \(v_{j-t}\). Let \(P\) be a parallel transformation of \(T\) that contains \(P_{1}\) as one of the constituent
epts. Since \(v_{i+t}v_{j-t}\)
is an edge in the path \(P(T)\), it
follows that \(i+t+1=j-t\) which
implies \(j=i+2t+1\). Therefore, \(i\) and \(j\) are of opposite parity.
The induced edge label of \(v_{i}v_{j}\) is given by \[\begin{aligned}
f^{*}(v_{i}v_{j}) & = f^{*}(v_{i}v_{i+2t+1})\\ & =
2|(f(v_{i})+f(v_{i+2t+1}))\\ & = 1.
\end{aligned}\] The induced edge label of \(v_{i+t}v_{j-t}\) is given by \[\begin{aligned}
f^{*}(v_{i+t}v_{j-t}) & = f^{*}(v_{i+t}v_{i+t+1})\\ & =
2|(f(v_{i+t})+f(v_{i+t+1}))\\ & = 1.
\end{aligned}\] Therefore, \(f^{*}(v_{i}v_{j})=f^{*}(v_{i+t}v_{j-t})\).
The induced edge labels are as follows:
\(f^{*}(v_{j}v_{j+1})=1, \ 1 \leq j \leq
m-1;\)
for \(1 \leq j \leq m\),
\(f^{*}(u^{j}_{0}u^{j}_{n})=0\);
when \(n\) is odd and \(1 \leq i \leq n-1\),
\(f^{*}(u^{j}_{0}u^{j}_{i})=\begin{cases}1
& \text{ if } \ i \ \text{is odd} \\ 0 & \text{ if } \ i \
\text{is even}; \end{cases}\)
when \(n\) is even and \(1 \leq i \leq n-1\),
\(f^{*}(u^{j}_{0}u^{j}_{i})=\begin{cases} 1
& \text{ if } \ i \ \text{is odd and} \ j \ \text{is odd} \\ 0 &
\text{ if } \ i \ \text{is even and} \ j \ \text{is odd} \\ 0 &
\text{ if } \ i \ \text{is odd and} \ j \ \text{is even} \\ 1 &
\text{ if } \ i \ \text{is even and} \ j \ \text{is even}.
\end{cases}\)
In view of above labeling we get,
when \(m\) is odd and \(n\) is even,
\(e_{f}(0)=e_{f}(1)=\frac{mn+m-1}{2}\);
when \(m\) is odd and \(n\) is odd,
\(e_{f}(0)=\left\lceil
\frac{mn+m-1}{2}\right\rceil\) and \(e_{f}(1)=\left\lfloor \frac{mn+m-1}{2}
\right\rfloor\);
when \(m\) is even and \(n\) is odd or even,
\(e_{f}(0)=\left\lceil
\frac{mn+m-1}{2}\right\rceil\) and \(e_{f}(1)=\left\lfloor \frac{mn+m-1}{2}
\right\rfloor\).
Clearly \(|e_{f}(0)-e_{f}(1)| \leq 1\).
Hence \(T \widehat{O} K_{1,n}\) is sum
divisor cordial graph. ◻
Example 3. Sum divisor cordial labeling of \(T \widehat{O} K_{1,3}\) where \(T\) is a \(T_{p}\)-tree with 12 vertices is shown in Figure 4.
Theorem 5. If \(T\) be a \(T_{p}\)-tree on \(m\) vertices, then the graph \(T \odot \overline{K_{n}}\) is sum divisor cordial graph.
Proof. Let \(T\) be a \(T_{p}\)-tree with \(m\) vertices. By the definition of \(T_{p}\)-tree there exists a parallel
transformation \(P\) of \(T\) such that for the path \(P(T)\), we have \((i) \ V(P(T))=V(T)\) and \((ii) \ E(P(T))=(E(T)-E_{d}) \bigcup
E_{p}\), where \(E_{d}\) is the
set of edges deleted from \(T\) and
\(E_{p}\) is the set of edges newly
added through the sequence \(P=(P_{1},P_{2},\cdots,P_{k})\) of the
epts \(P\) used to arrive at
the path \(P(T)\). Clearly, \(E_{d}\) and \(E_{p}\) have the same number of edges.
Denote the vertices of \(P(T)\)
successively as \(v_{1},v_{2},\cdots,v_{m}\) starting from
one pendant vertex of \(P(T)\) right up
to the other. Let \(u^{j}_{1},u^{j}_{2},\cdots,u^{j}_{n}(1 \leq j \leq
m)\) be the pendant vertices joined with \(v_{j}(1 \leq j \leq m)\) by an edge. Then
\(V(T \odot
\overline{K_{n}})=\{v_{j},u^{j}_{i} : 1 \leq i \leq n, 1 \leq j \leq m
\}\) and \(E(T \odot
\overline{K_{n}})=E(T) \bigcup \{v_{j}u^{j}_{i}: \ 1 \leq j \leq m, \ 1
\leq i \leq n \}\).
Define \(f:V(T \odot
\overline{K_{n}})\rightarrow \{1,2,\cdots,mn+m \}\) as
follows:
For \(1 \leq j \leq m\),
\(f(v_{j})=2j-1;\)
\(f(u^{j}_{n})=2j;\)
\(f(u^{j}_{i})=2m+(n-1)(j-1)+i, \ 1 \leq i
\leq n-1.\)
Let \(v_{i}v_{j}\) be a transformed
edge in \(T\), \(1 \leq i<j \leq m\) and let \(P_{1}\) be the ept obtained by
deleting the edge \(v_{i}v_{j}\) and
adding the edge \(v_{i+t}v_{j-t}\)
where \(t\) is the distance of \(v_{i}\) from \(v_{i+t}\) and the distance of \(v_{j}\) from \(v_{j-t}\). Let \(P\) be a parallel transformation of \(T\) that contains \(P_{1}\) as one of the constituent
epts. Since \(v_{i+t}v_{j-t}\)
is an edge in the path \(P(T)\), it
follows that \(i+t+1=j-t\) which
implies \(j=i+2t+1\). Therefore, \(i\) and \(j\) are of opposite parity.
The induced edge label of \(v_{i}v_{j}\) is given by \[\begin{aligned}
f^{*}(v_{i}v_{j}) & = f^{*}(v_{i}v_{i+2t+1})\\ & =
2|(f(v_{i})+f(v_{i+2t+1}))\\ & = 1.
\end{aligned}\] The induced edge label of \(v_{i+t}v_{j-t}\) is given by \[\begin{aligned}
f^{*}(v_{i+t}v_{j-t}) & = f^{*}(v_{i+t}v_{i+t+1})\\ & =
2|(f(v_{i+t})+f(v_{i+t+1}))\\ & = 1.
\end{aligned}\] Therefore, \(f^{*}(v_{i}v_{j})=f^{*}(v_{i+t}v_{j-t})\).
The induced edge labels are as follows:
\(f^{*}(v_{j}v_{j+1})=1, \ 1 \leq j \leq
m-1;\)
for \(1 \leq j \leq m\),
\(f^{*}(v_{j}u^{j}_{n})=0;\)
when \(n\) is odd and \(1 \leq i \leq n-1\),
\(f^{*}(v_{j}u^{j}_{i})=\begin{cases}1 &
\text{ if } \ i \ \text{is odd} \\ 0 & \text{ if } \ i \ \text{is
even}; \end{cases}\)
when \(n\) is even and \(1 \leq i \leq n-1\),
\(f^{*}(v_{j}u^{j}_{i})=\begin{cases} 1 &
\text{ if } \ i \ \text{is odd and} \ j \ \text{is odd} \\ 0 &
\text{ if } \ i \ \text{is even and} \ j \ \text{is odd} \\ 0 &
\text{ if } \ i \ \text{is odd and} \ j \ \text{is even} \\ 1 &
\text{ if } \ i \ \text{is even and} \ j \ \text{is even}.
\end{cases}\)
It can be verified that \(|e_{f}(0)-e_{f}(1)|
\leq 1\). Hence \(T \odot
\overline{K_{n}}\) is sum divisor cordial graph. ◻
Example 4. Sum divisor cordial labeling of \(T \odot \overline{K_{4}}\) where \(T\) is a \(T_{p}\)-tree with 10 vertices is shown in Figure 5.
Theorem 6. If \(T\) be a \(T_{p}\)-tree on \(m\) vertices, then the graph \(T \widehat{O} Q_{n}\) is sum divisor cordial graph.
Proof. Let \(T\) be a \(T_{p}\)-tree with \(m\) vertices. By the definition of a
transformed tree there exists a parallel transformation \(P\) of \(T\) such that for the path \(P(T)\), we have \((i) \ V(P(T))=V(T)\) and \((ii) \ E(P(T))=(E(T)-E_{d}) \bigcup
E_{p}\), where \(E_{d}\) is the
set of edges deleted from \(T\) and
\(E_{p}\) is the set of edges newly
added through the sequence \(P=(P_{1},P_{2},\cdots,P_{k})\) of the
epts \(P\) used to arrive at
the path \(P(T)\). Clearly, \(E_{d}\) and \(E_{p}\) have the same number of edges.
Denote the vertices of \(P(T)\)
successively as \(v_{1},v_{2},\cdots,v_{m}\) starting from
one pendant vertex of \(P(T)\) right up
to the other. Let \(u^{j}_{1},u^{j}_{2},\cdots,u^{j}_{n},u^{j}_{n+1}(1
\leq j \leq m)\) be the vertices of \(j^{th}\) copy of \(Q_{n}\) with \(u^{j}_{n+1}=v_{j}\). Then \(V(T \widehat{O} Q_{n})=\{u^{j}_{i} : 1 \leq i \leq
n+1, 1 \leq j \leq m \} \bigcup \{x^{j}_{i}, y^{j}_{i} : 1 \leq i \leq
n, 1 \leq j \leq m \}\) and \(E(T
\widehat{O} Q_{n})=E(T) \bigcup E(Q_{n})\). We note that \(\left|V(T \widehat{O} Q_{n})\right|=3nm+m\)
and \(\left|E(T \widehat{O}
Q_{n})\right|=4mn+m-1\). Define \(f:V(T
\widehat{O} Q_{n})\rightarrow \{1,2,\cdots,3mn+m \}\) as
follows:
Case 1.1] \(m\) is odd.
For \(1 \leq j \leq m\) and \(1 \leq i \leq n\),
\(f(u^{j}_{i})=m+3n(j-1)+3i-2;\)
\(f(x^{j}_{i})=m+3n(j-1)+3i-1;\)
\(f(y^{j}_{i})=m+3n(j-1)+3i;\)
\(f(v_{j})=f(u^{j}_{n+1})=\begin{cases}j &
\text{ if } \ j \equiv 1,0 \ (mod \ 4)\\ j+1 & \text{ if } \ j
\equiv 2 \ (mod \ 4)\\ j-1 & \text{ if } \ j \equiv 3 \ (mod \ 4) \
.\end{cases}\)
Let \(v_{i}v_{j}\) be a transformed edge in \(T\), \(1 \leq i<j \leq m\) and let \(P_{1}\) be the ept obtained by deleting the edge \(v_{i}v_{j}\) and adding the edge \(v_{i+t}v_{j-t}\) where \(t\) is the distance of \(v_{i}\) from \(v_{i+t}\) and the distance of \(v_{j}\) from \(v_{j-t}\). Let \(P\) be a parallel transformation of \(T\) that contains \(P_{1}\) as one of the constituent epts.
Since \(v_{i+t}v_{j-t}\) is an edge
in the path \(P(T)\), it follows that
\(i+t+1=j-t\) which implies \(j=i+2t+1\). Therefore, \(i\) and \(j\) are of opposite parity.
The induced edge label of \(v_{i}v_{j}\) is given by \[\begin{aligned}
f^{*}(v_{i}v_{j}) & = f^{*}(v_{i}v_{i+2t+1})\\ & =
\begin{cases}1 & \text{ if } \ i \ \text{is odd}\\ 0 & \text{ if
} \ i \ \text{is even} .\end{cases}
\end{aligned}\] The induced edge label of \(v_{i+t}v_{j-t}\) is given by \[\begin{aligned}
f^{*}(v_{i+t}v_{j-t}) & = f^{*}(v_{i+t}v_{i+t+1})\\ & =
\begin{cases}1 & \text{ if } \ i \ \text{is odd}\\ 0 & \text{ if
} \ i \ \text{is even} .\end{cases}
\end{aligned}\] Therefore, \(f^{*}(v_{i}v_{j})=f^{*}(v_{i+t}v_{j-t})\).
The induced edge labels are as follows:
\(f^{*}(v_{j}v_{j+1})=\begin{cases}1 &
\text{ if } \ i \ \text{is odd and} \ 1 \leq j \leq m-1\\ 0 & \text{
if } \ i \ \text{is even and} \ 1 \leq j \leq
m-1;\end{cases}\)
for \(1 \leq j \leq m\),
\(f^{*}(u^{j}_{i}x^{j}_{i})=0, \ 1 \leq i \leq
n;\)
\(f^{*}(u^{j}_{i}y^{j}_{i})=1, \ 1 \leq i \leq
n;\)
\(f^{*}(x^{j}_{i}u^{j}_{i+1})=1, \ 1 \leq i
\leq n-1;\)
\(f^{*}(y^{j}_{i}u^{j}_{i+1})=0, \ 1 \leq i
\leq n-1;\)
\(f^{*}(x^{j}_{n}v_{j})=\begin{cases}1 &
\text{ if } \ n \ \text{is odd and} \ j \equiv 1,0 \ (mod \ 4)\\ 0 &
\text{ if } \ n \ \text{is odd and} \ j \equiv 2,3 \ (mod \ 4)\\ 0 &
\text{ if } \ n \ \text{is even and} \ j \equiv 1,2 \ (mod \ 4)\\ 1
& \text{ if } \ n \ \text{is even and} \ j \equiv 3,0 \ (mod \
4);\end{cases}\)
\(f^{*}(y^{j}_{n}v_{j})=\begin{cases}0 &
\text{ if } \ n \ \text{is odd and} \ j \equiv 1,0 \ (mod \ 4)\\ 1 &
\text{ if } \ n \ \text{is odd and} \ j \equiv 2,3 \ (mod \ 4)\\ 1 &
\text{ if } \ n \ \text{is even and} \ j \equiv 1,2 \ (mod \ 4)\\ 0
& \text{ if } \ n \ \text{is even and} \ j \equiv 3,0 \ (mod \
4).\end{cases}\)
Case 2.1] \(m\) is even.
For \(1 \leq j \leq m\) and \(1 \leq i \leq n\),
\(f(u^{j}_{i})=m+3n(j-1)+3i-2;\)
\(f(x^{j}_{i})=m+3n(j-1)+3i-1;\)
\(f(y^{j}_{i})=m+3n(j-1)+3i;\)
\(f(v_{j})=f(u^{j}_{n+1})=\begin{cases}j &
\text{ if } \ j \equiv 1,2 \ (mod \ 4)\\ j+1 & \text{ if } \ j
\equiv 3 \ (mod \ 4)\\ j-1 & \text{ if } \ j \equiv 0 \ (mod \ 4) \
.\end{cases}\)
Let \(v_{i}v_{j}\) be a transformed edge in \(T\), \(1 \leq i<j \leq m\) and let \(P_{1}\) be the ept obtained by deleting the edge \(v_{i}v_{j}\) and adding the edge \(v_{i+t}v_{j-t}\) where \(t\) is the distance of \(v_{i}\) from \(v_{i+t}\) and the distance of \(v_{j}\) from \(v_{j-t}\). Let \(P\) be a parallel transformation of \(T\) that contains \(P_{1}\) as one of the constituent epts.
Since \(v_{i+t}v_{j-t}\) is an edge
in the path \(P(T)\), it follows that
\(i+t+1=j-t\) which implies \(j=i+2t+1\). Therefore, \(i\) and \(j\) are of opposite parity.
The induced edge label of \(v_{i}v_{j}\) is given by \[\begin{aligned}
f^{*}(v_{i}v_{j}) & = f^{*}(v_{i}v_{i+2t+1})\\ & =
\begin{cases}0 & \text{ if } \ i \ \text{is odd}\\ 1 & \text{ if
} \ i \ \text{is even} .\end{cases}
\end{aligned}\] The induced edge label of \(v_{i+t}v_{j-t}\) is given by \[\begin{aligned}
f^{*}(v_{i+t}v_{j-t}) & = f^{*}(v_{i+t}v_{i+t+1})\\ & =
\begin{cases}0 & \text{ if } \ i \ \text{is odd}\\ 1 & \text{ if
} \ i \ \text{is even} .\end{cases}
\end{aligned}\] Therefore, \(f^{*}(v_{i}v_{j})=f^{*}(v_{i+t}v_{j-t})\).
The induced edge labels are as follows:
\(f^{*}(v_{j}v_{j+1})=\begin{cases}0 &
\text{ if } \ i \ \text{is odd and} \ 1 \leq j \leq m-1\\ 1 & \text{
if } \ i \ \text{is even and} \ 1 \leq j \leq
m-1;\end{cases}\)
for \(1 \leq j \leq m\),
\(f^{*}(u^{j}_{i}x^{j}_{i})=0, \ 1 \leq i \leq
n;\)
\(f^{*}(u^{j}_{i}y^{j}_{i})=1, \ 1 \leq i \leq
n;\)
\(f^{*}(x^{j}_{i}u^{j}_{i+1})=1, \ 1 \leq i
\leq n-1;\)
\(f^{*}(y^{j}_{i}u^{j}_{i+1})=0, \ 1 \leq i
\leq n-1;\)
\(f^{*}(x^{j}_{n}v_{j})=\begin{cases}0 &
\text{ if } \ n \ \text{is odd and} \ j \equiv 1,2 \ (mod \ 4)\\ 1 &
\text{ if } \ n \ \text{is odd and} \ j \equiv 3,0 \ (mod \ 4)\\ 1 &
\text{ if } \ n \ \text{is even and} \ j \equiv 1,0 \ (mod \ 4)\\ 0
& \text{ if } \ n \ \text{is even and} \ j \equiv 2,3 \ (mod \
4);\end{cases}\)
\(f^{*}(y^{j}_{n}v_{j})=\begin{cases}1 &
\text{ if } \ n \ \text{is odd and} \ j \equiv 1,2 \ (mod \ 4)\\ 0 &
\text{ if } \ n \ \text{is odd and} \ j \equiv 3,0 \ (mod \ 4)\\ 1 &
\text{ if } \ n \ \text{is even and} \ j \equiv 2,3 \ (mod \ 4)\\ 0
& \text{ if } \ n \ \text{is even and} \ j \equiv 1,0 \ (mod \
4).\end{cases}\)
In the above two cases,
when \(m\) is odd,
\(e_{f}(1)=e_{f}(0)=
\frac{4mn+m-1}{2}\);
when \(m\) is even,
\(e_{f}(1)=\left\lfloor
\frac{4mn+m-1}{2}\right\rfloor\) and \(e_{f}(0)=\left\lceil \frac{4mn+m-1}{2}
\right\rceil\).
It can be verified that \(|e_{f}(0)-e_{f}(1)|
\leq 1\). Hence \(T \widehat{O}
Q_{n}\) is sum divisor cordial graph. ◻
Example 5. Sum divisor cordial labeling of \(T \widehat{O} Q_{2}\) where \(T\) is a \(T_{p}\)-tree with 8 vertices is shown in Figure \(6\).
Theorem 7. If \(T\) be a \(T_{p}\)-tree on \(m\) vertices, then the graph \(T \widetilde{O} C_{n}\) is sum divisor cordial graph if \(n \equiv 0,3,1 \ (mod \ 4)\).
Proof. Let \(T\) be a \(T_{p}\)-tree with \(m\) vertices. By the definition of a
transformed tree there exists a parallel transformation \(P\) of \(T\) such that for the path \(P(T)\), we have \((i) \ V(P(T))=V(T)\) and \((ii) \ E(P(T))=(E(T)-E_{d}) \bigcup
E_{p}\), where \(E_{d}\) is the
set of edges deleted from \(T\) and
\(E_{p}\) is the set of edges newly
added through the sequence \(P=(P_{1},P_{2},\cdots,P_{k})\) of the
epts \(P\) used to arrive at
the path \(P(T)\). Clearly, \(E_{d}\) and \(E_{p}\) have the same number of edges.
Denote the vertices of \(P(T)\)
successively as \(v_{1},v_{2},\cdots,v_{m}\) starting from
one pendant vertex of \(P(T)\) right up
to the other. Let \(u^{j}_{1},u^{j}_{2},\cdots,u^{j}_{n}(1 \leq j \leq
m)\) be the vertices of \(j^{th}\) copy of \(C_{n}\). Then \(V(T \widetilde{O} C_{n})=\{v_{j},u^{j}_{i} : 1
\leq i \leq n, \ 1 \leq j \leq m \}\) and \(E(T \widetilde{O} C_{n})=E(T) \bigcup
E(C_{n})\bigcup \{v_{j}u^{j}_{1}: 1 \leq j \leq m \}\). Define
\(f:V(T \widetilde{O} C_{n})\rightarrow
\{1,2,\dots,mn+m\}\) as follows:
Case 1. \(n \equiv 0 \ (mod \
4)\).
\(f(v_{j})=(n+1)j, 1 \leq j \leq m
;\)
for \(1 \leq j \leq m\) and \(1 \leq i \leq n\),
\(f(u^{j}_{i})=\begin{cases}(n+1)(j-1)+i &
\text{ if } \ i \equiv 1,0 \ (mod \ 4) \\ (n+1)(j-1)+i+1 & \text{ if
} \ i \equiv 2 \ (mod \ 4) \\ (n+1)(j-1)+i-1 & \text{ if } \ i
\equiv 3 \ (mod \ 4) \ .\end{cases}\)
Let \(v_{i}v_{j}\) be a transformed
edge in \(T\), \(1 \leq i<j \leq m\) and let \(P_{1}\) be the ept obtained by
deleting the edge \(v_{i}v_{j}\) and
adding the edge \(v_{i+t}v_{j-t}\)
where \(t\) is the distance of \(v_{i}\) from \(v_{i+t}\) and also the distance of \(v_{j}\) from \(v_{j-t}\). Let \(P\) be a parallel transformation of \(T\) that contains \(P_{1}\) as one of the constituent
epts. Since \(v_{i+t}v_{j-t}\)
is an edge in the path \(P(T)\), it
follows that \(i+t+1=j-t\) which
implies \(j=i+2t+1\). Therefore, \(i\) and \(j\) are of opposite parity.
The induced edge label of \(v_{i}v_{j}\) is given by \[\begin{aligned}
f^{*}(v_{i}v_{j}) & = f^{*}(v_{i}v_{i+2t+1})\\ & = 0.
\end{aligned}\] The induced edge label of \(v_{i+t}v_{j-t}\) is given by \[\begin{aligned}
f^{*}(v_{i+t}v_{j-t}) & = f^{*}(v_{i+t}v_{i+t+1})\\ & = 0.
\end{aligned}\] Therefore, \(f^{*}(v_{i}v_{j})=f^{*}(v_{i+t}v_{j-t})\).
The induced edge labels are as follows:
\(f^{*}(v_{j}v_{j+1})=0, \ 1 \leq j \leq
m-1;\)
\(f^{*}(u^{j}_{1}v_{j})=1, \ 1 \leq j \leq
m\);
\(f^{*}(u^{j}_{n}u^{j}_{1})= 0, \ 1 \leq j
\leq m\);
for \(1 \leq j \leq m\),
\(f^{*}(u^{j}_{i}u^{j}_{i+1})=\begin{cases}1
& \text{ if } \ i \ \text{is odd and} \ 1 \leq i \leq n-1 \\ 0 &
\text{ if } \ j \ \text{is even and} \ 1 \leq i \leq n-1.
\end{cases}\)
Case 2. \(n \equiv 3 \ (mod \
4)\).
\(f(v_{j})=\begin{cases}(n+1)j & \text{ if
} \ j \equiv 1,2 \ (mod \ 4) \ \text{and} \ 1 \leq j \leq m \\
(n+1)(j-1)+1 & \text{ if } \ j \equiv 3,0 \ (mod \ 4) \ \text{and} \
1 \leq j \leq m \ ;\end{cases}\)
choose ‘if \(j \equiv 1,2 \ (mod \
4)\)’ and \(1 \leq j \leq
m\),
\(f(u^{j}_{i})=\begin{cases}(n+1)(j-1)+i+1
& \text{ if } \ i \equiv 1 \ (mod \ 4) \ \text{and} \ 1 \leq i \leq
n \\ (n+1)(j-1)+i-1 & \text{ if } \ i \equiv 2 \ (mod \ 4) \
\text{and} \ 1 \leq i \leq n\\ (n+1)(j-1)+i & \text{ if } \ i \equiv
3,0 \ (mod \ 4) \ \text{and} \ 1 \leq i \leq n \
;\end{cases}\)
choose ‘if \(j \equiv 3,0 \ (mod \
4)\)’ and \(1 \leq j \leq
m\),
\(f(u^{j}_{i})=\begin{cases}(n+1)(j-1)+i+2
& \text{ if } \ i \equiv 1 \ (mod \ 4) \ \text{and} \ 1 \leq i \leq
n \\ (n+1)(j-1)+i & \text{ if } \ i \equiv 2 \ (mod \ 4) \
\text{and} \ 1 \leq i \leq n\\ (n+1)(j-1)+i+1 & \text{ if } \ i
\equiv 3,0 \ (mod \ 4) \ \text{and} \ 1 \leq i \leq n \
.\end{cases}\)
Let \(v_{i}v_{j}\) be a transformed
edge in \(T\), \(1 \leq i<j \leq m\) and let \(P_{1}\) be the ept obtained by
deleting the edge \(v_{i}v_{j}\) and
adding the edge \(v_{i+t}v_{j-t}\)
where \(t\) is the distance of \(v_{i}\) from \(v_{i+t}\) and the distance of \(v_{j}\) from \(v_{j-t}\). Let \(P\) be a parallel transformation of \(T\) that contains \(P_{1}\) as one of the constituent
epts. Since \(v_{i+t}v_{j-t}\)
is an edge in the path \(P(T)\), it
follows that \(i+t+1=j-t\) which
implies \(j=i+2t+1\). Therefore, \(i\) and \(j\) are of opposite parity.
The induced edge label of \(v_{i}v_{j}\) is given by \[\begin{aligned}
f^{*}(v_{i}v_{j}) & = f^{*}(v_{i}v_{i+2t+1})\\ & =
\begin{cases}1 & \text{if} \ i \ \text{is odd} \\ 0 & \text{if}
\ i \ \text{is even} .\end{cases}
\end{aligned}\] The induced edge label of \(v_{i+t}v_{j-t}\) is given by \[\begin{aligned}
f^{*}(v_{i+t}v_{j-t}) & = f^{*}(v_{i+t}v_{i+t+1})\\ & =
\begin{cases}1 & \text{if} \ i \ \text{is odd} \\ 0 & \text{if}
\ i \ \text{is even} .\end{cases}
\end{aligned}\] Therefore, \(f^{*}(v_{i}v_{j})=f^{*}(v_{i+t}v_{j-t})\).
The induced edge labels are as follows:
\(f^{*}(v_{j}v_{j+1})=\begin{cases}1 &
\text{if} \ i \ \text{is odd and} \ 1 \leq j \leq m-1 \\ 0 &
\text{if} \ i \ \text{is even and} \ 1 \leq j \leq m-1 \
;\end{cases}\)
for \(1 \leq j \leq m\),
\(f^{*}(u^{j}_{1}v_{j})=1;\)
\(f^{*}(u^{j}_{n}u^{j}_{1})=0;\)
\(f^{*}(u^{j}_{i}u^{j}_{i+1})=\begin{cases} 0
& \text{if} \ i \ \text{is odd and} \ 1 \leq i \leq n-1 \\ 1 &
\text{if} \ i \ \text{is even and} \ 1 \leq i \leq n-1 \
.\end{cases}\)
Case 3. \(n \equiv 1 \ (mod \
4)\).
\(f(v_{j})=\begin{cases}(n+1)j & \text{ if
} \ j \equiv 1,2 \ (mod \ 4) \ \text{and} \ 1 \leq j \leq m \\
(n+1)(j-1)+1 & \text{ if } \ j \equiv 3,0 \ (mod \ 4) \ \text{and} \
1 \leq j \leq m \ ;\end{cases}\)
choose ‘if \(j \equiv 1,2 \ (mod \
4)\)’ and \(1 \leq j \leq
m\),
\(f(u^{j}_{i})=\begin{cases}(n+1)(j-1)+i &
\text{ if } \ i \equiv 1,0 \ (mod \ 4) \ \text{and} \ 1 \leq i \leq n \\
(n+1)(j-1)+i+1 & \text{ if } \ i \equiv 2 \ (mod \ 4) \ \text{and} \
1 \leq i \leq n\\ (n+1)(j-1)+i-1 & \text{ if } \ i \equiv 3 \ (mod \
4) \ \text{and} \ 1 \leq i \leq n \ ;\end{cases}\)
choose ‘if \(j \equiv 3,0 \ (mod \
4)\)’ and \(1 \leq j \leq
m\),
\(f(u^{j}_{i})=\begin{cases}(n+1)(j-1)+i+1
& \text{ if } \ i \equiv 1,0 \ (mod \ 4) \ \text{and} \ 1 \leq i
\leq n \\ (n+1)(j-1)+i+2 & \text{ if } \ i \equiv 2 \ (mod \ 4) \
\text{and} \ 1 \leq i \leq n\\ (n+1)(j-1)+i & \text{ if } \ i \equiv
3 \ (mod \ 4) \ \text{and} \ 1 \leq i \leq n \
;\end{cases}\)
Let \(v_{i}v_{j}\) be a transformed
edge in \(T\), \(1 \leq i<j \leq m\) and let \(P_{1}\) be the ept obtained by
deleting the edge \(v_{i}v_{j}\) and
adding the edge \(v_{i+t}v_{j-t}\)
where \(t\) is the distance of \(v_{i}\) from \(v_{i+t}\) and the distance of \(v_{j}\) from \(v_{j-t}\). Let \(P\) be a parallel transformation of \(T\) that contains \(P_{1}\) as one of the constituent
epts. Since \(v_{i+t}v_{j-t}\)
is an edge in the path \(P(T)\), it
follows that \(i+t+1=j-t\) which
implies \(j=i+2t+1\). Therefore, \(i\) and \(j\) are of opposite parity.
The induced edge label of \(v_{i}v_{j}\) is given by \[\begin{aligned}
f^{*}(v_{i}v_{j}) & = f^{*}(v_{i}v_{i+2t+1})\\ & =
\begin{cases}1 & \text{if} \ i \ \text{is odd} \\ 0 & \text{if}
\ i \ \text{is even} .\end{cases}
\end{aligned}\] The induced edge label of \(v_{i+t}v_{j-t}\) is given by \[\begin{aligned}
f^{*}(v_{i+t}v_{j-t}) & = f^{*}(v_{i+t}v_{i+t+1})\\ & =
\begin{cases}1 & \text{if} \ i \ \text{is odd} \\ 0 & \text{if}
\ i \ \text{is even} .\end{cases}
\end{aligned}\] Therefore, \(f^{*}(v_{i}v_{j})=f^{*}(v_{i+t}v_{j-t})\).
The induced edge labels are as follows:
\(f^{*}(v_{j}v_{j+1})=\begin{cases}1 &
\text{if} \ i \ \text{is odd and} \ 1 \leq j \leq m-1 \\ 0 &
\text{if} \ i \ \text{is even and} \ 1 \leq j \leq m-1 \
;\end{cases}\)
for \(1 \leq j \leq m\),
\(f^{*}(u^{j}_{1}v_{j})=0;\)
\(f^{*}(u^{j}_{n}u^{j}_{1})=1;\)
\(f^{*}(u^{j}_{i}u^{j}_{i+1})=\begin{cases} 1
& \text{if} \ i \ \text{is odd and} \ 1 \leq i \leq n-1 \\ 0 &
\text{if} \ i \ \text{is even and} \ 1 \leq i \leq n-1 \
.\end{cases}\)
In the above three cases,
when \(m\) is odd,
\(e_{f}(1)=\begin{cases} \frac{mn+2m-1}{2}
& \text{if} \ n \equiv 1,3 \ (mod \ 4) \\ \left\lceil
\frac{mn+2m-1}{2}\right\rceil & \text{if} \ n \equiv 0 \ (mod \ 4) ,
\end{cases}\)
\(e_{f}(0)=\begin{cases} \frac{mn+2m-1}{2}
& \text{if} \ n \equiv 1,3 \ (mod \ 4) \\ \left\lfloor
\frac{mn+2m-1}{2} \right\rfloor & \text{if} \ n \equiv 0 \ (mod \
4); \end{cases}\)
when \(m\) is even and \(n \equiv 1,3,0 \ (mod \ 4)\),
\(e_{f}(1)=\left\lceil
\frac{mn+2m-1}{2}\right\rceil\) and \(e_{f}(0)=\left\lfloor \frac{mn+2m-1}{2}
\right\rfloor\).
It can be verified that \(|e_{f}(0)-e_{f}(1)|
\leq 1\). Hence \(T \widetilde{O}
C_{n}\) is sum divisor cordial graph. ◻
Example 6. Sum divisor cordial labeling of \(T \widetilde{O} C_{5}\) where \(T\) is a \(T_{p}\)-tree with 8 vertices is shown in Figure \(7\).
Theorem 8. If \(T\) be a \(T_{p}\)-tree on \(m\) vertices, then the graph \(T \widetilde{O} Q_{n}\) is sum divisor cordial graph.
Proof. Let \(T\) be a \(T_{p}\)-tree with \(m\) vertices. By the definition of a
transformed tree there exists a parallel transformation \(P\) of \(T\) such that for the path \(P(T)\), we have \((i) \ V(P(T))=V(T)\) and \((ii) \ E(P(T))=(E(T)-E_{d}) \bigcup
E_{p}\), where \(E_{d}\) is the
set of edges deleted from \(T\) and
\(E_{p}\) is the set of edges newly
added through the sequence \(P=(P_{1},P_{2},\cdots,P_{k})\) of the
epts \(P\) used to arrive at
the path \(P(T)\). Clearly, \(E_{d}\) and \(E_{p}\) have the same number of edges.
Denote the vertices of \(P(T)\)
successively as \(v_{1},v_{2},\cdots,v_{m}\) starting from
one pendant vertex of \(P(T)\) right up
to the other. Let \(u^{j}_{1},u^{j}_{2},\cdots,u^{j}_{n},u^{j}_{n+1}(1
\leq j \leq m)\) be the vertices of \(j^{th}\) copy of \(Q_{n}\). Then \(V(T \widetilde{O} Q_{n})=\{v_{j},u^{j}_{i} : 1
\leq i \leq n+1, 1 \leq j \leq m \} \bigcup \{x^{j}_{i}, y^{j}_{i} : 1
\leq i \leq n, 1 \leq j \leq m \}\) and \(E(T \widetilde{O} Q_{n})=E(T) \bigcup E(Q_{n})
\bigcup \{v_{j}u^{j}_{n+1}: 1 \leq j \leq m \}\). We note that
\(\left|V(T \widetilde{O}
Q_{n})\right|=m(3n+2)\) and \(\left|E(T
\widetilde{O} Q_{n})\right|=4mn+2m-1\). Define \(f:V(T \widetilde{O} Q_{n})\rightarrow
\{1,2,\cdots,m(3n+2)\}\) as follows:
Case 1.1] \(n\) is odd.
\(f(v_{j})=(3n+2)j, \ 1 \leq j \leq m
;\)
for \(1 \leq j \leq m\) and \(1 \leq i \leq n+1\),
\(f(u^{j}_{i})=\begin{cases}(3n+2)(j-1)+3i-1
& \text{ if } \ i \ \text{is odd} \\ (3n+2)(j-1)+3i-3 & \text{
if } \ i \ \text{is even} \ ;\end{cases}\)
for \(1 \leq j \leq m\) and \(1 \leq i \leq n\),
\(f(x^{j}_{i})=\begin{cases}(3n+2)(j-1)+3i-2
& \text{ if } \ i \ \text{is odd} \\ (3n+2)(j-1)+3i-1 & \text{
if } \ i \ \text{is even} \ ;\end{cases}\)
\(f(y^{j}_{i})=\begin{cases}(3n+2)(j-1)+3i+1
& \text{ if } \ i \ \text{is odd} \\ (3n+2)(j-1)+3i & \text{ if
} \ i \ \text{is even} \ .\end{cases}\)
Let \(v_{i}v_{j}\) be a transformed
edge in \(T\), \(1 \leq i<j \leq m\) and let \(P_{1}\) be the ept obtained by
deleting the edge \(v_{i}v_{j}\) and
adding the edge \(v_{i+t}v_{j-t}\)
where \(t\) is the distance of \(v_{i}\) from \(v_{i+t}\) and also the distance of \(v_{j}\) from \(v_{j-t}\). Let \(P\) be a parallel transformation of \(T\) that contains \(P_{1}\) as one of the constituent
epts. Since \(v_{i+t}v_{j-t}\)
is an edge in the path \(P(T)\), it
follows that \(i+t+1=j-t\) which
implies \(j=i+2t+1\). Therefore, \(i\) and \(j\) are of opposite parity.
The induced edge label of \(v_{i}v_{j}\) is given by \[\begin{aligned}
f^{*}(v_{i}v_{j}) & = f^{*}(v_{i}v_{i+2t+1})\\ & = 0.
\end{aligned}\] The induced edge label of \(v_{i+t}v_{j-t}\) is given by \[\begin{aligned}
f^{*}(v_{i+t}v_{j-t}) & = f^{*}(v_{i+t}v_{i+t+1})\\ & = 0.
\end{aligned}\] Therefore, \(f^{*}(v_{i}v_{j})=f^{*}(v_{i+t}v_{j-t})\).
The induced edge labels are as follows:
\(f^{*}(v_{j}v_{j+1})=0, \ 1 \leq j \leq
m-1;\)
for \(1 \leq j \leq m\),
\(f^{*}(u^{j}_{n+1}v_{j})=1;\)
\(f^{*}(u^{j}_{i}x^{j}_{i})=0, \ 1 \leq i \leq
n\);
\(f^{*}(u^{j}_{i}y^{j}_{i})=1, \ 1 \leq i \leq
n\);
\(f^{*}(x^{j}_{i}u^{j}_{i+1})=1, \ 1 \leq i
\leq n\);
\(f^{*}(y^{j}_{i}u^{j}_{i+1})=0, \ 1 \leq i
\leq n\).
Case 2.1] \(n\) is even.
\(f(v_{j})=(3n+2)j, \ 1 \leq j \leq m
;\)
for \(1 \leq j \leq m\),
\(f(u^{j}_{i})=(3n+2)(j-1)+3i-2, \ 1 \leq i
\leq n+1\);
\(f(x^{j}_{i})=(3n+2)(j-1)+3i-1, \ 1 \leq i
\leq n\);
\(f(y^{j}_{i})=(3n+2)(j-1)+3i, \ 1 \leq i \leq
n\).
Let \(v_{i}v_{j}\) be a transformed
edge in \(T\), \(1 \leq i<j \leq m\) and let \(P_{1}\) be the ept obtained by
deleting the edge \(v_{i}v_{j}\) and
adding the edge \(v_{i+t}v_{j-t}\)
where \(t\) is the distance of \(v_{i}\) from \(v_{i+t}\) and also the distance of \(v_{j}\) from \(v_{j-t}\). Let \(P\) be a parallel transformation of \(T\) that contains \(P_{1}\) as one of the constituent
epts. Since \(v_{i+t}v_{j-t}\)
is an edge in the path \(P(T)\), it
follows that \(i+t+1=j-t\) which
implies \(j=i+2t+1\). Therefore, \(i\) and \(j\) are of opposite parity.
The induced edge label of \(v_{i}v_{j}\) is given by \[\begin{aligned}
f^{*}(v_{i}v_{j}) & = f^{*}(v_{i}v_{i+2t+1})\\ & =
2|(f(v_{i})+f(v_{i+2t+1}))\\ & = 1.
\end{aligned}\] The induced edge label of \(v_{i+t}v_{j-t}\) is given by \[\begin{aligned}
f^{*}(v_{i+t}v_{j-t}) & = f^{*}(v_{i+t}v_{i+t+1})\\ & =
2|(f(v_{i+t})+f(v_{i+t+1}))\\ & = 1.
\end{aligned}\] Therefore, \(f^{*}(v_{i}v_{j})=f^{*}(v_{i+t}v_{j-t})\).
The induced edge labels are as follows:
\(f^{*}(v_{j}v_{j+1})=1, \ 1 \leq j \leq
m-1;\)
for \(1 \leq j \leq m\),
\(f^{*}(u^{j}_{n+1}v_{j})=0;\)
\(f^{*}(u^{j}_{i}x^{j}_{i})=0, \ 1 \leq i \leq
n\);
\(f^{*}(u^{j}_{i}y^{j}_{i})=1, \ 1 \leq i \leq
n\);
\(f^{*}(x^{j}_{i}u^{j}_{i+1})=1, \ 1 \leq i
\leq n\);
\(f^{*}(y^{j}_{i}u^{j}_{i+1})=0, \ 1 \leq i
\leq n\).
In above two cases, it can be verified that \(|e_{f}(1)-e_{f}(0)| \leq 1\). Hence \(T \widetilde{O} Q_{n}\) is sum divisor
cordial graph. ◻
Example 7. Sum divisor cordial labeling of \(T \widetilde{O} Q_{2}\) where \(T\) is a \(T_{p}\)-tree with 8 vertices is shown in Figure 8.
The authors declare no conflict of interests.