Square difference labeling of some union and disjoint union graphs
The paper deals with methods of constructing square difference labeling of caterpillars and graphs derived from two operations: path union of cycles and disjoint union of stars. The existence of the square difference labeling of disjoint union of any SD graph with path is proved.
Gespeichert in:
| Datum: | 2018 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2018
|
| Schriftenreihe: | Algebra and Discrete Mathematics |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/188364 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Square difference labeling of some union and disjoint union graphs / Z. Sherman // Algebra and Discrete Mathematics. — 2018. — Vol. 25, № 2. — С. 294–302. — Бібліогр.: 8 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-188364 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1883642023-02-26T01:26:56Z Square difference labeling of some union and disjoint union graphs Sherman, Z. The paper deals with methods of constructing square difference labeling of caterpillars and graphs derived from two operations: path union of cycles and disjoint union of stars. The existence of the square difference labeling of disjoint union of any SD graph with path is proved. 2018 Article Square difference labeling of some union and disjoint union graphs / Z. Sherman // Algebra and Discrete Mathematics. — 2018. — Vol. 25, № 2. — С. 294–302. — Бібліогр.: 8 назв. — англ. 1726-3255 2010 MSC: 05C78. http://dspace.nbuv.gov.ua/handle/123456789/188364 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
The paper deals with methods of constructing square difference labeling of caterpillars and graphs derived from two operations: path union of cycles and disjoint union of stars. The existence of the square difference labeling of disjoint union of any SD graph with path is proved. |
| format |
Article |
| author |
Sherman, Z. |
| spellingShingle |
Sherman, Z. Square difference labeling of some union and disjoint union graphs Algebra and Discrete Mathematics |
| author_facet |
Sherman, Z. |
| author_sort |
Sherman, Z. |
| title |
Square difference labeling of some union and disjoint union graphs |
| title_short |
Square difference labeling of some union and disjoint union graphs |
| title_full |
Square difference labeling of some union and disjoint union graphs |
| title_fullStr |
Square difference labeling of some union and disjoint union graphs |
| title_full_unstemmed |
Square difference labeling of some union and disjoint union graphs |
| title_sort |
square difference labeling of some union and disjoint union graphs |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2018 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/188364 |
| citation_txt |
Square difference labeling of some union and disjoint union graphs / Z. Sherman // Algebra and Discrete Mathematics. — 2018. — Vol. 25, № 2. — С. 294–302. — Бібліогр.: 8 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT shermanz squaredifferencelabelingofsomeunionanddisjointuniongraphs |
| first_indexed |
2025-07-16T10:23:29Z |
| last_indexed |
2025-07-16T10:23:29Z |
| _version_ |
1837798690431959040 |
| fulltext |
“adm-n2” — 2018/7/24 — 22:32 — page 294 — #132
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 25 (2018). Number 2, pp. 294–302
c© Journal “Algebra and Discrete Mathematics”
Square difference labeling of some union and
disjoint union graphs
Zoya Sherman
Communicated by D. Simson
Abstract. The paper deals with methods of constructing
square difference labeling of caterpillars and graphs derived from
two operations: path union of cycles and disjoint union of stars. The
existence of the square difference labeling of disjoint union of any
SD graph with path is proved.
Introduction
Research studies conducted by Ajitha et. al. in the field of number
theory inspired them to create two new types of labelings: square sum
labeling and square difference labeling. For the first time, square difference
labeling was introduced to scientific world in 2012 [1]. Its authors proved
the existence of this labeling for such classes of graphs as paths, stars,
cycles, complete graphs, bipartite graphs, friendship graphs, triangular
snakes. Tharmaraj and Sarasija identified new classes of graphs that have
square difference labeling, such as: fan Fn, graph gn, middle graphs of path
and cycle, total graphs of path and cycle [2,3]. In addition, they proved that
the disjoint union of path with such graphs as star, path, cycle, and other
constructions of graphs have the square difference labeling. Shiama [4]
focused on the particular case of the caterpillar and demonstrated the
existence of the square difference labeling for the graph Pn ⊙K1. These
2010 MSC: 05C78.
Key words and phrases: square difference labeling, the square difference graph,
caterpillar, disjoint union of graphs.
“adm-n2” — 2018/7/24 — 22:32 — page 295 — #133
Z. Sherman 295
labelings, as well as majority of others, are well presented in the review
published by Gallian [5].
In this paper, we prove the existence of the square difference labeling
for new types of graphs, which were obtained using disjoint union of stars
and path union of cycles. In addition, we show that the caterpillar, and
the disjoint union of any SD graph and path are square difference graphs.
1. Definitions
We consider finite undirected graphs without loops and multiple edges.
Let G=(V,E) be a graph with vertex set V =V (G) and edge set E=E(G).
We assume that |V (G)| = p, |E(G)| = q.
Definition 1 ([1]). A graph G = (V (G), E(G)) with |V (G)| = p is
said to be a square difference graph if there exist a bijection
f : V (G) → {0, 1, 2, . . . , p− 1} such that the induced an injection function
f∗ : E(G) → N given by f∗(uv) = |[f(u)]2−[f(v)]2| for every edge uv∈G
and the function f is called square difference labeling of the graph G.
Graph, allowing square difference labeling, is called square difference
graph or SD graph.
For n copies of the graph G=(V,E), we introduce the definition of the
path union.
Definition 2 ([6]). Let the graphs G1, G2, . . . , Gn(n > 2) are n copies of
certain graph G. Then the graph obtained via connection of Gi vertex
with the corresponding Gi+1 vertex, for i = 1, 2, . . . , n− 1, with edge is
called the path graphs union G1, G2, . . . , Gn.
Definition 3 ([6]). Disjoint union of graphs G1 = (V1, E1), G2 = (V2, E2),
. . . , Gm = (Vm, Em) is a graph G = G1 ∪G2 ∪ · · · ∪Gm with vertex set
V = V1 ∪ V2 ∪ · · · ∪ Vm and edge set E = E1 ∪ E2 ∪ · · · ∪ Em, where
V1 ∩ V2 ∩ · · · ∩ Vm = ⊘.
Definition 4 ([7]). Caterpillar is a tree that after removing its end-
vertices (vertices with degree 1), turns into a path. The path is called a
tree trunk and end-vertices are leaves of the tree, which grow out of the
trunk vertices.
Theorem 1 ([8]). The square difference of consecutive numbers equals
the sum of these numbers.
Theorem 2 ([8]). If n = x2 − y2, then n ≡ 0, 1, 3 (mod 4).
“adm-n2” — 2018/7/24 — 22:32 — page 296 — #134
296 Square difference labeling of some union
Let f be square difference labeling for graph G, generating edge label-
ing f∗, then for each edge uv of the set E(G), the following condition is true:
f∗(u, v) ≡ 0, 1, 3 (mod 4). Furthermore, if f(u) = 0, then f∗(u, v) ≡ 0, 1
(mod 4).
2. Square difference labeling of caterpillars
Theorem 3. Any caterpillar is a square difference graph.
Proof. Let G be the caterpillar with |V (G)| = kn. We define V (P ) =
{v1, v2, . . . , vk} as a set of vertices of the trunk of the graph G and
{ui,1, ui,2, . . . , ui,ni
} as a set of leaves, for i = 1, 2, . . . , k.
Let us analyze the case when i = 1. We obtain a caterpillar, which is
the star K1,n1
. We define the vertex labeling f of star K1,n1
as follows:
f(v1) = 0,
f(u1,j) = j, for j = 1, 2, . . . , n1.
Function f defines bijection from the set of vertices into set {0, 1, . . . , n1}
and induces a different edge labels, according to Definition 1. Edge labels
form a set {1, 4, 9, . . . , n2
1}. So labeling f is a square difference label-
ing K1,n1
.
Further, assume that i = l and l > 1. For the vertices of the trunk
v1, v2, . . . , vl we assign labels 0, 1, 2, . . . , l − 1; and u1,1, . . . , u1,n1
, u2,1,
. . . , u2,n2
, ui,1, . . . , ui,ni
form a set {l, l + 1, . . . , l + n1 − 1, l + n1, . . . ,
l +m− 1}, for m being the number of leaves.
Trunk edge labels and end-edge labels will form two sets of numbers
{1, 3, 5, . . . , 2l − 3}, and {l2, (l + 1)2, . . . , (l +m − 1)2 − (l − 1)2}. As a
result, we assign labels to the vertices, using all the positive integers from
0 to kn− 1.
Edge labeling f∗, generated by labeling f , presents an injection of
E(G) onto a certain subset of positive integers. According to Definition 1,
labeling f of the graph G is a square difference labeling.
3. Square difference labeling of path and cycle union
Theorem 4. An arbitrary path union of n copies of the cycle C3 is a
square difference graph for any positive integer n.
Proof. Let graph G be formed by the path union of n copies of the cycle
C3 as shown in Figure 1.
“adm-n2” — 2018/7/24 — 22:32 — page 297 — #135
Z. Sherman 297
Figure 1. A square difference labeling the path union 3C3.
Let u10, u
2
0,. . . ,u
n
0 be isomorphic images of vertex u of cycle C3 selected
randomly. V (G)={ui0, w
i
1, w
i
2} — a set of vertices of graph G, for i =
1, 2, . . . , n. We define the vertex labeling f of graph G with graph order
|V (G)| = 3n as follows:
f(ui0) = i− 1,
f(wi
1) = n+ 2i− 2,
f(wi
2) = n+ 2i− 1,
for i = 1, 2, . . . , n. Therefore, function f is bijection of vertex set of graph G
onto set of numbers {0, 1, 2, . . . , 3n− 1}. Then edge labeling f∗ generated
by the function f , as defined by the Definition 1, is:
f∗(ui0, u
i+1
0
) = |[f(ui0)]
2 − [f(ui+1
0
)]2|, (1)
for i = 1, 2, . . . , n− 1;
f∗(wi
1, w
i
2) = |[f(wi
1)]
2 − [f(wi
2)]
2|, (2)
f∗(wi
1, u
i
0) = |[f(wi
1)]
2 − [f(ui0)]
2|, (3)
f∗(wi
2, u
i
0) = |[f(wi
2)]
2 − [f(ui0)]
2|, (4)
for i = 1, 2, . . . , n.
We apply Theorem 5 to formulas (1) and (2), and obtain
f∗(ui0, u
i+1
0
) = f(ui0) + f(ui+1
0
), (5)
f∗(wi
1, w
i
2) = f(wi
1) + f(wi
2). (6)
Edge labels calculated by formulas (5) and (6) form sets of numbers
S1 = {1, 3, 5, . . . , 2n − 3}, S2 = {2n + 1, 2n + 5, 2n + 9, . . . , 6n − 3}.
Meanwhile, edge labels obtained by formulas (3) and (4) form set S3 =
{n2, (n+ 1)2, . . . , (2n− 1)(4n− 3), 2n(4n− 3)}.
“adm-n2” — 2018/7/24 — 22:32 — page 298 — #136
298 Square difference labeling of some union
Let us consider minimum number of n2 in set S3, and compare it with
the maximum number of 6n−3 from set S1∪S2. If n > 6, then n2 > 6n−3
and elements of set S = S1 ∪ S2 ∪ S3 ⊂ N are different, where N is the
set of positive integers. They form a set S = S1 ∪ S2 ∪ S3 ⊂ N . Thus,
for n > 6 function f∗ is an injection of E(G) into the S set. Labeling f ,
according to Definition 1, is a square difference labeling, while graph G is
a SD graph.
For n = 1, 2, 3, 4, 5 square difference labeling of an arbitrary path
union of n copies of the cycle C3 is shown in Figure 2, 3.
Figure 2. Square difference labeling the path union nC3, for n = 1, 2.
Figure 3. Square difference labeling the path union nC3, for n = 3, 4, 5.
4. Square difference labeling of the disjoint union of
graphs
Theorem 5. The disjoint union of graphs G1, G2, . . . , Gm of the family
of graphs Gi = Ki
1,ni
, for i = 1, 2, . . . ,m is a square difference graph for
any positive integers m and ni.
Proof. The graph G is obtained by disjoint union of stars K1,ni
, for i =
1, 2, . . . ,m. Let V (K1,ni
) = {ui0, u
i
1, u
i
2, . . . , u
i
ni
} be the set of vertices of
“adm-n2” — 2018/7/24 — 22:32 — page 299 — #137
Z. Sherman 299
the graph G, for ni can be any value starting from 1. We assume that ui0
is a central vertex of star K1,ni
. We define the vertex labeling f of the
graph G with graph order |V (G)| = (n1+n2+ · · ·+nm)+m as following:
f(ui0) = i− 1, (7)
f(uij) =
{
m− 1 + j if i = 1,
Σi−1
l=1
nl +m− 1 + j otherwise,
(8)
for i = 1, 2, . . . ,m, j = 1, 2, . . . , ni. Function f defines bijection from the
set of vertices into a set of numbers {0, 1, 2, . . . , (n1 + n2 + · · · + nm) +
m− 1}. At the same time it induces the following edge labels for the first
stars K1,n1
:
f∗(u11, u
1
0) = |[f(u11)]
2 − [f(u10)]
2| = |m2 − 0| = m2,
f∗(u12, u
1
0) = |[f(u12)]
2 − [f(u10)]
2| = |(m+ 1)2 − 0| = (m+ 1)2,
f∗(u13, u
1
0) = |[f(u13)]
2 − [f(u10)]
2| = |(m+ 2)2 − 0| = (m+ 2)2,
· · ·
f∗(u1n1
, u10) = |[f(u1n1
)]2 − [f(u10)]
2| = |(m+n1−1)2−0| = (m+n1−1)2.
The calculated edge labels form a set of different numbers S1 = {m2,
(m+ 1)2, . . . , (m+ n1 − 1)2}. Also, the function f generates edge labels
for the second star K1,n2
:
f∗(u21, u
2
0) = |[f(u21)]
2 − [f(u20)]
2| = |(m+ n1)
2 − 1|
= |1 + 2(m+ n1 − 1) + (m+ n1 − 1)2 − 1|
= 2(m+ n1 − 1) + (m+ n1 − 1)2,
f∗(u22, u
2
0) = |[f(u22)]
2 − [f(u20)]
2| = |(m+ n1 + 1)2 − 1|
= |1 + 2(m+ n1) + (m+ n1)
2 − 1|
= 2(m+ n1) + (m+ n1)
2,
. . .
f∗(u2n2
, u20) = |[f(u2n2
)]2 − [f(u20)]
2| = |(m+ n1 + n2 − 1)2 − 1|
= |1 + 2(m+ n1 + n2 − 2) + (m+ n1 + n2 − 2)2 − 1|
= 2(m+ n1 + n2 − 2) + (m+ n1 + n2 − 2)2.
Thus, we get a set of numbers S2 = {2(m + n1 − 1) + (m+ n1 − 1)2,
2(m+ n1) + (m+ n1)
2, . . . , 2(m+ n1 + n2 − 2) + (m+ n1 + n2 − 2)2}.
Similar actions are performed for all the stars in the disjoint union.
Thus, the edge labels for the latest star K1,nm
, induced by function f , form
“adm-n2” — 2018/7/24 — 22:32 — page 300 — #138
300 Square difference labeling of some union
a set of numbers Sm = {2(n1 + n2 + · · ·+ nm−1 + 1)(m− 1) + (n1 + n2 +
· · ·+nm−1+1)2, . . . , 2(n1+n2+ · · ·+nm)(m−1)+(n1+n2+ · · ·+nm)2}.
Consequently, set S = S1 ∪ S2 ∪ · · · ∪ Sm ⊂ N , consisting of different
numbers is formed. Therefore, function f∗, is the injection of E(G) into
the set of positive integers. Labeling f for the graph G, according to
Definition 1, is square difference labeling.
In the case of graph mK1,n, formulas (7) and (8) can be written as
following:
f(ui0) = i− 1, (9)
f(uij) = n(i− 1) +m− 1 + j, (10)
for i = 1, 2, . . . ,m, j = 1, 2, . . . , n.
Example 1. We apply these formulas (9) and (10) to the graph 3K1,4,
and get square difference labeling of the graph 3K1,4 as shown in Figure 4.
Figure 4. Square difference labeling the graph 3K1,4.
In the following theorem, we summarize some results obtained in the
articles [2,3] concerning the square difference labeling of the disjoint union
of paths or cycles, or other types of SD graphs with path.
Theorem 6. The disjoint union of any SD graph G with path Pk, is the
square difference graph for any k.
Proof. Let us consider the disjoint union of G and path Pk. Let V (G) =
{w1, w2, . . . , wl} be the set of vertices of graph G. We denote V (Pk) =
{v1, v2, . . . , vk} the set of vertices of path Pk. Let f be a square difference
labeling of G. We define the vertex labeling f1 of graph G∪Pk, as follows:
f1(vi) = i− 1 for i = 1, 2, . . . , k,
f1(wj) = f(wj) + k for j = 1, 2, . . . , l.
“adm-n2” — 2018/7/24 — 22:32 — page 301 — #139
Z. Sherman 301
Function f1 defines bijection from V (G ∪ Pk) onto the set {0, 1, 2, . . . ,
k + l − 1}. Edge labels of path image Pk in G∪Pk, induced by labeling f1,
form a set of numbers {1, 3, 5, . . . , 2k − 3}.
Let wn, wm be any adjacent vertices of G with labels f(wn) = n,
f(wm) = m, for m,n ∈ {0, 1, . . . , l − 1}, n 6= m and f∗ be edge labeling
of G, induced by labeling f . Also, we assume n > m. Then
f∗(wn, wm) = |[f(wn)]
2 − [f(wm)]2 = |n2 −m2| = n2 −m2.
Let us consider edge labeling f∗
1 of the graph G ∪ Pk, induced by
labeling f1 and find an edge label wnwm:
f∗
1 (wn, wm) = |[f∗
1 (wn)]
2 − [f∗
1 (wm)]2
= |(n+ k)2 − (m+ k)2|
= |n2 + 2nk + k −m2 − 2mk − k2|
= n2 −m2 + 2k(n−m)
= f∗(wn, wm) + 2k(n−m).
(11)
Since 2k(n−m) > 2k−3 for ∀m,n ∈ {0, 1, . . . , l−1}, then f∗
1 (wn, wm) >
2k− 3. Consequently, the edge labeling of graph G∪Pk is different. So f∗
1
is an injection. According to Definition 1, f1 is square difference labeling
of graph G.
Additionally, using analytical description of labeling obtained in The-
orems 4 and 5, we developed algorithms for square difference labeling of
certain graph examples for path union of cycles and disjoint union of stars.
Results verify our theoretical findings.
5. Conclusion
In this paper the class of square difference graphs is expanded. The
existence of the square difference labeling of the disjoin union of any SD
graph with path is proved. The methods developed for constructing a
square difference labeling for caterpillars and graphs derived from two
operations: a path union of cycles and disjoint union of stars, may be used
in further theoretical studies.
References
[1] V. Ajitha, K. L. Princy, V. Lokesha and P. S. Ranjini. On square difference Graphs.
International Journal of Mathematical Combinatorics, 1(1):31–40, 2012.
“adm-n2” — 2018/7/24 — 22:32 — page 302 — #140
302 Square difference labeling of some union
[2] T. Tharmaraj, P. B. Sarasija. Square difference Labeling for Certain Graphs.
International Journal of Mathematical Archive, 4(8):183–186, 2013.
[3] T. Tharmaraj, P. B. Sarasija. Square difference Labeling of Some Union Graphs.
International Journal of Mathematics Trends and Technology, 11(11):81–88, 2014.
[4] J. Shiama. Square difference labeling for some path, fan and gear graphs. Interna-
tional Journal of Scientific and Engineering Research, 4:1–9, 2013.
[5] J. A. Gallian. A dynamic survey of graph labeling. The Electronic Journal of
Combinatorics, 18:#DS6, 2011.
[6] F. Harary. Graph Theory. Addison Wesley, Reading, Massachusetts, 1969.
[7] G. A. Donets, D. A. Petrenko. Building T-factorizations of the complete graph
and the problem Rosa. International Journal of Control systems and machines,
4:21–24, 2010.
[8] S. G. Telang. Number Theory. (Sixth edition), TATA McGRAW-HILL, 1996.
Contact information
Z. Sherman V. M. Glushkov Institute of Cybernetics
National Academy of Sciences of Ukraine,
Kyiv, Ukraine
E-Mail(s): sherman.zoya@gmail.com
Received by the editors: 02.09.2016
and in final form 06.11.2016.
|