On k-graceful labeling of pendant edge extension of complete bipartite graphs
For any two positive integers m, n, we denote the graph Km,n ⊙ K₁ by G. Ma Ke-Jie proposed a conjecture [9] that pendant edge extension of a complete bipartite graph is a k-graceful graph for k > 2. In this paper we prove his conjecture for n ≤ m < n² + ⎣k/n⎦ + r.
Збережено в:
| Дата: | 2018 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2018
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/188358 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | On k-graceful labeling of pendant edge extension of complete bipartite graphs / S. Bhoumik, S. Mitra // Algebra and Discrete Mathematics. — 2018. — Vol. 25, № 2. — С. 188–199. — Бібліогр.: 14 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-188358 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1883582023-02-26T01:26:52Z On k-graceful labeling of pendant edge extension of complete bipartite graphs Bhoumik, S. Mitra, S. For any two positive integers m, n, we denote the graph Km,n ⊙ K₁ by G. Ma Ke-Jie proposed a conjecture [9] that pendant edge extension of a complete bipartite graph is a k-graceful graph for k > 2. In this paper we prove his conjecture for n ≤ m < n² + ⎣k/n⎦ + r. 2018 Article On k-graceful labeling of pendant edge extension of complete bipartite graphs / S. Bhoumik, S. Mitra // Algebra and Discrete Mathematics. — 2018. — Vol. 25, № 2. — С. 188–199. — Бібліогр.: 14 назв. — англ. 1726-3255 2010 MSC: 05C78 http://dspace.nbuv.gov.ua/handle/123456789/188358 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
For any two positive integers m, n, we denote the graph Km,n ⊙ K₁ by G. Ma Ke-Jie proposed a conjecture [9] that pendant edge extension of a complete bipartite graph is a k-graceful graph for k > 2. In this paper we prove his conjecture for n ≤ m < n² + ⎣k/n⎦ + r. |
| format |
Article |
| author |
Bhoumik, S. Mitra, S. |
| spellingShingle |
Bhoumik, S. Mitra, S. On k-graceful labeling of pendant edge extension of complete bipartite graphs Algebra and Discrete Mathematics |
| author_facet |
Bhoumik, S. Mitra, S. |
| author_sort |
Bhoumik, S. |
| title |
On k-graceful labeling of pendant edge extension of complete bipartite graphs |
| title_short |
On k-graceful labeling of pendant edge extension of complete bipartite graphs |
| title_full |
On k-graceful labeling of pendant edge extension of complete bipartite graphs |
| title_fullStr |
On k-graceful labeling of pendant edge extension of complete bipartite graphs |
| title_full_unstemmed |
On k-graceful labeling of pendant edge extension of complete bipartite graphs |
| title_sort |
on k-graceful labeling of pendant edge extension of complete bipartite graphs |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2018 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/188358 |
| citation_txt |
On k-graceful labeling of pendant edge extension of complete bipartite graphs / S. Bhoumik, S. Mitra // Algebra and Discrete Mathematics. — 2018. — Vol. 25, № 2. — С. 188–199. — Бібліогр.: 14 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT bhoumiks onkgracefullabelingofpendantedgeextensionofcompletebipartitegraphs AT mitras onkgracefullabelingofpendantedgeextensionofcompletebipartitegraphs |
| first_indexed |
2025-07-16T10:22:59Z |
| last_indexed |
2025-07-16T10:22:59Z |
| _version_ |
1837798659700293632 |
| fulltext |
“adm-n2” — 2018/7/24 — 22:32 — page 188 — #26
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 25 (2018). Number 2, pp. 188–199
c© Journal “Algebra and Discrete Mathematics”
On k-graceful labeling of pendant edge extension
of complete bipartite graphs
Soumya Bhoumik and Sarbari Mitra
Communicated by D. Simson
Abstract. For any two positive integers m,n, we denote
the graph Km,n ⊙K1 by G. Ma Ke-Jie proposed a conjecture [9]
that pendant edge extension of a complete bipartite graph is a k-
graceful graph for k > 2. In this paper we prove his conjecture for
n 6 m < n2 + ⌊ k
n
⌋+ r.
Introduction
Let G = (V (G), E(G)) be a finite simple connected graph with vertex
set V (G) and edge set E(G). In this work Km,n denotes a regular complete
bipartite graph. For all other terminology and notations we follow [2].
A function f is called a graceful labeling of a graph G with m edges
if f : V (G) → {0, 1, 2, . . . ,m} is injective and the induced function
F : E(G) → {1, 2, . . . ,m} defined as F (e = uv) = |f(u) − f(v)| is
bijective. This type of graph labeling, first introduced by Rosa in 1967
as a β-valuation [12], was used as a tool for decomposing a complete
graph into isomorphic subgraphs. Both Rosa [12] and Golomb [5] proved
that complete bipartite graphs are graceful. Also it is known that Kn is
graceful if and only if n 6 4 [4]. The k-graceful graphs, which is a natural
generalization of graceful graphs was introduced independently by Slater
[14] in 1982 and by Maheo and Thuillier [10] in 1982.
2010 MSC: 05C78.
Key words and phrases: k-graceful labeling, complete bipartite graph, corona,
1-crown.
“adm-n2” — 2018/7/24 — 22:32 — page 189 — #27
S. Bhoumik, S. Mitra 189
Definition 1. A graph G is k-graceful, if there exists a mapping f :
V (G) → {0, 1, 2, . . . |E(G)| + k − 1} such that f(x) 6= f(y) for distinct
x, y ∈ V (G) and an induced mapping is defined as f∗ : E(G) → {k, k +
1, . . . , |E|+k−1}, where f∗(uv) = |f(u)−f(v)| is a bijection for all edges
uv ∈ E(G).
If a graph is k-graceful for any integer k, then it also called arbitrarily
graceful. Obviously G is graceful when k = 1. In 2011, Li, Li, and Yan
proved that Km,n is k-graceful [8].
The corona G1⊙G2 of two graphs is the graph obtained by taking one
copy of G1, and p1 copies of G2 (where |V (G1)| = p1), and then joining
the ith vertex of G1 by an edge to every vertex in the ith copy of G2. For
positive integer m, and n, we define the graph Km,n ⊙K1 by G, and in
this paper we show that G is k-graceful. In [9], Ma ke-jie proposed the
following conjecture,
Conjecture 1. 1-crown (pendant edge extension) of complete bipartite
graph Km,n(m 6 n) is k-graceful graph for k > 2.
This conjecture has not been proved or disproved until today. Jirimutu
[7] has showed that this conjecture is true when m = 1. In [1,11,13], it has
been shown that pendant edge extension of a complete bipartite graph,
i.e. Km,n ⊙ K1 is 1-graceful. In our paper we had a different approach
to verify this conjecture. First in Theorem 1 we show that it holds for
k > mn + m + n. Later we also show that our approach works when
k < mn +m + n with some restrictions (Theorem 2). Throughout the
paper we assume that m < n2 + ⌊ k
n
⌋ + r, where r is the smallest non-
negative integer such that k + r = nq, for some q ∈ Z. Note that since
k > 1 as per assumption, q must be a positive integer. Finally in Lemma
2 we explain the reason behind the restriction of m < n2 + ⌊ k
n
⌋+ r.
1. Main results
In this paper, we freely use the notation and graph theoretic termi-
nologies introduced in [3] and [5]. Let us first specify the notations used in
this section. We consider that the bipartite graph Km,n (where m > n) is
composed of two sets (partitions) - one consisting of m vertices on the left
side and the other consisting of n vertices on the right side. In the graph
G = Km,n ⊙K1, let X = {x1t, x2t, . . . , xmt} and Y = {y1t, y2t, . . . , ynt}
define the vertices on the left and right partitions respectively. Let us
“adm-n2” — 2018/7/24 — 22:32 — page 190 — #28
190 k-graceful labeling of Km,n ⊙K1
assume that t = 0 denote the vertices on Km,n, and t = 1 denote the
vertices on the leaves extended from Km,n.
Based on the above notations we define the vertex labeling using the
following two functions.
f(xit) = n(i− 1) + teit
and
f(yjt) = mn+m+ n+ k − j − tejt,
where
eit =
k + i− 1, if 1 6 i 6 r
i+ p+ k, if p(n− 1) + r + 1 6 i
6 min{(p+ 1)(n− 1) + r,m}
i+ n+ k − 1, if (s+ 1)(n− 1) < i− r 6 m
and
ejt =
{
k + r + n(j − 1), if 1 6 j 6 min{ℓ+ 1, n}
k +m+ j − 1, if ℓ+ 2 6 j 6 n
where ℓ is the largest integer less than m−r
n−1
, s = min{ℓ, n}, and p ∈
{0, 1, . . . , s}.
Lemma 1. For the above vertex labeling f , the induced edge labeling
function f∗ is bijective.
Proof. We show that the induced function f∗ : E(G) → {k, k + 1, . . . ,
|E(G)| + k − 1} is bijective, where f∗(u ∼ v) = |f(u) − f(v)|, for all
u, v ∈ V (G). To prove the bijection we need to show that there is a
one-to-one correspondence between the two sets {f∗(xi0 ∼ yi0)∪ f∗(xi1 ∼
xi0) ∪ f∗(yi1 ∼ yi0)} and {k, k + 1, . . . , k +mn+m+ n− 1} (note that
|E(G)| = mn+m+ n). Now, from the definition of the function f , it is
easy to observe that
f∗(xi0 ∼ yi0) = {k +m+ n, k +m+ n+ 1, . . . , k +mn+m+ n− 1}.
Therefore, it remains to show that there is also a one-to-one correspondence
between the two sets {f∗(xi1 ∼ xi0)∪ f∗(yi1 ∼ yi0)} and {k, k+1, . . . , k+
m+n− 1}. To proceed further, depending on the values of m we consider
the following three cases and in each case we show that f∗(xi1 ∼ xi0) ∪
f∗(yi1 ∼ yi0) = {k, k + 1, . . . , k +m+ n− 1}.
“adm-n2” — 2018/7/24 — 22:32 — page 191 — #29
S. Bhoumik, S. Mitra 191
Case 1: m 6 (n− 1)2 + r (for any r).
Note that since ℓ < m−r
n−1
6 n − 1 which implies ℓ 6 n − 2, hence
s = min{ℓ, n− 1} = ℓ.
f∗(xi1 ∼ xi0) =
k + i− 1, if 1 6 i 6 r
i+ p+ k, if p(n− 1) + r + 1 6 i
6 min{(p+ 1)(n− 1) + r,m}
f∗(yj1 ∼ yj0) =
{
k + r + n(j − 1), if 1 6 j 6 s+ 1
k +m+ j − 1, if s+ 2 6 j 6 n
It is easy to observe that f∗(yj1 ∼ yj0) = {k + r, k + r + n, k + r +
2n, . . . , k + r + sn, k +m+ s+ 1, k +m+ s+ 2, . . . , k +m+ n− 1}. On
the other hand f∗(xi1 ∼ xi0) = {k, k + 1, . . . , k + r − 1}
⋃
(
⋃s
p=0
Ap
)
,
where
A0 = {k + r + 1, k + r + 2, . . . , k + r + n− 1}
A1 = {k + r + n+ 1, k + r + n+ 2, . . . , k + r + 2n− 1}
...
As = {k + r + ns+ 1, k + r + ns+ 2, . . . ,m+ k + s}.
Hence we obtain that f∗(xi1 ∼ xi0)∪ f∗(yi1 ∼ yi0) = {k, k+1, . . . , k+
m+n−1}. Also, the uniqueness of all the elements, of the form f∗(u ∼ v),
is evident from the pattern of the sets mentioned above. This is enough to
ensure the bijection. Therefore, it follows that f∗ maps the set of pendant
extension edges uniquely to the set {k, k + 1, . . . , k +m+ n− 1}, when
m 6 (n− 1)2 + r.
Case 2: (n− 1)2 < m− r 6 n2 − n.
Observe that ℓ < m−r
n−1
6
n2
−n
n−1
= n. On the other hand, the facts that
ℓ is the greatest integer less than (m− r)/(n− 1) and m− r > (n− 1)2,
together imply that ℓ must be greater than n−1. Hence s = min{ℓ, n−1} =
n− 1, and consequently min{(s+ 1)(n− 1) + r,m} = m.
f∗(yj1 ∼ yj0) = k + r + n(j − 1), if 1 6 j 6 n
f∗(xi1 ∼ xi0) =
k + i− 1, if 1 6 i 6 r
i+ p+ k, if s(n− 1) + r + 1 6 i
6 min{(s+ 1)(n− 1) + r,m}
“adm-n2” — 2018/7/24 — 22:32 — page 192 — #30
192 k-graceful labeling of Km,n ⊙K1
It is easy to observe that f∗(yj1 ∼ yj0) = {k + r, k + r + n, k + r +
2n, . . . , k + r + n2 − n}. On the other hand
f∗(xi1 ∼ xi0) = {k, k + 1, . . . , k + r − 1}
⋃
( s
⋃
p=0
Bp
)
,
where
B0 = {k + r + 1, k + r + 2, . . . , k + r + n− 1}
B1 = {k + r + n+ 1, k + r + n+ 2, . . . , k + r + 2n− 1}
...
Bs−1 = {k + r + ns− n+ 1, k + r + ns− n+ 2, . . . , k + r + ns− 1}
Bs = {k + r + ns+ 1, k + r + ns+ 2, . . . ,m+ k + s}.
In this case also we observe that f∗(xi1 ∼ xi0)∪f∗(yi1 ∼ yi0) = {k, k+
1, . . . , k+m+s}, where s = n−1. Also, the uniqueness of all the elements
f∗(u ∼ v) is evident from the pattern of the sets mentioned above. Similar
arguments as Case 1 indicate the bijection of f∗ in this case. Therefore, it
follows that f∗ maps the set of pendant extension edges uniquely to the
set {k, k + 1, . . . , k +m+ n− 1}, when (n− 1)2 < m− r 6 n2 − n.
Case 3: n2 − n < m− r < n2 + ⌊ k
n
⌋.
As n2−n < m−r, it is clear that in this case s = min{ℓ, n−1} = n−1.
Also min{(s+1)(n− 1)+ r,m} = min{n2−n+ r,m} = (s+1)(n− 1)+ r.
f∗(yj1 ∼ yj0) = k + r + n(n− j), if 1 6 j 6 n
f∗(xi1 ∼ xi0) =
k + i− 1, if 1 6 i 6 r
i+ p+ k, if p(n− 1) + r + 1 6 i
6 min{(p+ 1)(n− 1) + r,m}
i+ k + n− 1, if (s+ 1)(n− 1) + r + 1
6 i 6 m
where p ∈ {0, 1, 2, . . . , n− 1}. It is easy to observe that f∗(yj1 ∼ yj0) =
{k + r + n2 − n, k + r + n2 − 2n, . . . , k + r}. On the other hand
f∗(xi1 ∼ xi0) = {k, k + 1, . . . , k + r − 1}
⋃
( s
⋃
p=0
Cp
)
⋃
{k + r + n2, k + r + n2 + 1, . . . ,m+ k + n− 1},
“adm-n2” — 2018/7/24 — 22:32 — page 193 — #31
S. Bhoumik, S. Mitra 193
where
C0 = {k + r + 1, k + r + 2, . . . , k + r + n− 1},
C1 = {k + r + n+ 1, k + r + n+ 2, . . . , k + r + 2n− 1},
...
Cn−1 = {k + r + n2 − n+ 1, k + r + n2 − n+ 2, . . . , k + r + n2 − 1}.
Proceeding similarly as the previous two cases we obtain that
f∗(xi1 ∼ xi0) ∪ f∗(yi1 ∼ yi0) = {k, k + 1, . . . , k +m+ n− 1}.
Therefore, similar arguments as the previous two cases leads us to the fact
that that f∗ maps the set of pendant extension edges uniquely to the set
{k, k + 1, . . . , k +m+ n− 1}, when n2 − n < m− r < n2 + ⌊ k
n
⌋.
This completes the proof.
Lemma 1 proves that all the edge labels obtained by f∗ are distinct.
Now, to prove the k-gracefulness of the graph, it remains to show that the
the vertex labels defined by f are distinct as well. In the following section,
we either prove the uniqueness of the vertex labels and when there are
repetitions in the vertex labels under certain condition, we rearrange the
assignments to ensure there is no repetition and also the uniqueness of
the edge labels remains unaltered.
2. Vertex labeling
2.1. k > mn + m + n
In the following theorem, we see when the function f labels the graph
k-gracefully, i.e., the vertex labels are unique. (In other words, there is no
repetition in the vertex labels).
Theorem 1. Km,n ⊙K1 is k-graceful for any positive integer m,n when
m 6 n2 + n, and k > mn+m+ n.
Proof. We have already shown that the induced function f∗ is bijective.
It is easy to observe that the vertex labeling function f is well-defined.
Hence to prove that Km,n ⊙K1 is k-graceful, we just need to show that
f is injective, when k > mn +m + n. Our approach is to show that f
is distributing vertex labels in four mutually exclusive subsets. In other
words, all of the vertex labels are distinct. Note that
f(xi0) = n(i− 1)
“adm-n2” — 2018/7/24 — 22:32 — page 194 — #32
194 k-graceful labeling of Km,n ⊙K1
where i ∈ {1, 2, . . . ,m}, therefore
⋃m
i=1
f(xi0) = {0, n, . . . ,mn− n}. Next
f(yj0) = mn+m+ n+ k − j
where j ∈ {1, 2, . . . , n}, i.e.
n
⋃
j=1
f(yj0) = {mn+m+n+ k− 1,mn+m+n+ k− 2, . . . ,mn+m+ k}.
Now we need to consider two cases based on the value r.
Case 1: r = 0. This occurs when k is a multiple of n
f(xi1) =
n(i− 1) if p(n− 1) + r + 1 6 i
+ i+ p+ k, 6 min{(p+ 1)(n− 1) + r,m}
n(i− 1) if (s+ 1)(n− 1) < i− r 6 m
+ i+ n+ k − 1,
Hence
⋃m
i=1
f(xi1) = {k + 1, k + 2, . . . ,mn+m+ k − 1}. Next
f(yj1) =
mn+m+ 2n− j(n+ 1), if 1 6 j 6 ℓ+ 1;
m 6 n2 − n
mn+ n− 2j + 1, if ℓ+ 2 6 j 6 n;
m 6 n2 − n
mn+m+ 2n− j(n+ 1), if m > n2 − n
Hence if m 6 n2 − n, then
n
⋃
j=1
f(yj1) = {mn− n+ 1,mn− n+ 3, . . . ,mn+m+ n− 1}.
If n2 − n < m 6 n2 + n, then
n
⋃
j=1
f(yj1) = {mn+m+ n− 1,mn+m− 2, . . . ,mn+m− n2}.
Case 2: r 6= 0.
f(xi1) =
n(i− 1) + k + i− 1, if 1 6 i 6 r
n(i− 1) if p(n− 1) + r + 1 6 i
+ i+ p+ k, 6 min{(p+ 1)(n− 1) + r,m}
n(i− 1) if (s+ 1)(n− 1) < i− r 6 m
+ i+ n+ k − 1,
“adm-n2” — 2018/7/24 — 22:32 — page 195 — #33
S. Bhoumik, S. Mitra 195
Hence
⋃m
i=1
f(xi1) = {k, k + 1, . . . ,mn+m+ k − 1}. Next
f(yj1) =
mn+m+ 2n− j(n+ 1)− r, if 1 6 j 6 ℓ+ 1;
m 6 n2 − n
mn+ n− 2j + 1, if ℓ+ 2 6 j 6 n;
m 6 n2 − n
mn+m+ 2n− j(n+ 1)− r, if m > n2 − n
Hence if m 6 n2 − n, then
n
⋃
j=1
f(yj1) = {mn− n+ 1,mn− n+ 3, . . . ,mn+m+ n− r − 1}.
If n2 − n < m 6 n2 + n, then
n
⋃
j=1
f(yj1) = {mn+m+n− r− 1,mn+m− r− 2, . . . ,mn+m− r−n2}.
For the sake of the proof we define the four sets as follows:
A = {f(xi0) ∈ Z : i = 1, 2, . . . ,m}
B = {f(xi1) ∈ Z : i = 1, 2, . . . ,m}
C = {f(xj0) ∈ Z : i = 1, 2, . . . , n}
D = {f(xj1) ∈ Z : i = 1, 2, . . . , n}
From the pattern of the vertex labels obtained above, we see that all
the elements in set X (for each X ∈ A,B,C,D) can be arranged in an
increasing/decreasing order and this can also be observed that all the
elements of the set X (for each X ∈ A,B,C,D) is distinct. Further, we
assume that maxX and minX denote the maximum and minimum element
respectively, contained in set X (for each X ∈ A,B,C,D).
From the above discussion it can be easily verified (for the both the
cases) that
min
A
= 0, max
A
= mn− n,
min
B
= k + 1, max
B
= mn+m+ k − 1,
min
C
= k +mn+m, max
C
= mn+m+ n+ k − 1,
min
D
= mn− n− r + 1, max
D
= mn+m+ n− 1.
“adm-n2” — 2018/7/24 — 22:32 — page 196 — #34
196 k-graceful labeling of Km,n ⊙K1
Since k > mn+m+ n, it can be easily noticed that
min
A
< max
A
< min
D
< max
D
< min
B
< max
B
< min
C
< max
C
This implies A < B < C < D, i.e. we have
A ∩ B ∩ C ∩ D
=
(
m
⋃
i=1
f(xi0)
)
⋂
(
m
⋃
i=1
f(xi1)
)
⋂
(
n
⋃
j=1
f(jj0)
)
⋂
(
n
⋃
j=1
f(yj0)
)
= ∅.
This completes the proof.
Theorem 1 proves the uniqueness of the vertex labels when k >
mn +m + n. Therefore, Lemma 1 and Theorem 1 together prove that
G = Km,n ⊙ K1 is k-graceful when k > mn + m + n. In the following
subsection we shall observe the case when k < mn+m+ n.
2.2. k < mn + m + n
In this section we consider the case k < mn+m+ n. We assume that
k + r = nq, where q is any positive integer. In this section we first define
few sets of integers.
• A1 = {z ∈ Z|z = (m + 1 − j)/n + m + 2 − i − j, where 1 6 i 6
r, 1 6 j 6 min{ℓ+ 1, n}}
• A2 = {z ∈ Z|z = (m−j−p)/n+m+2−i−j, where p(n−1)+r+1 6
i 6 min{(p+ 1)(n− 1) + r,m},
1 6 j 6 min{ℓ+ 1, n}}
• A3 = {z ∈ Z|z = (m+1−j)/n+m+1−i−j, where (s+1)(n−1) <
i− r 6 m, 1 6 j 6 n}
• A4 = {z ∈ Z|z = n(m+ 1 − i) − 2j + 2, where 1 6 i 6 r, ℓ + 2 6
j 6 n}
• A5 = {z ∈ Z|z = n(m+1− i)−2j−p+1, where p(n−1)+ r+1 6
i 6 min{(p+ 1)(n− 1) + r,m}, ℓ+ 2 6 j 6 n}
Now we have the following theorem which describes that the graph
G = Km,n ⊙K1 is k-graceful, if k is not in this following sets of integers.
Theorem 2. Let G = Km,n ⊙ K1, then G is k-graceful if each of the
followings statements are true.
1) If m 6 n2 − n+ r, then q is not in A1, A2, and/or k is not in A4,
and A5.
2) If n2 − n < m− r 6 n2 + ⌊ k
n
⌋, then q is not in A1, A2, and/or A3.
“adm-n2” — 2018/7/24 — 22:32 — page 197 — #35
S. Bhoumik, S. Mitra 197
Proof. First assume that m 6 n2 − n. Then if Li = Rj for some i, j, then
we have this following cases to consider, depending on the values of i
and j.
Case 1: If 1 6 i 6 r, and 1 6 j 6 min{ℓ+ 1, n}, then we have (i− 1)n+
k + i− 1 = mn+m+ n+ k − j − (k + r + n(j − 1)), which simplifies to
n(k + r + i+ j −m− 2) = m+ 1− j. As we know k + r = nq, we easily
arrive at q = (m+ 1− j)/n+m+ 2− i− j ∈ A1.
Case 2: If p(n − 1) + r + 1 6 i 6 min{(p + 1)(n − 1) + r,m}, and
1 6 j 6 min{ℓ+1, n}, then we have (i−1)n+k+i+p = mn+m+n+k−j−
(k+r+n(j−1)), which simplifies to n(k+r+i+j−m−2) = m−p−j. As we
know k+r = nq, we easily arrive at q = (m−j−p)/n+m+2− i−j ∈ A2.
Case 3: If 1 6 i 6 r, and ℓ + 1 6 j 6 n, then we have (i − 1)n +
k + i − 1 = mn + m + n + k − j − (k + m + j − 1), which implies to
k = n(m+ 1− i)− 2j + 2 ∈ A4.
Case 4: If p(n−1)+r+1 6 i 6 min{(p+1)(n−1)+r,m}, and ℓ+1 6 j 6 n,
then we have (i− 1)n+ k+ i+ p = mn+m+n+ k− j − (k+m+ j − 1),
which implies to k = n(m+ 1− i)− 2j − p+ 1 ∈ A5.
Next we consider n2 − n 6 m 6 n2 + n. In this case it is easy to
observe that min{ℓ + 1, n} = n. Then if Li = Rj for some i, j, then we
again have some more cases to consider, depending on the values of i,
and j. When 1 6 i 6 r, or p(n − 1) + r + 1 6 i 6 min{(p + 1)(n −
1) + r,m}, then similar to Case(1), and Case(2), we can easily observe
that q is not in A1, A2. The remaining case that we need to consider
is (s + 1)(n − 1) < i − r 6 m and 1 6 j 6 n. In this case we have
(i− 1)n+ k+ i+ n− 1 = mn+m+ n+ k− j − (k+ r+ n(j − 1)), which
simplifies to n(k+ r+ i+ j−m− 1) = m+1− j. As we know k+ r = nq,
we easily arrive at q = (m+1− j)/n+m+1− i− j ∈ A3. This completes
the proof.
Throughout the paper we have followed the restriction on m that m 6
n2+ ⌊ k
n
⌋+ r+1. In the following lemma we explain the reason behind this
restriction. Actually, we observe that
(
⋃m
i=1
f(xi0)
)
⋂
(
⋃m
i=1
f(xi1) 6= ∅
when m > n2 + ⌊ k
n
⌋+ r + 1. As a consequence of that we get a repetition
in the vertex labels and hence f fails to remain injective anymore.
Lemma 2. f is not injective when m > n2 + ⌊ k
n
⌋+ r + 1.
Proof. In this theorem we consider the case when m > n2 + ⌊ k
n
⌋+ r + 1.
There is no restriction on any other variable in this proof. For our conve-
nience, throughout this proof we express f(xic) as f(xi,c) (where c = 0, 1).
“adm-n2” — 2018/7/24 — 22:32 — page 198 — #36
198 k-graceful labeling of Km,n ⊙K1
If possible we assume that f is injective i.e., f(xi1,j1) 6= f(xi2,j2) for any
i1, i2 ∈ {1, 2, . . . ,m} and j1, j2 ∈ {0, 1}.
First, note that k = nq − r, which implies ⌊k/n⌋ = q − 1.
Now, in this proof we must have m > n2 + ⌊ k
n
⌋+ r + 1. So, we start
with the assumption m > n2 + ⌊ k
n
⌋+ r + 2 = n2 + q + r + 1.
Without loss of any generality, we consider a particular case where
m = n2+q+r+1. Then we have from the definition, f(xm,0) = n(m−1) =
n(n2 + q + r).
On the other hand, since m = n2 + q + r + 1 > (n − 1)2, then
s = min{ℓ, n− 1} = n− 1 in this case. So, for i = n(n− 1)+ r+1, we get
f(xi,1) = {n(n−1)+r+1−1}+n(n−1)+r+1+n+k−1 = n(n2+q+r).
Therefore, we get a contradiction f(xi1,j1) = f(xi2,j2) = n(n2+q+r) when
i1 = m, j1 = 0 and i2 = n(n− 1) + r + 1, j2 = 1. Hence, this completes
the proof.
Conclusion
In this paper we have shown that Km,n ⊙ K1 is k-graceful for any
integer n > 2 and m < n2 + ⌊ k
n
⌋+ r. As our future work we would like to
investigate whether is possible to label Km,n ⊙K1 k-gracefully, for any
m, and k.
References
[1] Bhoumik, S., Mitra S., Graceful Labeling of Pendant Edge Extension of Complete
Bipartite Graph, International Journal of Mathematical Analysis, 8(58) pp. 2885–
2897, 2014.
[2] Bondy, J. A. and Murty, U. S. R., Graph theory, Springer, 244, New York, 2008.
[3] Cvetković, D. M., Rowlinson, P., and Simić S. K., An Introduction to the Theory
of Graph Spectra, Cambridge-New York, 2010
[4] Gallian, J. A., A Dynamic Survey of Graph Labeling, The Electronics Journal of
Combinatorics 16(3), 2013.
[5] Golomb, S. W., How to number a graph, Graph theory and computing, pp. 23–37,
1972
[6] Graham, R. L, Sloane, N. J., On additive bases and harmonious graphs, SIAM
Journal on Algebraic Discrete Methods, 1(4), pp. 382–404, 1980.
[7] Jirimuta, Y.L., On k-gracefulness of r-Crown Ir(K1,n)(n > 2, r > 2) for Complete
Bipartite Graph, Journal of Inner Mongolia University for Nationalities, 2, pp.
108-110, 2003.
[8] Li, W., Li, G., and Yan, Q., Advances in Computer Science, Environment, Ecoin-
formatics, and Education, Communications in Computer and Information Science,
214, pp. 297–301, 2011.
“adm-n2” — 2018/7/24 — 22:32 — page 199 — #37
S. Bhoumik, S. Mitra 199
[9] Ma, Ke-Jie, Graceful Graphs, Beijing University Publishing House, Beijing, 1991.
[10] Maheo, M., Thuillier, H., On d-graceful graphs. Ars Combin., 13, pp. 181–192,
1982.
[11] Mitra, S., Bhoumik S., On Graceful Labeling Of 1-crown For Complete Bipartite
Graph, International Journal of Computational and Applied Mathematics, 10(1)
pp. 69–75, 2015
[12] Rosa, A., On certain valuations of the vertices of a graph, Theory of Graphs
(International Symposium Rome), pp. 349–355, 1966
[13] Sethuraman G. and Elumalai A., On graceful graphs: pendant edge extensions
of a family of complete bipartite and complete tripartite graphs, Indian J. Pure
Appl. Math, 32(9), pp. 1283–1296, 2001.
[14] Slater, P. J., On k-graceful graphs. In Proc. of the 13th SE Conf. on Combinatorics,
Graph Theory and Computing, pp. 53–57, 1982.
Contact information
Soumya Bhoumik,
Sarbari Mitra
Fort Hays State University, 600 Park St, Hays,
KS, USA
E-Mail(s): s_bhoumik@fhsu.edu,
s_mitra@fhsu.edu
Received by the editors: 19.05.2016.
|