Open Journal of Discrete Mathematics
Vol.04 No.04(2014), Article ID:50292,11 pages
10.4236/ojdm.2014.44013
Balance in Random Trees
Azer Akhmedov, Warren Shreve
Department of Mathematics, North Dakota State University, Fargo, ND, USA
Email: azer.akhmedov@ndsu.edu, warren.shreve@ndsu.edu
Copyright © 2014 by authors and Scientific Research Publishing Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY).
http://creativecommons.org/licenses/by/4.0/
Received 30 July 2014; revised 25 August 2014; accepted 20 September 2014
ABSTRACT
We prove that a random labeled (unlabeled) tree is balanced. We also prove that random labeled and unlabeled trees are strongly -balanced for any
. Definition: Color the vertices of graph
with two colors. Color an edge with the color of its endpoints if they are colored with the same color. Edges with different colored endpoints are left uncolored.
is said to be balanced if neither the number of vertices nor and the number of edges of the two different colors differs by more than one.
Keywords:
Random Trees, Balance, Equicolorable Graphs
1. Introduction
The notion of a balanced graph is defined [1] as follows:
Definition 1.1 Let be a finite simple graph,
be an integer,
be a map.
For all, we write
. We also write
. The map
is called a coloring.
The case of is especially interesting. In this case, the sets
are called the sets of black vertices, white vertices, black edges, and white edges respectively. If the coloring
is fixed we may drop it in the notation.
Definition 1.2 A finite simple graph is called balanced if there exists a coloring
such that and
. A map
satisfying this condition is called a balanced coloring.
The graph in Figure 1 is balanced since we have shown a balanced coloring of it.
It is not difficult to see that:
Figure 1. With the given coloring, the graph has 4 black and 3 white vertices; it also has 2 white edges (labeled with a “W”) and 1 black edge (labeled with a “B”).
1) The complete graph is balanced if and only if
or
is even.
2) The star is balanced if and only if
; see Figure 2 for a balanced coloring of
.
3) The double star is balanced if and only if
. (The double star
is a connected graph where some two adjacent vertices have degree
and
, and all other vertices have degree 1).
In [2] , the author introduces a somewhat similar notion of a cordial graph, a generalization of both graceful and harmonious graphs. It has been conjectured by A. Rosa, G. Ringel and A. Kotzig that every tree is graceful (Graceful Tree Conjecture, [3] ), and it has been conjectured by R. Graham and N. Sloane that every tree is harmonious (see [4] ). While these conjectures are still open, in [5] it is proved that every tree is cordial.
Not every tree is balanced; in this paper, we will be interested in the property of being balanced for a random labeled and unlabeled tree, as well as for random labeled graphs.
The main results of the paper are Theorem A and Theorem B, stated below.
Theorem A A random labeled (unlabeled) tree is balanced; more precisely, if denotes the number of all labeled (unlabeled) trees on
vertices, and
denotes the number of all balanced labeled (unla-
beled) trees on vertices, then
and
.
Remark 1.3 In this paper, for simplicity, we consider only uniform models of random graphs and random trees. The results can be extended to a large class of non-uniform models as well. Note that (see [6] or [7] ) and
for some positive constants
and
(see [8] ).
We also would like to introduce the notion of -balanced graphs.
Definition 1.4 Let. A finite simple graph
is called
-balanced if there exists a coloring
such that
and
for all distinct
. The map
will be called a
-balanced coloring.
Definition 1.5 Let. A finite simple graph
is called strongly
-balanced if there exists a coloring
such that
, and
for all distinct
. The map
will be called a strongly
-balanced coloring.
In more popular terms, a finite simple graph is strongly -balanced if and only if it is
-equitably colorable. In Section 5 we study some basic properties of
-balanced graphs. We prove the following theorem.
Theorem B. For all, a random (labeled) tree is strongly
-balanced.
Remark 1.6 Let us emphasize that Theorem B is originally due to B. Bollobás and R. Guy (see [9] ). Our proof in this paper is very different with some ingredients which might be interesting independently.
Remark 1.7 It has been proved by I. Ben-Eliezer and M. Krivelevich (see [10] ) that a random graph is balanced. For, it seems quite plausible that a random graph is indeed
-balanced. However, notice that the clique number of a random graph on
vertices is at least
(see [11] ) thus a random graph is not strongly
-balanced.
Figure 2. A balanced coloring of.
Acknowledgement: We would like to thank to B. Gittenberger for the discussion and for bringing the reference [12] to our attention; to I. Pak for his comments; to M. Krivelevich for bringing [9] to our attention. We also would like to extend our gratitude to the anonymous referee for many helpful remarks, and for pointing out a flaw in the proof of Lemma 5.3.
Notes:
1) For any finite simple graph, we will denote the maximum degree of
by
.
2) A vertex of degree one will be called a leaf vertex or simply a leaf. A non-leaf vertex is called a pre- leaf vertex if it is adjacent exactly to
leaves where
. A pre-leaf vertex of degree two is called special.
3) For, there exists a unique tree up to isomorphism with
vertices and maximum degree at most two; we will call this tree a path on
vertices, and denote it with
.
4) For a finite simple graph and for a subset
, the induced subgraph
will be called the full subgraph of
on
.
5) For a tree and a non-leaf vertex
, a subset
will be called a branch of
with respect to
if
is a maximal subset such that the full subgraph
is connected and
where
denotes the distance in the tree
.
2. Characterization of Balanced Graphs
In this section we observe some basic facts on balanced and -balanced graphs. Let us first prove a very simple lemma which provides a necessary and sufficient condition for a graph to be balanced.
Lemma 2.1 Let be a finite simple graph with
vertices, and degrees
.
is balanced if and only if there exists a partition
such that
1)
2)
Proof. Let.
Assume is balanced with a balanced coloring
.
Let.
Since is a balanced coloring, we get
so condition 1) is satisfied.
For every, we denote
and for every, we denote
Then. On the other hand, since
is balanced, we have
.
Then. Thus condition 2) is also satisfied.
To prove the converse, assume conditions 1) and 2) are satisfied. We define the coloring as follows: for every
we set
and for every
we set
.
Then we have.
On the other hand,
Then by condition 2), we get.
Corollary 2.2 It is proved in [1] that an -regular finite simple graph with
vertices is balanced if and only if
is even or
. This fact also follows immediately from Lemma 2.1. In [13] , the authors deduce the same fact from their characterization of balanced graphs.
Lemma 2.1 shows that the balancedness of a graph completely depends on the degree sequence of it. This is no longer the case for -balanced graphs for
. In fact, the trees
and
in Figure 3 have the same degree sequence
, and it is not difficult to see that
is 3-balanced while
is not.
The fact that, for, the
-balancedness is not determined by the degree sequence causes difficulties in proving that random graphs are
-balanced. It also seems plausible that, generically,
-balancedness is a weaker condition than balancedness, although it does not seem easy to describe (with a good sufficient condition) when exactly is this true. It is useful to point out the following simple fact.
Proposition 2.3 For all distinct there exists a finite simple graph which is
-balanced but not
-balanced.
Proof. Let be a prime number such that
.
Let us first assume that. If
divides
, then the graph
is
-balanced but not
-balanced. If
does not divide
then the graph
is
-balanced but not
-balanced.
Now assume that. Then the graph
is
-balanced but not
-balanced.
3. Combinatorial Lemmas
Let. The elements of
consist of sequences of positive integers of length
such that no term is bigger than
. We denote
.
Now we introduce the notion of balanced sequences:
Definition 3 A sequence (an element) is called balanced if and only if there exists a partition
such that
1)
2)
The partition will be called a balanced partition.
In these new terms, Lemma 2.1 states that a graph is balanced if and only if its degree sequence is balanced.
When the sequence is not balanced, we would like to measure how far it is from being balanced.
Figure 3. The trees and
have the same degree sequence;
is 3-balanced while
is not.
Definition 3.1 Let be any finite sequence of non-negative integers. The quantity
will be called the balance of.
Remark 3.2 By Lemma 2.1, a sequence is balanced if and only if
. The quantity
, somewhat roughly, measures how far the sequence is from being balanced. For an example, let
and be a sequence of length 8. It is easy to see
.
The following easy lemma will be useful:
Lemma 3.3 Let be any finite sequence of non-negative integers. Then
.
Proof. We will present a constructive proof.
Without loss of generality, we may assume that. First, let us assume that
is even, so let
. We will build two subsets
of
inductively such that
,
and
.
We divide the sequence into pairs, and we will abide by the rule that exactly one element of each pair belongs to
and the other element belongs to
. We start by letting
. Assume now we have built the subsets
such that
and
for all
.
Let. If
then we let
but if
then we let
, and we proceed by induction. Then we let
. Clearly, we have
.
If is odd, then we may replace
by
and apply the previous argument.
We will need the following notations
Definition 3.4 Let. We will denote
Lemma 3.5 Let such that
and
. Then
is balanced.
Proof. Let. Without loss of generality we may assume that
. If
then
is clearly balanced so let
and let
.
By Lemma 3.3, hence there exists a partition
such that
and
. Then there exists a partition
such that
and
. By letting
we obtain that
,
, and
.
4. Proof of Theorem A
First, we will discuss the case of labeled trees. The following theorem of J. W. Moon will play a crucial role.
Theorem 4.1 (see [14] ) If is a fixed positive constant, then in a random labeled tree
with
vertices, the maximum degree
satisfies the following inequality
Remark 4.2 By choosing we obtain that
in a random tree with vertices.
We will use only the upper bound in the inequality of Remark 4.2. Besides the upper bound on the maximum degree in random trees, we also need a lower bound on the number of vertices with degree 1, and with degree 2. Notice that, since the sum of degrees of a tree with vertices is exactly
, at least half of the vertices have degree either 1 or 2. However, we need a linear lower bound for the number of vertices of degree 1 and for the number of vertices of degree 2 separately.
Let be the random variable which denotes the number of vertices of degree
in a labeled tree
with
vertices. Also let
. It has been proved by A. Rényi (see [15] ) that the asymptotic distribution of random variable
is normal with mean
and variance
. A similar result has been proved for the random variable
, by A. Meir and J. W. Moon (see [16] ), namely, that the asymptotic distribution of the random variable
is normal with mean
and variance
. Combining these two results we can state the following theorem (due to A. Rényi and A. Meir-J.W. Moon)
Theorem 4.3 Let be fixed real numbers,
; and for
, let
denotes the probability that
. Then
We need the following immediate corollary of this theorem
Corollary 4.4 In a random labeled tree with vertices, for all
,
.
Now, in the case of random labeled trees, Theorem A immediately follows from Theorem 4.1, Corollary 4.4, and Lemma 3.5.
The case of unlabeled trees: We will use the results analogous to Theorem 4.1 and Theorem 4.3. The analogue of Theorem 4.1 is proved by W. Goh and E. Schmutz:
Theorem 4.5 (see [12] ) There exists positive constants such that in a random unlabeled tree
with
vertices, the maximum degree
satisfies the inequality
.
Now, for any let the random variable
denotes the number of vertices of degree
in a random unlabeled tree with
vertices. The following theorem is due to M. Drmota and B. Gittenberger; in the case of
, as a special case, it provides an analogue of Theorem 4.3.
Theorem 4.6 (see [17] ) For arbitrary fixed natural, there exist positive constants
and
such that the limiting distribution of
is normal with mean
and variance
.
Corollary 4.7 For all and
, in a random unlabeled tree with
vertices
.
Now, in the case of unlabeled trees, the claim of Theorem A follows from Theorem 4.5, Lemma 3.5, and Corollary 4.7.
5. -Balanced Trees: Proof of Theorem B
In this section we will assume that. The fact that the
-balancedness is not determined by the degree sequence causes significant difficulties in proving that random graphs are balanced. We nevertheless prove that random trees are strongly
-balanced by more careful study of
-balancedness.
First, we need to prove the following technical lemma.
Lemma 5.1 Let be a tree and
be distinct vertices of
with degree at least
. If
are distinct pre-leaf vertices of
then there exists a strongly 3-balanced coloring
of
such that
and
.
Proof. The proof is by induction on. For
the claim is obvious (since, in this case,
will be isomorphic either to a path or to the double star
), so we will assume that
and the claim holds for all trees of order less than
.
Assume that at least one of the following two conditions holds:
(c1) there exists such that
;
(c2) there exists a leaf vertex not adjacent to any of the vertices.
Then there exists a leaf such that if
is a full subgraph on
, then, in the tree
, we have
, and
are still pre-leaf vertices.
By inductive hypothesis, there exists a strongly 3-balanced coloring of
such that
and
. Let
be the unique vertex of
adjacent to
. Without loss of generality, we may assume that
and
.
If then we let
thus extending
to a strongly 3-balanced coloring
of
such that
and
.
If, however, then there exists
such that
; also, since
,
there exists a branch of
with respect to
which is disjoint from
. Let
be a leaf vertex in
. Then
and
. We define
as follows:
Notice that because of the inequality, we have
and
. Then the map
is a strongly 3-balanced coloring.
Now, suppose that neither of the conditions (c1) and (c2) hold. Let be the path in
starting at
and ending at
(it may possibly consist of just the vertices
and
). Then the tree
satisfies the following conditions: there exists two vertices
in
and paths
starting at
respectively such that any vertex of
either belongs to one of the paths
or it is a leaf vertex adjacent to one of the vertices
. Then it is straightforward to build a strongly 3-balanced coloring
satisfying the conditions
and
.
The following proposition is interesting in itself; it will also play a key role in proving Theorem B.
Proposition 5.2 If is a tree with
then
is strongly
-balanced. Moreover, for
any two distinct pre-leaf vertices and
of
there exists a strongly 3-balanced coloring
such that
.
Proof. The proof will be by induction on. For
we have
hence
is isomorphic to a path. Thus, the claim is obvious. Let us now assume that
, and the claim holds for all trees
of
order less than with
.
Let and
. We will consider the following three cases separately:
Case 1..
Let be a leaf of
,
, and let
be the full subgraph of
on
. Then we have
By inductive hypothesis, there exists a strongly 3-balanced coloring of
.
On the other hand, is adjacent to exactly one vertex in
; let
be this vertex. Let
be any element of
. We extend the coloring
of
to a strongly 3-balanced coloring
by defining
.
Case 2..
Let be distinct leaves and
be the only vertices of
adjacent to
respectively (
and
are not necessarily distinct). Let also
be the full subgraph of
on the set
. Then we still have the inequality
. Hence, by inductive assumption, there exists a strongly 3-balanced coloring
of
.
Then there exist distinct such that
and
. Thus we can extend
to a strongly 3-balanced coloring of
by defining
and
.
Case 3..
The major difference in this case compared with the previous two cases is that when we obtain by deleting some arbitrary three leaves
from
, we may lose the inequality
. (Notice that
possesses three leaf vertices unless it is isomorphic to a path). Suppose
are the vertices adjacent to
respectively. Note that
are not necessarily distinct. If we have the inequality
then by inductive assumption we would have a strongly 3-balanced coloring
. However, if
then it becomes problematic to extend
to a strongly 3-balanced coloring
. Thus we need to employ different and more careful tactics.
We will prove the following lemma which suffices for the proof of Proposition 5.2 in the case.
Lemma 5.3 Let be a tree with
vertices where
. If
are distinct pre-leaf vertices of
then there exists a strongly 3-balanced coloring
such that
.
Proof. The proof of the lemma will be again by induction on. The “
part” of the claim will be needed to make the step of the induction. For
, the graph
is isomorphic to a path thus the claim is obvious. For
it can be seen by a direct checking. (We leave this to a reader as a simple exercise.) Thus let us assume that
.
Let. Let also
. We will consider the following cases (the notations in each case will be independent of the notations of other cases):
Case A: The vertices and
are the only pre-leaf vertices of
.
The claim is obvious when, so we may assume that
. We will consider two sub- cases:
Sub-case 1:.
Then there exist leaves such that
is adjacent to
and
are adjacent to
. Let
be the full subgraph of
on
. Notice that
and
are still pre-leaf vertices of
. By the inductive hypothesis,
has a strongly 3-balanced coloring
such that
. We may assume that
. Then we extend
to a strongly 3-balanced coloring
by letting
.
Sub-case 2:.
In this case there exists a path in
where
is a leaf,
are vertices of degree two, and
where are the leaves adjacent to
. Then we have the inequalities
and
. We will construct the required strongly 3-balanced coloring explicitly as follows.
First, for all we let
when
is odd, and
when
is even. We also let
and
.
Now we need to define the coloring on the remaining set
Let where
for all
. (Thus we are reorder the elements of the set
from closest to the farthest from the leaf
.) Then, for all
, we let
when
is odd, and
when
is even.
For the rest of the proof we will assume that has more than two pre-leaf vertices.
Case B: and
is not special.
Let be distinct leaves such that
is adjacent to
,
is adjacent to
, and
is adjacent to a vertex
distinct from
and
. We let
be the full subgraph on
. Then
and we have
. By inductive hypothesis, there exists a strongly 3-balanced coloring
such that
. Without loss of generality we may assume that
. Then we extend
to a strongly 3-balanced coloring
as follows: if
then we let
; and if
then we let
.
Case C: and
is special.
Let be the only leaf adjacent to
,
be the unique non-leaf vertex adjacent to
,
be a leaf vertex not adjacent to
, and
be the unique vertex adjacent to
. We let
be the full subgraph on
. Then
and
. By inductive hypothesis, there exists a strongly 3-balanced coloring
. Then we extend
to a strongly 3-balanced coloring
as follows: we let
such that
is distinct from
and
. Then we define
such that
is distinct from
and
. Finally we let
such that
is distinct from
and
. Notice also that we obtain
.
Case D: and there exists a leaf vertex adjacent to
.
This case is similar to Case B. Since and
, we have
. If
, we let
be leaves adjacent to
respectively; and if
, we let
be leaves adjacent to
respectively, and
be a leaf not adjacent to either of the vertices
. We define
be the full subgraph on
. Then
hence
admits a strongly 3-balanced coloring
such that
. We extend
to a strongly 3-balanced coloring to
as in Case B.
Case E:,
is special and there exists a leaf vertex adjacent to
.
This case is similar to Case C. Let be the only leaf adjacent to
,
be the unique non-leaf vertex adjacent to
,
be a leaf vertex adjacent to
. We let
be the full subgraph on
. Then
and
. By inductive hypothesis, there exists a strongly 3-balanced coloring
. Then we extend
to a strongly 3-balanced coloring
as follows: we let
such that
is distinct from
and
. Then we define
such that
is distinct from
and
. Finally we let
such that
is distinct from
and
.
Case F:, and there is no leaf vertex adjacent to
.
Since, there exists a special vertex
adjacent to
. Let
be the unique leaf adjacent to
. Let also
be a leaf not adjacent to any of the vertices
(such a leaf exists because
), and let
be the unique vertex adjacent to
.
We define to be the full subgraph on
. By inductive assumption, there exists a strongly 3-balanced coloring
, moreover, if
then
.
If, then we let
be any element of
distinct from
. Then we let
be any element of
distinct from
and
. Finally, we let
be any element of
distinct from
and
. Thus we have extended
to a strongly 3-balanced coloring
such that
.
If then
and we may assume that
. Then we let
be any element of distinct from
and
; then we let
be any element of
distinct from
and
; finally we let
be any element of
distinct from
and
.
Case G:.
In this case the claim follows immediately from Lemma 5.1.
Now we can prove an analogous result for -balanced graphs.
Proposition 5.4 Let be a tree with
vertices where
and
. Then
is strongly
-balanced.
Proof. The proof is by induction on. For
, the claim is true by Proposition 5.2.
Assume now. The tree
has
vertices
such that
. Moreover, for all distinct
, the vertices
and
are not connected by an edge. Let also
, and
be a full subgraph on the subset
. Then
is a forest with
vertices but with
. This implies that
is a subgraph of a tree
with
vertices where
.
Then. By inductive hypothesis, we obtain that
is strongly -balanced, hence
is strongly
-balanced. Since no two elements of
are adjacent, we obtain that
is strongly
-balanced.
Now, for random labeled trees, Theorem B follows immediately from Theorem 4.1 and Proposition 5.4; and for random unlabeled trees, it follows immediately from Theorem 4.5 and Proposition 5.4.
References
- Lee, S.-M., Liu, A. and Tan, S.K. (1992) On Balanced Graphs. Congressus Numerantium, 87, 59-64.
- Cahit, I. (1987) Cordial Graphs: A Weaker Version of Graceful and Harmonious Graphs, Ars Combinatoria, 23, 201- 207.
- Gallian, J.A. (2009) A Dynamical Survey of Graph Labeling. The Electronics Journal of Combinatorics, Dynamic Survey 6, 43 p. (electronic).
- Graham, R. and Sloane, N. (2009) On Additive Bases and Harmonious Graphs. SIAM Journal of Algebraic and Discrete Mathematics, 1, x382-x404. http://dx.doi.org/10.1137/0601045
- Cahit, I. (1990) On Cordial and 3-Equitable Graphs, Utilitas Mathematica, 37, 189-198.
- Cayley, A. (1889) A Theorem on Trees. The Quarterly Journal of Mathematics, 23, 376-378.
- West, D.B. (2001) Introduction to Graph Theory. 2nd Edition, Prentice-Hall, Inc., Upper Saddle River, 82-83.
- Otter, R. (1948) The Number of Trees. Annals of Mathematics, 49, 583-599.
- Bollobás, B. and Guy, R. (1983) Equitable and Proportional Coloring of Trees. Journal of Combinatorial Theory, Series B, 34, 177-186.
- Ben-Eliezer, I. and Krivelevich, M. (2009) Perfectly Balanced Partitions of Smoothed Graphs. Electronic Journal of Combinatorics, 16, Note N14.
- Bollobás, B. (2001) Random Graphs. Cambridge Studies in Advanced Mathematics (Book 73). 2nd Edition, Cambridge University Press, Cambridge.
- Goh, W. and Schmutz, E. (1994) Unlabeled Trees: Distribution of the Maximum Degree. Random Structures and Algorithms, 5, 13-24.
- Kong, M.C., Lee, S.-M., Seah, E. and Tang, A. (2008) A Complete Characterization of Balanced Graphs (English Summary). Journal of Combinatorial Mathematics and Combinatorial Computing, 66, 225-236.
- Moon, J.W. (1968) On the Maximum Degree in a Random Tree. The Michigan Mathematical Journal, 15, 429-432.
- Rényi, A. (1959) Some Remarks on the Theory of Trees. Magyar Tud. Akad. Mat. Kutat Int. Kzl, 4, 73-85.
- Meir, A. and Moon, J.W. (1968) On Nodes of Degree Two in Random Trees. Mathematika, 15, 188-192. http://dx.doi.org/10.1112/S0025579300002552
- Drmota, M. and Gittenberger, B. (1999) Distribution of Nodes of Given Degree in Random Trees. Journal of Graph Theory, 31, 227-253. http://dx.doi.org/10.1002/(SICI)1097-0118(199907)31:3<227::AID-JGT6>3.0.CO;2-6