![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
The binomial tree consists of a single vertex. The binomial tree
is an ordered tree defined recursively. The binomial tree
consists of two binomial trees
that are linked together: the root of one is the leftmost child of the root of the other. The popular Graceful Tree Conjecture states that every tree is graceful. In this paper, we show that binomial trees
is graceful for every
.
1 Introduction
All the graphs considered in this paper are finite simple graphs. Terms that are not defined here can be referred from the book [Citation1]. In 1963, at the Smolenice symposium in 1963, Ringel [Citation2] conjectured that , the complete graph on
vertices, can be decomposed into
isomorphic copies of a given tree with
edges. In 1965, Kotzig [Citation3] also conjectured that the complete graph
can be cyclically decomposed into
copies of a given tree with
edges. In an attempt to settle these two conjectures, in 1967, in his classical paper [Citation4] Rosa introduced a hierarchical series of ‘valuations’ of a graph called
and used these valuations to investigate the cyclic decomposition of complete graphs. Later,
-valuation was called graceful by Golomb [Citation5], and this term is being widely used. A function
is called a graceful labeling of a graph
with
edges, if
is an injective function from
to
such that, when every edge
is assigned the edge label
, then the resulting edge labels are distinct. A graph which admits graceful labeling is called a graceful graph. In the same paper [Citation4] Rosa proved the following significant theorem.
Theorem 1
Rosa [Citation4] If a graph with
edges has a graceful labeling, then
can be cyclically decomposed into
copies of
.
This result led to the Rosa–Kotzig–Ringel Conjecture popularly called Graceful Tree Conjecture, which states that “All trees are graceful”. The graceful tree conjecture has been the focus of many papers for over four decades. So far, no proof of the truth or falsity of the conjecture has been found. In the absence of a generic proof, one approach used in investigating the Graceful Tree Conjecture is proving the gracefulness of specialized classes of trees. Aldred and Mckay [Citation6] used computer search to prove that all trees on at most 27 vertices are graceful. Michael Horton [Citation7] has verified that all trees with at most 29 vertices are graceful. Fang [Citation8] has verified that all trees with at most 35 vertices are graceful. Rosa [Citation4] has proved that all paths and caterpillars are graceful. Some special classes of lobsters were shown to be graceful by Ng [Citation9] and Wang et al. [Citation10]. Chen, Lu and Yeh [Citation11] have shown that all firecrackers are graceful. Sethuraman and Jeba Jesintha [Citation12] have shown that all banana trees are graceful. Pastel and Raynaud [Citation13] have shown that olive trees are graceful. Bermond and Sotteau [Citation14] have proved that all symmetrical trees are graceful. One of the general results proved on Graceful Tree Conjecture is the result due to Havier et al. [Citation15] that all trees of diameter five are graceful. Using Havier’s branch moving technique, Balbuena et al. [Citation16] have shown that trees having an even or quasi even degree sequence are graceful. Koh, Rogers and Tan [Citation17] gave different methods to construct a bigger graceful tree from smaller graceful trees. Burzio and Ferrarese [Citation18] extended the method of Koh et al. and consequently they have shown that the subdivision of every graceful tree is graceful. Cahit [Citation19] has exhibited canonic labeling technique for proving the gracefulness of a class of rooted trees. Sethuraman and Venkatesh [Citation20] have given a method of attaching caterpillars recursively with other caterpillars to generate graceful trees. For an exhaustive survey on Graceful Tree Conjecture, refer the excellent survey by Gallian [Citation21], for other related results refer [Citation22,23].
The binomial tree consists of a single vertex. The binomial tree
is an ordered tree defined recursively. The binomial tree
consists of two binomial trees
that are linked together: the root of one is the leftmost child of the root of the other. Note that there are
vertices in the binomial tree
. shows the binomial trees
through
.
For more details about binomial trees refer [Citation24]. In this paper, we show that all binomial trees are graceful.
2 Main result
In this section, we prove that the binomial tree is graceful, for all
. In fact, we show that the binomial trees
admits
-labeling, a stronger version of graceful labeling. A graceful labeling
of a graph
with
edges is said to be an
-valuation if there exists a
such that
or
for every edge
, where
is called the width of the
-valuation.
Theorem 2
The binomial tree , for all
is graceful.
Proof
We prove that binomial tree of order ,
, for all
admits a stronger version of the graceful labeling, the
-labeling. More precisely, we prove that the binomial tree
admits
-labeling with width
, for
. It is obvious that
, a single vertex tree admits
-labeling. We prove this result by induction on
, the order of the binomial tree
. When
, the
-labelings of
and
respectively having the width
, and
are given in .
By induction, we assume that the binomial tree admits
-labeling with
, where
. By the definition of
-labeling, the vertices of
are labeled with
. Under this
-labeling, the sequence of labels
and the sequence of labels
are respectively referred to as the first half sequence and the second half sequence of the labels of vertices of
.
Consider the binomial tree of order
,
. For the convenience, we denote
, a single vertex tree and we denote
for
, where
and
are the two copies of
and
is the new edge added between the roots of
and
(The
is referred to as the first copy of
and
is referred to as the second copy of
). As
has an
-labeling, the two copies of
,
and
also have the same
-labeling. Consider the
and
as
-labeled tree with their
-labeling. Consequently, tree
is also a labeled tree labeled from the set
such that every label is assigned exactly to two vertices of
of which one vertex is in
and the other vertex is in
. Hereafter, we refer the vertices of
, for
in
with their vertex labels that are defined by the
-labeling of
, for
.
Consider the first half sequence of vertex labels of and the second half sequence of vertex labels of
and add
to each label in both of the sequences and retain the original labels for the remaining vertices of
, for
. Thus we have the labels of the vertices of
, for
after the above relabeling as given in Table 1.
From Table 1, the labels of the vertices of , for
can be arranged as the sequence of labels from
, followed by the sequence of labels from
, followed by the sequence of labels from
and followed by the sequence of labels from
as a monotonic sequence of vertex labels
. Hence the labels of the vertices of
are distinct.
Since of
, for
is
, for any edge in
, the label of the one end vertex of the edge is in the first half sequence of vertex labels and the label of the other end vertex of the edge is in the second half sequence of vertex labels corresponding to its
-labeling.
Let be the edge label of an edge
in
with vertex labels
,
in
. If
, then
and
. Therefore, by the above relabeling procedure in
,
gets the label
and the label of
is retained. Thus, the edge
of
gets the label
in
. Similarly, if
, then the edge
of
gets the label
in
.
Let be the edge label of an edge
in
with vertex labels
in
corresponding to its
-labeling. If
, then
and
. Therefore by the above relabeling procedure,
gets the label
and the label of
is retained. Thus, the edge
of
gets the label
in
. Similarly if
, then the edge
gets the relabel
in
. Thus, after the relabeling, the
edges in
will get the edge labels as
in
. Therefore, after the relabeling, the
edges in
will get the edge labels as
in
. Also note that after the relabeling process, the label of the root of
relabeled as
and the label of the root of
is retained as
in
. Therefore the edge connecting the roots of
and
gets the edge label
in
. Hence the edges of
get the distinct edge labels
. Hence the relabeling procedure indeed gives
-labeling for
having the width
. This completes the induction.
Table 1 The First and Second half Sequences of , for
after the relabeling.
The following two significant theorems indicate that the -labeled graphs decomposes the complete graphs and complete bipartite graphs.
Theorem 3
Rosa [Citation4] If a graph with
edges has an
-valuation, then there exists a cyclic decomposition of the complete graph
into subgraphs isomorphic to
, where
is an arbitrary natural number.
Theorem 4
El-zanati and Vanden Eynden [Citation25] If has
edges and admits an
-valuation, then
can be decomposed into subgraphs isomorphic to
for all positive integers
and
.
Since the binomial tree ,
admits
-labeling, the following corollary is a direct consequence of Theorems 3 and 4.
Corollary 4.1
The complete graph and the complete bipartite graph
can be decomposed into isomorphic copies of the binomial tree
for every
, where
.
References
- WestD.B., Introduction to Graph Theorysecond ed.2001Prentice Hall of India
- G. Ringel, Problem 25, in theory of graphs and its applications, in: Proc. Symposium Smolenice, Prague, 1963, p. 162.
- KotzigA., Decompositions of a complete graph into 4k-gons Matematicky Casopis 151965 229–233(in Russian)
- RosaA., On certain valuations of the vertices of a graph Theory of Graphs (International Symposium, Rome, July 1966)1966Gordon and BreachN.Y. and Dunod Paris349–355
- GolombS.W., How to number a graphReadR.C.Graph Theory and Computing1972Academic PressNew York23–37
- AldredR.E.MckayB.D., Graceful and harmonious labelings of trees Bull. Inst. Combin. Appl. 231998 69–72
- Horton Michael, Graceful Trees Statistics and Algorithms (Master’s thesis).http://eprints.comp.utas.edu.au:81/archieve/00000019/01/.
- W. Fang, A computational approach to the graceful tree conjecture.arXiv:1003.3045v1 [cs.DM].
- NgH.K., Gracefulness of a class of lobsters Notices AMS 71986825-05-294
- WangJ.G.JinD.J.LuX.G.ZhangD., The gracefulness of a class of lobster trees Math. Comput. Modelling 201994 105–110
- Chen,W.C., H.I. Lu, Y.N. Yeh, Operations of interlaced trees and graceful trees, Southeast Asian Bull. Math. 21 337–348.
- JebaJesintha J.SethuramanG., All arbitrary fixed generalized banana trees are graceful Math. Comput. Sci. 5 1 2011 51–62
- PastelA.M.RaynaudH., Numerotation gracieuse des olivers Colloq. Grenoble1978Publications Universite de Grenoble218–223
- J.C. Bermond, D. Sotteau, Graph decompositions and G-design, in: Proc. 5th British Combin. Conf., 53–72 (second series), vol. 12, 1989, pp. 25–28.
- PavelHavierAlfonzHavier, All trees of diameter five are graceful Discrete Math. 2332001 133–150
- BalbuenaC.Garcia-VazquezP.MarcoteX.ValenzuelaJ.C., Trees having an even or quasi even degree sequence are graceful Appl. Math. Lett. 202007 370–375
- KohK.H.RogersD.G.TanT., Two theorems on graceful trees Discrete Math. 251979 141–148
- BurzioM.FerrareseG., The subdivision graph of a graceful tree is a graceful tree Discrete Math. 1811998 275–281
- I. Cahit, Graceful labelings of rooted complete trees, preprint, 2002.
- SethuramanG.VenkateshS., Decomposition of complete graphs and complete bipartite graphs into α-labeled trees Ars Combin. 932009 371–385
- GallianJ.A., A dynamic survey of graph labeling Electron. J. Combin. 192012 #DS6
- Van BusselF., Relaxed graceful labelings of trees Electron. J. Combin. 92002 #R4
- SlaterP.J., On k-graceful graphs Proc. of the 13th S.E. Conf. on CombinatoricsGraph Theory Comput.1982 53–57
- Thomas Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, second ed., MIT Press.
- El-ZanatiS.Vanden EyndenC., Decomposition of km,n into cubes J. Combin. Des. 41996 51–67