Abstract
Let be a simple, finite and undirected graph of order
and size
. A bijection
such that
for every edge
is said to be a
-super graceful labeling of
. We say
is
-super graceful if it admits a
-super graceful labeling. For
, the function
is called a super graceful labeling and a graph is super graceful if it admits a super graceful labeling. In this paper, we study the super gracefulness of complete graph, the disjoint union of certain star graphs, the complete tripartite graphs
, and certain families of trees. We also present four methods of constructing new super graceful graphs. In particular, all trees of order at most 7 are super graceful. We conjecture that all trees are super graceful.
1 Introduction
Let be a simple, finite and undirected graph of order
and size
. All notations not defined in this paper can be found in [Citation1]. An injective function
is called a graceful labeling of
if all the edge labels of
given by
for every
are distinct. This concept was first introduced by Rosa in 1967 [Citation2]. Since then, there have been more than 1500 research papers published on graph labelings (see the dynamic survey by Gallian [Citation3]).
In [Citation4], the authors defined a -sequentially additive labeling
of a graph
as a bijection from
to
such that for each edge
,
. A graph
admitting a
-sequentially additive labeling is called a
-sequentially additive graph. If
, then
is called a simply sequentially additive graph or an SSA-graph. They conjectured that all trees are SSA-graphs. More results on
-sequentially additive labeling can be found in [Citation5,Citation6].
Definition 1.1
A bijection is called a
-super graceful labeling if
for every edge
in
. For
, the function
is called a super graceful labeling. We say
is super graceful if it admits a super graceful labeling.
This is a generalization of super graceful labeling defined in [Citation7,Citation8]. Among others, the authors proved that paths, cycles, complete bipartite graphs and several families of trees are super graceful. In this paper, we continue with the search for super graceful graphs. We study the super gracefulness of complete graph, the disjoint union of certain star graphs, the complete tripartite graphs , and certain families of trees. We also present four methods of constructing new super graceful graphs. In particular, all trees of order at most 7 are super graceful. We conjecture that all trees are super graceful. Note that we only give the vertex labels of all the given examples.
2 New super graceful graphs
In [Citation4], the authors showed that the complete graph is an SSA-graph if and only if
.
Theorem 2.1
The complete graph is super graceful if and only if
.
Proof
It is easy to verify that the sufficiency holds. To prove the necessity, we show that is not super graceful for
. Assume that
admits a super graceful labeling. Let
, which is the largest label. Thus,
cannot be a difference of other labels,
must be a vertex label.
Case (1). 1 is a vertex label. This means is an edge label and 2 is not a vertex label. Hence
cannot be a difference of two vertex labels. So 1 and
are vertex labels. Then the difference
is an edge label. Note that
. Since
, 2 and
are edge labels,
cannot be an edge label. Thus,
is a vertex label. This yields a contradiction since
,
and
are vertex labels creating 2 as an edge label twice.
Case (2). 1 is an edge label. The only way to have as an edge label would be an edge joining the vertices labeled 1 and
, which is impossible in this case. Thus
is a vertex label. Hence the edge labeled by 1 is incident with the vertices labeled by
and
. It follows that
cannot be a vertex label. Thus
is an edge label. The edge labeled by
must be incident with the vertices labeled by
and 2. Since
and 2 are vertex labels, an edge which is incident with vertices labeled by
and 2 is labeled by
. By means of this fact and together with
and 2 that served as vertex labels, 3 and 4 must be edge labels, respectively. 1, 3, 4,
and
are edge labels implies that
and
cannot be edge labels.
Finally, the edge joining the vertices labeled and
, and the edge joining the vertices labeled
and
both have label 1, a contradiction. ■
Theorem 2.2
The complete tripartite graph is super graceful for
.
Proof
Let and
. Now,
and
. Define a labeling
as follows:
,
for
; and
,
for
.
It is easy to verify that is a bijection with
for every edge
. Hence,
is super graceful. ■
Example 2.1
In , we give the super graceful labeling of according to the function defined above.
Problem 2.1
Study the super gracefulness of complete tripartite graph .
Definition 2.1
Let be the disjoint union of
copies of star graphs
for
and
.
Theorem 2.3
The graph is super graceful if
(a) |
|
(b) | for |
Proof
Let with
and
. Clearly,
and
. Define a labeling
as follows:
(a) Begin with the central vertex of each star subgraph .
(1) | Label the vertices |
(2) | For |
(3) | For |
(b) Begin with .
(1) | Label vertex |
(2) | For |
Thus, in both (a) and (b) above, is a bijection with
for every edge
in
. Hence,
is super graceful. ■
Example 2.2
In and , we give the super graceful labeling of (a) and (b)
according to the function defined in (a) and (b) above, respectively.
3 Construction of super graceful graphs
In this section, we give four methods of constructing new super graceful graphs.
Construction C1. Let be a graph with a super graceful labeling
having vertices
that satisfy the following conditions:
(a) |
|
(b) |
|
Example 3.1
Refer to the graph in Example 4.1. We let
be the edge with label 8 such that
and
have labels 23 and 15 respectively. Let
be the vertex with label 7. We can now delete edge
and add a new edge
with label 8. The obtained new graph is super graceful.
Construction C2. Let be a graph of order
and size
with a super graceful labeling
. Let
be a vertex of
with
.
(a) | Attached |
(b) | For |
Example 3.2
We refer to the super graceful labeling of in and add 4 pendant edges to the vertex with label 4. Label the newly added vertices by 23, 24, 25, 26 respectively and the corresponding pendant edges will have labels 19, 20, 21, 22. The new graph obtained is super graceful.
Construction C3. Let be a graph with a super graceful labeling
.
(a) | Let |
(b) | Suppose there exists a vertex |
(c) | Delete edges |
(d) | Label |
Example 3.3
Refer to the caterpillar in Example 4.1. We let
be the vertices with labels
respectively. Delete the edges
and
with labels
respectively. Add 2 new edges
and
. Label
and
with
. We have a new super graceful caterpillar.
Construction C4. Begin with vertices .
(a) | Label |
(b) | For |
(c) | Label edge |
(d) | Delete edge |
(e) | For |
(f) | Delete each new edge in (e) if its label is one of the new vertex labels. |
Note: We can choose not to perform Steps (e) and (f). If we do perform Steps (e) and (f), the common new vertex labels and new edge labels introduced in part (e) are those of the new vertices except the last one. Thus edges with these labels are to be deleted.
Example 3.4
In , we give an example for . In Step (a), vertices
to
are labeled
respectively. In Steps (b) and (c), we add vertices
to
that are labeled 18 to 21 consecutively. In Step (d), we delete the edge joining vertices
to
. We then perform Steps (e) and (f) by taking
. Thus, we add 5 more vertices that are labeled 38 to 42 consecutively.
Since this construction method will give us infinitely many connected super graceful bipartite graphs, we then have
Problem 3.1
Study the super gracefulness of connected bipartite graphs.
4 Super graceful trees
We now investigate the super gracefulness of some families of trees.
A caterpillar graph is a tree in which all the vertices are within distance 1 of a central path for
. A caterpillar graph of order greater than 1 is a star graph when
, which is
for some
. When
, a caterpillar graph is obtained from a path
by attaching
pendant vertices
(
) to each
. We shall denote this caterpillar graph by
. In [Citation7,Citation8], the authors showed that
,
and
for
are super graceful. We now show that
is super graceful for
,
and
, i.e., all caterpillar graphs are super graceful.
Theorem 4.1
The graph is super graceful for
.
Proof
Define a labeling as follows:
for
, and
for
and
.
For odd :
,
,
,
for
,
for
,
.
For even :
for
,
, for
,
for
,
.
It can be verified that is a bijection with
for every edge
. Hence,
is super graceful. ■
Example 4.1
In , we give the super graceful labeling of according to the function defined above.
Note that if or 2, we get that both the star graph and double star graph are super graceful.
Definition 4.1
Given paths of length
with an end vertex
. A spider graph
is the one-point union of the
paths at vertex
.
In [Citation7], the authors showed that ,
is super graceful. We now show that many other families of spider graphs are also super graceful. For simplicity, we shall use
to denote a sequence of length
in which all items are
, where
.
Theorem 4.2
The following spider graphs are super graceful.
(a) |
|
(b) |
|
(c) |
|
(d) |
|
(e) |
|
Proof
(a) Let and
. Note that
. Define a labeling
as follows:
Case (1) is odd.
,
for
,
for odd
and even
,
for odd
,
for even
and odd
,
for even
.
Case (2) is even.
,
for
,
for odd
and even
,
for odd
,
for even
and odd
,
for even
.
It can be verified that is a bijection with all the vertex labels being odd and the edge labels being even such that for each edge
,
. Hence,
is super graceful.
In , we give the super graceful labeling of ,
,
,
as defined above.
(b) Let and
. Note that
. Define a labeling
as follows:
,
for odd
, and
for even
,
for odd
, and
for even
.
It can be verified that is a bijection with all the vertex labels being odd and the edge labels being even such that for each edge
,
.
In , we give the super graceful labeling of and
as defined above.
(c) Let and
. Note
is a super graceful path. For
, we note that
. Define a labeling
as follows:
Case (1). is odd. We have
,
for even
,
for odd
,
for even
,
for odd
,
for even
,
for odd
.
Case (2). is even. We have
,
for even
,
for odd
,
for even
,
for odd
,
for even
,
for odd
.
It can be verified that is a bijection with all the vertex labels being odd and the edge labels being even such that for each edge
,
.
In , we give the super graceful labeling of and
as defined above.
(d) We have . It is easy to verify that the labeling of the graph
as shown in is super graceful.
(e) We provide the proof for . In a similar way, it is easy to verify that the result holds for
. We let
and
. Note that
. Define a labeling
as follows:
Case (1). is odd. We have
,
for odd
, and
for even
.
Case (2). is even. We have
,
for odd
, and
for even
.
We now let and
. Note that
. Define a labeling
as follows:
Case (1). is odd. We have
,
for odd
, and
for even
.
Case (2). is even. We have
,
for odd
, and
for even
.
It can be verified that is a bijection with all the vertex labels being odd and the edge labels being even such that for each edge
,
. ■
Problem 4.1
Let be any real number.
(1) Given the sequence ,
, we can always arrange the
numbers as a sequence so that the difference of the
pairs of consecutive numbers is even from 2 to
.
(2) Given the sequence ,
, we can always arrange the
numbers as a sequence so that the difference of the
pairs of consecutive numbers is even from 2 to
.
Note that the spider in Case (e) is also known as lobsters. Observe that we always label the end-vertex, , of the longest path with 1. If we identify the central vertex of a star
, to
, then the new graph is also super graceful by labeling the
end-vertices of
with
for
. Hence, we have obtained new families of super graceful lobsters.
Consider another lobster tree, , having a longest path
and two
subpaths
and
. For
, we obtained that the tree is super graceful. The labelings of the vertices in the order of
are given below:
.
The case is shown in .
Problem 4.2
Show that the lobster tree is super graceful for all
.
Moreover, we may consider case (a) of Theorem 4.2 for . That means we may ignore all the vertices
’s. By using the same labeling and combining with Theorem 2.3 for the case
, we get the result of Perumal et al. [Citation7].
Corollary 4.3
The spider graphs are super graceful, where
and
.
Note that the Construction C2 can be used repeatedly to any super graceful tree to create infinitely many super graceful trees. Hence, we end this paper with the following conjecture.
Conjecture 4.1
All trees are super graceful.
Notes
Peer review under responsibility of Kalasalingam University.
References
- J.A.BondyU.S.R.MurtyGraph Theory with Applications1976MacMillanNew York
- A.RosaOn certain valuations of the vertices of a graphTheory of Graphs International Symposium, Rome1966
- J.A.GallianA dynamic survey of graph labelingElectron. J. Combin.192014#DS6
- D.W.BangeA.E.BarkauskasP.J.SlaterSequentially additive graphsDiscrete Math.441983235241
- S.M.HegdeM.MillerFurther results on sequentially additive graphsDiscuss. Math. Graph Theory272007251268
- K.ManimekalaiJ.Baskar BabujeeK.ThirusanguSimply sequentially additive labeling of some special treesAppl. Math. Sci.6131201265016514
- M.A.PerumalS.NavaneethakrishnanS.ArockiarajA.NagarajanSuper graceful labeling for some special graphsInt. J. Res. Rev. Appl. Sci.932011382404
- M.A.PerumalS.NavaneethakrishnanS.ArockiarajA.NagarajanSuper graceful labeling for some simple graphsInt. J. Math. Soft Comput.2120123549