![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
Let be a graph of order
. A numbering
of
is a labeling that assigns distinct elements of the set
to the vertices of
, where each edge
of
is labeled
. The strength str
of a numbering
of
is defined by
that is,
is the maximum edge label of
, and the strength str
of a graph
itself is
The strengths
and
are determined for caterpillars
and
-level complete
-ary trees
. The strength
is also given for graphs
obtained by taking the corona of certain graphs and an arbitrary number of isolated vertices. The work of this paper suggests an open problem on the strength of trees.
1 Introduction
In this paper, we will consider only finite graphs without loops or multiple edges. We refer the reader to the book by Chartrand and Lesniak Citation[1] for graph-theoretical notation and terminology not described in this paper. The graph with vertices and no edges is referred to as the empty graph of order
and is denoted by
. The
a vertex
in a graph is number of edges of
incident with
and is denoted by
. A vertex of degree
is called an isolated vertex and a vertex of degree
is an end-vertex of
. The minimum degree of
is the minimum degree among the vertices of
and is denoted by
.
For the sake of notational convenience, we will denote the interval of integers such that
by simply writing
.
For a graph of order
and size
, a bijective function
is called an edge-magic labeling if
is a constant
(called the magic constant) for each
. If such a labeling exists, then
is called an edge-magic graph.
The notion of edge-magic labelings was first introduced in 1970 by Kotzig and Rosa Citation[2]. These labelings were originally called “magic valuations” by them. These were rediscovered in 1996 by Ringel and Lladó Citation[3] who coined one of the now popular terms for them: edge-magic labelings. Afterwards, Enomoto et al. Citation[4] defined a slightly restricted version of an edge-magic labeling of a graph
by requiring that
. Such a labeling was called by them super edge-magic . Thus, a super edge-magic graph is a graph that admits a super edge-magic labeling. It is worth to mention that Acharya and Hegde Citation[5] had already discovered such graphs in 1991 under the name of “strongly indexable graphs”. However, they arrived at this concept from a different point view. Their motivation is much clear from the following alternative definition found in Citation[6].
Lemma 1
A graph of order
and size
is super edge-magic if and only if there exists a bijective function
such that the set
consists of
consecutive integers. In such a case,
extends to a super edge-magic labeling of
with magic constant
, where
and
The concept of super magic strength was introduced by Avadayappan et al. Citation[7]. The super magic strength of a graph
is defined as the minimum of all magic constants
, where the minimum is taken over all super edge-magic labelings
of
, that is,
It is an immediate consequence of the definition that if
is not a super edge-magic graph or an empty graph, then
is undefined (or we could define
). It is also true that
is a super edge-magic graph if and only if
.
As the concept of super magic strength is effectively defined only for super edge-magic graphs, this concept was generalized in Citation[8] for any nonempty graph as follows. A numbering of a graph
of order
is a labeling that assigns distinct elements of the set
to the vertices of
, where each edge
of
is labeled
. The strength str
of a numbering
of
is defined by
that is,
is the maximum edge label of
, and the strength str
of a graph
itself is
A numbering
of a graph
for which
is called a strength labeling of
. If
is an empty graph, then
is undefined (or we could define
).
There are several sharp bounds for the strength of a graph in terms of well-known invariants in graph theory (see Citation[8]). Among others, the following result that provides a lower bound for in terms of the order and the minimum degree is particularly useful.
Lemma 2
For every graph of order
with
,
The following results were obtained in Citation[8] for the paths and stars
of order
. These classes of graphs illustrate the sharpness of the bound given in Lemma 2.
Theorem 1
For every integer ,
Theorem 2
For every integer ,
We close this section with suggestions for further reading. A survey article on graph labelings and related topics can be found in Gallian Citation[9], and a book by Bača and Miller [Citation10] is another useful resource. Readers interested in more information on super edge-magic graphs should consult the books by López and Muntaner-Batle [Citation11] as well as Marr and Wallis [Citation12], which also include information on other kinds of graph labelings.
2 The strength of Caterpillars
In this section, we investigate the strength of caterpillars, beginning with double stars. The double star is a tree obtained by joining the centers of two disjoint stars
and
with an edge.
Theorem 3
For every two positive integers and
,
Proof
The inequality is a direct consequence of Lemma 2. In order to verify the inequality in the other direction, it suffices to find a numbering
of
with
. Assume, without loss of generality, that
, and define the double star
with
and
Now, consider the labeling
such that
,
,
Notice that
assigns distinct elements of the set
to the vertices of
. Also, notice that
Thus,
has the property that
Consequently,
. □
A caterpillar is a tree with the property that the removal of the end-vertices of
results in a path. This path is referred to as the spine of the caterpillar. If the spine is trivial, the caterpillar is a star; if the spine is
, then the caterpillar is a double star. The next result includes caterpillars whose spine is both trivial and
. Realize that the way of defining the spine provided in the proof is intended to make the vertex labeling easy to describe.
Theorem 4
For every caterpillar of order
,
Proof
In light of Theorems 2 and 3, it suffices to prove the theorem for caterpillars whose spine contains at least vertices and both end-vertices of the spine have end-vertices attached. The lower bound for
is obtained immediately from Lemma 2.
To establish the upper bound for , let
be the caterpillar with
and
Then
has the spine
with
and
Note that if we define a permutation
of
by
where
with
, then
is an involutive automorphism of
, and we have
. Hence, every edge of
joins vertices
and
with
and
whenever
or
In the case that
with
, we may assume that
is located to the left of
in the drawing of
in the plane.
The preceding construction allows us to define the caterpillar with
and
If we let
, then
. Notice that if
for some
, then we treat
as the empty set. Thus, assume that
for some
; otherwise,
and the result follows from Theorem 1. It remains to show the existence of a numbering
of
for which
. To complete this, there are two cases to proceed according to the possible values for the integer
.
Case 1: Assume that , and consider the labeling
such that
Then
assigns distinct elements of the set
to the vertices of
. In particular,
assigns distinct elements of the set
to the vertices of
. This implies that
However,
where
. At this point, let
be the integer so that
with
. Then
, which implies that
. Thus,
Consequently,
so
has the property that
.
Case 2: Assume that , and let
. Then
for
and
for
. With this knowledge in hand, consider the labeling
such that
Then
assigns distinct elements of the set
to the vertices of
. Thereby,
assigns distinct elements of the set
to the vertices of
as follows:
For the rest of the proof, we will examine the induced edge labels given by for each
. Then, in a similar manner to Case 1, we have
where
. However, there are three subcases to pursue according to the possibility for the edge
.
Subcase 2.1: Let . Then
However, since
has
end-vertices and
vertices of
have end-vertices, it follows that
, that is,
(1)
(1) This implies that
(2)
(2) Since
, it also follows from (2) that
(3)
(3) Thus, the fact that
together with (3) implies that
Subcase 2.2: Let . Then
Thus, it follows from (1) that
Subcase 2.3: Let . Then
for each
. Thus, it follows from (1) that
Consequently,
so
has the property that
. □
3 The strength of complete ![](//:0)
-ary trees
The -level complete
-ary tree
is a tree in which the
th level consists of
vertices and each vertex in level
has
‘sons’ at level
. If
, then
is referred to as a
-level complete binary tree. The strength of
depends on
as the next result indicates. The proof involves the concept of distance in a graph. For a connected graph
and pair
,
, the distance
between
and
is the length of a shortest
path in
.
Theorem 5
For every integer ,
Proof
The lower bound for follows immediately from Lemma 2, since
and
.
To establish the upper bound for , it suffices to show the existence of a numbering
of
for which
. Let
be given as a rooted tree in the plane. Then
has a unique vertex of degree
, so chose this distinct vertex to be the root of
and denoted it by
. Of course, if
is drawn in the plane, then by letting
the vertices in each level
can be ordered from left to right using the integers
. Since the
th level consists of
vertices, it follows that
. Thus,
can be written as
where
represents the level that the vertex occupies in
and
represents the place that the vertex in level
occupies in the level starting to count from left to right. If we let
then
and the edges of
can also be ordered from left to right in ascending order starting with
and ending up with
for each set
. Thus, we will write
for the edge in the set
that occupies position
when counting the edges of
from left to right. This implies that if
with
, then
is located to the left of
in the drawing of
in the plane.
Since , it follows from Theorem 1 that
. It also follows from Theorem 4 that
, since
is a caterpillar. Let
be an integer with
, and consider the labeling
such that
This implies that
Since
, it follows that
assigns distinct elements of the set
to the vertices of
.
For each , where
and
, we write
for the induced edge label given by
. Notice then that for each
with
, we have
if
with
, whereas we have
if
. Thus,
has the property that
and
implying that
Consequently,
. □
The strength of is also determined by considering a drawing of
as a rooted tree in the plane; the proof is quite similar to that of Theorem 5 and will not be included.
Theorem 6
For every two integers and
,
4 The strength of the corona of graphs
The corona of two graphs was introduced by Frucht and Harary [Citation13]. The corona of two graphs
and
is defined as the graph obtained by taking one copy of
(which has order
) and
copies of
, and then joining the
th vertex of
to every vertex in the
th copy of
. It is now possible to present the following result.
Theorem 7
Let be a graph of order
with
. If
, then
for every positive integer
.
Proof
Suppose that is a graph of order
with
, and let
be a strength labeling of
with
. Assume that
has the property that
for each
, where
. Further, let
, and define the graph
with
and
Then
and
. Thus, the lower bound for
follows from Lemma 2.
To establish the upper bound for , consider the labeling
such that
Then
and
This implies that
assigns distinct elements of the set
to the vertices of
. It is now immediate that
for every positive integer
. Moreover,
has the property that
Consequently,
. □
The preceding result is of particular interest, since there are infinitely many graphs for which
(see Citation[8] for a detailed list of graphs). Applying it with such classes of graphs repeatedly, we obtain other classes of graphs
for which
again.
5 Conclusions
In this paper, we have shown that every caterpillar and -level complete
-ary tree attains the bound provided in Lemma 2. We have also established a formula for the strength of the corona of certain graphs and an arbitrary number of isolated vertices (see Theorem 7). A new tree can be created by taking the corona with isolated vertices. Therefore, applying Theorem 7 with the classes of trees studied in this paper, we obtain other classes of trees
for which
. These trees include a class of lobsters (a lobster is a tree
with the property that the removal of the end-vertices of
results in a caterpillar). This motivates us to propose the following problem.
Problem 1
For every lobster , determine the exact value of
.
References
- ChartrandG.LesniakL., Graphs & digraphs Wadsworth & Brook/Cole Advanced Books and Software1986MontereyCalif.
- KotzigA.RosaA., Magic valuations of finite graphs Canad. Math. Bull. 131970 451–461
- RingelG.LladóA., Another tree conjecture Bull. Inst. Combin. Appl. 181996 83–85
- EnomotoH.LladóA.NakamigawaT.RingelG., Super edge-magic graphs SUT J. Math. 341998 105–109
- AcharyaB.D.HegdeS.M., Strongly indexable graphs Discrete Math. 931991 123–129
- Figueroa-CentenoR.M.IchishimaR.Muntaner-BatleF.A., The place of super edge-magic labelings among other classes of labelings Discrete Math. 2312001 153–168
- AvadayappanS.JeyanthiP.VasukiR., Super magic strength of a graph Indian J. Pure Appl. Math. 322001 1621–1630
- IchishimaR.Muntaner-BatleF.A.OshimaA., Bounds for the strength of graphs Australas. J. Combin. 72 3 2018 492–508
- GallianJ.A., A dynamic survey of graph labeling Electron. J. Combin.2018 #DS6
- BačaM.MillerM., Super Edge-Antimagic Graphs: A Wealth of Problems and Some Solutions2007Brown Walker PressBoca Raton, FL, USA
- LópezS.C.Muntaner-BatleF.A., Graceful Harmonious and Magic Type Labelings: Relations and Techniques2016SpringerNew York
- MarrA.M.WallisW.D., Magic Graphssecond ed.2013Birkhäuser/SpringerNew York
- FruchtR.HararyF., On the corona of two graphs Aequationes Math. 41970 322–325