Bell Numbers of Graphs
by
Bryce Duncan
A dissertation submitted to the Graduate Faculty of
Auburn University
in partial ful llment of the
requirements for the Degree of
Doctor of Philosophy
Auburn, Alabama
May 7, 2012
Keywords: Graph Theory, Vertex Partitions, Enumeration
Copyright 2012 by Bryce Duncan
Approved by
Peter Johnson, Chair, Professor of Mathematics
Dean Ho man, Professor of Mathematics
Curt Lindner, Distinguished University Professor of Mathematics
Chris Rodger, C. Harry Knowles Professor of Mathematics
Abstract
Let G be a simple graph with vertex set V(G). Let F be a family of graphs such that
K1 2F. Denote by B(G;F) the number of unordered partitions of V(G) such that each
part induces a member ofF. We call B(G;F) the Bell number of the graph G with respect
to the family F. We investigate properties of this function for di erent families F, and
conditions on F for the function B(G;F) to have certain properties.
ii
Acknowledgments
I am indebted to Rhodes Peele for the course in enumeration that uncovered this topic,
and my to advisor Peter Johnson for giving me direction with this problem and invaluable
editorial assistance. I cannot give enough thanks to Ken Baker and Tony Hickman, without
whom I would not have had the opportuity to attend Auburn. For their emotional support
over the years, I thank the Rowe family - especially Katie, Kathy, and John. All my love
to my partner Stephen, even though he nds all this math stu terribly dull, because every
day he gives me reason to smile.
iii
Table of Contents
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Information on Set Partitions . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 The Bell Number of a Graph With Respect to the Family F0 . . . . . . . . . . 4
2.1 Deletion and Contraction Properties of B(G;F0) . . . . . . . . . . . . . . . 4
2.2 Multiplicative Property of B(G;F0) . . . . . . . . . . . . . . . . . . . . . . 7
2.3 B(G;F0) for Particular Graphs . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.4 B(G;F0) for Graphs with Two Components . . . . . . . . . . . . . . . . . . 13
3 The Bell Number of a Graph With Respect to the Family Ft . . . . . . . . . . 16
3.1 Complete Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.3 Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.4 Combinations of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4 The Bell Number of a Graph With Respect to the Family Ff . . . . . . . . . . 22
5 Families F and Their Properties . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5.0.1 Situations where B(G;F) is Maximum . . . . . . . . . . . . . . . . . 25
5.0.2 Families with a Multiplicative Property . . . . . . . . . . . . . . . . . 25
5.0.3 Families with a Cut Vertex Property . . . . . . . . . . . . . . . . . . 26
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
iv
Chapter 1
Introduction
Suppose that G is a simple graph and F is a family of simple graphs where K1 2F.
We de ne the Bell number of G with respect to F, denoted B(G;F), to be the number of
unordered partitions of V(G) such that each member of the partition induces a member of
F. Such a partition is referred to as a F-partition of G. Members of partitions are referred
to as blocks (even if the partition is not a F-partition).
This problem arose when I was an undergraduate working with Rhodes Peele at Auburn
University at Montgomery. I was assigned the following problem. Due to Herbert Wilf [1],
let [n] denote the set of integers 1 through n:
Let f(n) be the number of subsets of [n] that contain no two consecutive elements. Find
the recurrence that is satis ed by these numbers, and then ? nd? the numbers themselves.
[1]
But I misread subsets as partitions; that is, I thought that f(n) was the number
of unordered partitions of [n] in which no partition set contained two consecutive integers.
This task proved to be more involved than Wilf?s problem. Dr. Peele suggested we view the
problem as being about a simple graph G where V(G) = [n] and two distinct vertices i;j
are adjacent if and only if ji jj = 1. In other words, G is a path on n vertices, and we
seek to partition V(G) such that no two vertices together in the same block have an edge
between them - that is, each block is an independent set of vertices of G. It turns out that
the number of such partitions is (n 1)th Bell number.
1
The nth Bell number, bn, denotes the number of non-empty, unordered partitions of an
n-element set. It is surprising that the number of partitions of the vertices of a path into
independent sets followed the Bell sequence (with a shift in index), since these partitions
are not unrestricted. Expanding this question to other graphs G, the Bell-like behavior
motivated referring to this problem as nding the \Bell number" of G. With Dr. Johnson,
this question was expanded from partitioning vertex sets into independent sets to partitioning
into blocks which ecach induce a member of a speci ed family of graphs F. Denoting the
number of such partitions by B(G;F), we call this the Bell number of G with respect to the
family F.
1.1 Information on Set Partitions
The Bell numbers satisfy a well-known recurrence
bn =
n 1X
i=0
n 1
i
bi:
The proof of the recurrence is enlightening when it comes to certains proofs for the Bell
numbers of graphs, so it is worthwhile to brie y examine it to build familiarity.
Proof. To partition the set [n], consider which block will contain the element n. If n is in a
block by itself, then there is n 10 ways to choose that block, n 1 elements remain outside
of the block, and there are bn 1 ways to partition them. If n is in a block with one other
element, then there are n 11 ways to form that block, n 2 elements remain outside of the
block, and there are bn 2 ways to partition the rest. More generally, if n is in a block with
k 1 other elements, then there are n 1k 1 ways to form the block, n k elements remain
outside of the block, and there are bn k ways to partition the rest. Double counting does
not occur from this process, so the recurrence is evident.
2
Another way of representing the Bell numbers is in terms of Stirling Numbers of the
Second Kind, denoted
( n
k
)
, which indicates the number of unordered partitions of an
n-element set into exactly k blocks. Clearly,
bn =
nX
k=1
( n
k
)
The corresponding notations that we will use for graphs G are B(G;F) and S(G;F;k).
For graphs, the latter is de ned to be the number of unordered partitions of V(G) into
exactly k blocks such that each block induces a member of F. It is, of course, the case that
the sum of S(G;F;k) over 1 k jV(G)j yields B(G;F).
3
Chapter 2
The Bell Number of a Graph
With Respect to the Family F0
F0 :=fKn : n2[n]g
With Kn denoting the complete graph on n vertices,F0 is the collection of graphs with
no edges and a positive number of vertices. The work I did with Rhodes Peele focused on
B(G;F0) for various graphs G. In particular, we considered trees, cycles, stars, and comple-
ments of paths. [2] More, we discovered certain properties of the B(G;F0) function.
2.1 Deletion and Contraction Properties of B(G;F0)
For a simple graph G, the minimal k for which S(G;F0;k) is non-zero is the chromatic
number (G). The chromatic polynomial (G; ) of a graph is a polynomial whose evaluation
at integer m yields the number of functions f : V(G)!f1;2;:::;mgthat properly color G
with at most m colors. It is commonly written as follows.
(G; ) =
n(G)X
k=1
pk(G) (k)
where (k) = ( 1) ( k + 1):[7]
Note that S(G;F0;k) = pk(G). It?s possible to obtain the Bell number of a graph G
with respect to F0 if the quantities pk(G) are known for all 1 k jV(G)j, but that?s
equivalent to nding the chromatic polynomial, which is known to be a di cult problem.
4
(cite something here)
The chromatic polynomial is known to have a very convenient deletion/contraction
property which is shared by the function B(G;F0). For a graph G, if e2E(G) then denote
by Gne the graph G with edge e removed. Denote by G e the graph G with the ends of
e identi ed as a single vertex, which is adjacent to all vertices to which either of the ends
of e were adjacent; if duplicate edges are created, merge them into a single edge. Then the
chromatic polynomial has the following property.
(G; ) = (Gne; ) (G e; )
The reason this works is as follows. Partitions of V(Gne) into independent sets consist
of two types: partitions where the ends of e appear together in a block, and partitions where
the ends of e are in di erent blocks. Partitions of V(G) into independent sets forbid the
ends of e from appearing in the same block, and partitions of V(G e) are those where the
ends of e are always together in the same block (as they are identi ed as the same vertex).
This means that
pk(G) = pk(Gne) pk(G e) for 1 k jV(G)j
Since these coe cients determine the Chromatic polynomial, it must be the case that
(G; ) = (Gne; ) (G e; ):
Moreover, those coe cients determine the Bell number, so it must also be the case that
B(G;F0) = B(Gne;F0) B(G e;F0):
5
Question Suppose thatF is a family of graphs with K12F. If for every graph G and
every e2E(G) it happens that B(G;F) = B(Gne;F) B(G e;F), does it follow that
F F0 ?
Theorem 2.1. Let G = (V;E) be a simple graph and w a vertex not in V. Let Gw represent
the collection of graphs obtained from G by adding w as a pendant vertex.
Gw =fHv : V(H) = V [fwg and E(H) = E(G)[fw;vg for some v2Vg
Then for any u, v 2 V, S(Hu;F0;k) = S(Hv;F0;k) for each 1 k jV(G)j+ 1.
Consequently, B(Hu;F0) = B(Hv;F0).
Proof. Let e = fw;ug2 E(Hu) and f = fw;vg2 E(Hv). Suppose we wish to examine
the partitions of V(Hu) and V(Hv) with respect to F0 into exactly k blocks with 1 k
jV(G)j+ 1. By deletion and contraction:
S(Hu;F0;k) = S(Hune;F0;k) S(Hu e;F0;k)
S(Hv;F0;k) = S(Hvnf;F0;k) S(Hv f;F0;k)
Alternatively, we may represent Hune by G + w to represent the disjoint union of G
and w. And then we see that Hvne = G+w as well. Since Hu e?G?Hv f,
S(Hu;F0;k) = S(G+w;F0;k) S(G;F0;k)
S(Hv;F0;k) = S(G+w;F0;k) S(G;F0;k)
Therefore,
S(Hu;F0;k) = S(Hv;F0;k):
6
Since B(J;F0) =
n(J)X
k=1
S(J;F0;k) for any graph J, we see that B(Hu;F0) = B(Hv;F0).
2.2 Multiplicative Property of B(G;F0)
Suppose that G and H are graphs with disjoint vertex sets and denote by G_H the
join of G and H where V(G_H) = V(G)[V(H) and E(G_H) = E(G)[E(H)[ffx;yg:
x2V(G);y2V(H)g. Then
B(G_H;F0) = B(G;F0) B(H;F0)
The property follows from the observation that if p is a partition of V(G) into inde-
pendent sets and q is a partition of V(H) into independent sets, then p[q is a partition of
V(G_H) into independent sets. Conversely, if s is a partition of V(G_H) into independent
sets then no block of s contains both a vertex of V(G) and a vertex of V(H), so s can be
sorted into blocks consisting only of vertices of G and blocks consisting only of vertices of
H. The former is a partition p of V(G) into independent sets and the latter is a parititon q
of V(H) into independent sets.
Note also that ifF0 F0, then B(G_H;F0) = B(G;F0) B(H;F0) by the same argu-
ment, because the number of elements in each block is irrelevant to the proof.
Question Let F be a family of graphs containing K1. If B(G_H;F) = B(G;F)
B(H;F) for all simple graphs G and H, is it necessarily the case that F F0?
7
2.3 B(G;F0) for Particular Graphs
Let n2N. Denote by Kn the complete graph on n vertices, and Kn its complement,
the graph with n vertices and no edges. Then it is immediate that
B(Kn;F0) = 1 and B(Kn;F0) = bn:
Theorem 2.2. Let Tn denote a tree on n vertices. Then
B(Tn;F0) = bn 1
Proof. By the deletion and contraction property, for any graph G and vertex w not in V(G):
if Hv;Hu2Gw, then these two graphs will have the same Bell number wih respect to F0 by
2.1. Applying this to trees obtains the result, as follows.
The result is immediate for n 2, so assume n > 2. Let Tn be a tree on n vertices.
Choose any non-leaf r2V(Tn). Since any tree on at least two vertices has at least two leafs,
let l be a leaf of Tn and e its edge. Denote by T0n the graph obtained from Tn by deleting e
and attaching l to r. Let G = Tnnl, then Tn;T0n2Gl. So
B(Tn;F0) = B(T0;F0):
If we iterate this process, we can move all edges of Tn to r. At each step, we choose a
leaf l not adjacent to r, delete its edge, and connect it to r. At each step, the Bell number
is preserved. After at most n 2 steps, we?ll arrive at K1;n 1, the star with n 1 leafs. And
so we see that for any tree Tn on n vertices,
8
B(Tn;F0) = B(K1;n 1;F0)
Since K1;n 1 = K1_Kn 1,
B(K1;n 1;F0) = B(K1_Kn 1;F0) = B(K1;F0)B(Kn 1;F0) = bn 1
Theorem 2.3. Let Pn denote a path on n vertices, and Pn the complement of Pn with respect
to Kn. Then
B(Pn;F0) = fn+1
where fn+1 denotes the (n+ 1)th Fibonacci number.
Proof. Let the vertices of Pn, from one end to the other, be f1;2;:::;ng. Consider parti-
tioning Pn with respect to F0. Blocks containing element n are either the singleton fng or
the doubleton fn 1;ng. If fng is a block, then there are B(Pn 1;F0) partitions of the
remaining vertices. If fn 1;ng is a block, then there are B(Pn 2;F0) partitions of the
remaining vertices. Therefore,
B(Pn;F0) = B(Pn 1;F0) +B(Pn 2;F0):
Since B(P1;F0) = 1 and B(P2;F0) = 2, the recurrence shows us that the sequence
(B(Pn;F0)) is \Fibonacci-like". In particular, B(Pn;F0) = fn+1.
Theorem 2.4. Let K1;n denote the star graph with n leafs, n 0. Denote by K1;n its
complement. Then
B(K1;n;F0) = n+ 1
9
Proof. Let r be the central vertex of K1;n. Notice that K1;n = K1 + Kn. Considering
partitioning its vertices with respect to F0. None of the vertices in the Kn component may
appear in a block together, and r in the K1 component can appear in a block either by itself
or with any of the vertices in the Kn component. Therefore, there are n+ 1 ways to form a
partition of K1 +Kn, so B(K1;n;F0) = n+ 1.
Corollary Every positive integer is the Bell number, with respect to F0, of some graph.
Corollary For n> 3, there exist trees T;R on n vertices such that B(T;F0)6= B(R;F0).
Proof. Let T = Pn and R = K1;n 1. Done.
Theorem 2.5. Let Cn denote a cycle on vertex set f1;2;:::;ng, for n 3. Then
B(Cn;F0) =
n 2X
k=0
( 1)kbn (k+1)
Proof. Apply deletion and contraction repeatedly.
B(Cn;F0) = B(Pn;F0) B(Cn 1;F0)
= B(Pn;F0) B(Pn 1;F0) +B(Cn 2;F0)
= ...
= B(Pn;F0) B(Pn 1;F0) +:::+ ( 1)n 3B(C3;F0)
= Pn 4k=0( 1)kbn (k+1) + ( 1)n 3B(C3;F0)
Since B(C3;F0) = 1 = b2 b1, the result follows.
Theorem 2.6. Let Cn denote the complement of a cycle on n 4 vertices. Then
B(Cn;F0) = fn + 2fn 1
where fk denotes the kth Fibonacci number.
10
Proof. Let Cn have vertex set f1;2;:::;ng, in order around the cycle, and consider parti-
tioning wih respect to F0. In particular, consider vertex n. Vertex n may be in a block by
itself, with 1, or with n 1. However, 1 and n 1 cannot be in a block together. Therefore,
we have three cases. If n is in a block by itself, there are B(Pn 1;F0) ways to partition the
remaining vertices. If eitherf1;ngorfn 1;ngare blocks, then there are B(Pn 2;F0) ways
to partition the rest. Therefore,
B(Cn;F0) = B(Pn 1;F0) + 2B(Pn 2;F0):
Since we know that B(Pn;F0) = fn+1, the result follows.
Theorem 2.7. Let Mn be a collection of n vertex-disjoint edges. (That is, Mn is a matching
on 2n vertices.) Then, for n 2,
B(Mn;F0) =
n 1X
k=0
n 1
k
bn+k:
Proof. Deletion and contraction can instead be thought of as insertion and contraction.
Suppose n 2 and Mn is a matching on 2n vertices. Then the graph obtained from Mn by
inserting an edge between any two of its non-adjacent vertices results in P4 +Mn 2. Deletion
and contraction would tell us the Bell number of this graph is
B(P4 +Mn 2;F0) = B(Mn;F0) B(P3 +Mn 2;F0):
Therefore,
B(P4 +Mn 2;F0) +B(P3 +Mn 2;F0) = B(Mn;F0):
Successive applications of insertion/contraction to terms of the form B(Pi+Mj;F0) (for
j > 0) will transform Pi +Mj into a path, providing we choose to insert edges only between
11
vertices of degree 1. The resulting coe cients on the terms are of importance. To see how
they are generated, suppose that n is su ciently large to apply insertion/contraction several
times. On each line, we will order the terms B(Pi +Mj;F0) by decreasing j.
B(Mn;F0) = B(P4 +Mn 2;F0) +B(P3 +Mn 2;F0)
= B(P6 +Mn 3;F0) +B(P5 +Mn 3;F0) +B(P5 +Mn 3;F0) +B(P4 +Mn 3;F0)
= B(P6 +Mn 3;F0) + 2B(P5 +Mn 3;F0) +B(P4 +Mn 3;F0)
Notice that under insertion/contraction, adjacent terms B(Pi + Mj;F0) and B(Pi 1 +
Mj 2;F0) each generate a term involving B(Pi+1 + Mj 3;F0). The consequence of this is
after i applications of insertion/contraction, the coe cients on the terms are precisely ni .
B(Mn;F0) = B(P6 +Mn 3;F0) + 2B(P5 +Mn 3;F0) +B(P4 +Mn 3;F0)
= B(P8 +Mn 4;F0) + 3B(P7 +Mn 4;F0) + 3B(P6 +Mn 4;F0) +B(P5 +Mn 4;F0)
= B(P10 + 4Mn 5;F0) + 4B(P9 +Mn 5;F0) + 6B(P8 +Mn 5;F0)
+4B(P7 +Mn 5;F0) +B(P6 +Mn 5;F0)
= ...
=
kX
i=0
k
i
B(P2k+2 i +Mn k 1;F0)
When k = n 1,
B(Mn;F0) =
n 1X
i=0
n 1
i
B(P2(n 1)+2 i +M0;F0)
Since M0 is the empty graph, we?re left with B(P2n i;F0) = b2n i 1 in the ith term,
above. So,
B(Mn;F0) =
n 1X
i=0
n 1
i
b2n i 1
=
n 1X
i=0
n 1
n 1 i
bn+(n 1 i) =
n 1X
i=0
n 1
k
bn+k
12
2.4 B(G;F0) for Graphs with Two Components
The material in this section originally appeared in [3]. Here we consider graphs with
two components.
Theorem 2.8. Suppose that D is a graph with components G and H, so we can write
D = G+H. Let V(G) have size n and V(H) have size m. Then
B(G+H;F0) =
nX
i= (G)
mX
j= (H)
S(G;F0;i)S(H;F0;j)B(Ki +Kj;F0)
where (G) and (H) are the chromatic numbers of G and H and Ki;Kj are complete
graphs on i and j vertices, respectively.
Proof. Let q = fq1;q2;:::;qig and r = fr1;r2;:::;rjg be F0-partitions of G and H respec-
tively. We can form a F0-partition p = fp1;p2;:::;pkg of G + H = D by combininig the
blocks of q and r in such a way that each block of p is either a block of q, a block of r, or
a union of one block of q and one block of r. So, we see that F0-partitions of D may be
constructed from any pair of partitions of its components.
Conversely, suppose that p =fp1;p2;:::;pkgis aF0-partition of D. For each 1 i k,
de ne qi = pi \V(G) and ri = pi \V(H). Let q = fqi : qi 6= ;;1 i kg and
r = fri : ri 6= ;;1 i kg, and observe that q and r are F0-partitions of G and H
respectively. Consequently, each F0-partition of D arises from a pair (q;r) of F0-partitions
of G and H. Further, if a V(G) is a non-empty independent set and a =2q, then a[ri6= pj
for any i;j2f1;2;:::;kg. Therefore, if q0 and r0 areF0-partitions of G and H respectively,
then the F0-partitions of D derived from (q0;r0) and (q;r) are the same if and only if q = q0
and r = r0.
13
Regarding the blocks of q and r as vertices of complete graphs Ki and Kj respectively,
then we see that the partitions yielded by the construction above are in one-to-one corre-
spondence with the partitions of Ki+Kj. Since there are S(G;F0;i)F0-partitions of G into i
blocks and S(H;F0;j)F0-partitions of H into j blocks, there are S(G;F0;i)S(H;F0;j) such
pairs (q;r) and B(Ki+Kj;F0)S(G;F0;i)S(H;F0;j) partitions of D that can be constructed
from those pairs.
Theorem 2.9. For complete graphs Ki and Kj (with i j), B(Ki+Kj;F0) = Pil=0 il j!(j l)!
Proof. Note that B(Kn;F0) = 1, and that partition consists only of singletons. F0-partitions
of Ki +Kj will consist of singletons and only those doubletons consisting of one vertex from
V(Ki) and one vertex from V(Kj).
Let P and Q be the F0-partitions of Ki and Kj, respectively. We can construct a F0-
partition of Ki +Kj from blocks of P and Q such that each block of the resulting partition
is either a block of P (i.e., a vertex of Ki), a block of Q, or the union of exactly one block
of P and one block of Q.
There are il ways to select l blocks from P. If these l blocks are used to form unions
with blocks of Q in a partition of Ki + Kj, then there are j!(j l)! ways to choose blocks of Q
for the l blocks of P. ThisF0-partition of Ki +Kj will have j +i l blocks: l blocks which
are unions of blocks of P and blocks of Q, j l blocks which are singletons of Q, and i l
blocks which are singletons of P. Since there can be no other way to form F0-partitions of
Ki +Kj with j+i l blocks, we nd that S(Ki +Kj;F0;j+i l) = il j!(j l)!. Consequently,
B(Ki +Kj) = Pil=0S(Ki +Kj;F0;j +i l)
= Pil=0 il j!(j l)!.
14
Theorem 2.10. Consider a graph D with connected components G and H.
Then S(G+H;F0;k) =
X
(i;j)2N2
S(G;F0;i)S(H;F0;j)S(Ki +Kj;F0;k)
the sum taken over pairs (i;j) subject to max(i;j) k i + j, (G) i n(G) and
(H) j n(H).
Proof. The method of construction here will be the same as in 2.8. Let
P =fp1;p2;:::;pig be a partition of G with i blocks and Q =fq1;q2;:::;qjg be a partition
of H with j blocks. Then P and Q will be used to construct partitions of G+H where blocks
will be of the form pr, qs, or pr[qs. With this in mind, the pair (P;Q) can construct partitions
of G+H with as few as max(i;j) blocks and as many as i+j blocks. In order to construct
a partition with exactly k blocks from (P;Q), it is necessary that max(i;j) k i+j.
Suppose a pair of partitions (P;Q) of G;H respectively satis es max(i;j) k i + j
for some chosen k. If we regard the blocks of P and Q as vertices of complete graphs
Ki and Kj respectively, then the number of partitions with k blocks yielded by (P;Q)
are in one-to-one correspondence with the partitions of Ki + Kj with k blocks. Since
there are B(G;F0;i), B(H;F0;j) partitions of G with i blocks and H with j blocks, re-
spectively, there are B(G;F0;i)B(H;F0;j) such pairs (P;Q) and thus there are B(Ki +
Kj;F0;k)B(G;F0;i)B(H;F0;j) partitions of G + H with k blocks that can be constructed
from partitions of G with i blocks and partitions of H with j blocks.
As noted in the proof of 2.8, every partition of G+H is derived from some pair (P;Q)
of partitions of G;H separately, and collections of partitions derived from di erent pairs are
disjoint. Since max(i;j) k i + j is a necessary condition on i and j for a partition of
G + H to be constructed from a partition P of G with i blocks and Q of H with j blocks,
and clearly there can be no such partitions unless (G) i n(G) and (H) j n(H),
the sum in 2.9 counts each k-block partition of G+H exactly once.
15
Chapter 3
The Bell Number of a Graph
With Respect to the Family Ft
Ft :=fT : T is a tree g
Ft is the collection of acyclic connected graphs, or trees. For this family, the Bell num-
ber B(G;Ft) is examined in the cases where G is a complete graph, a tree, and a cycle.
Moreover, exploitable properties of B(G;Ft) are found when G has certain features.
It is rst worthwhile to notice that the functions B(G;F0) and B(G;Ft) behave very
di erently.
This material originally appeared in [4].
3.1 Complete Graphs
Theorem 3.1. B(Kn;Ft) = Pbn2ck=0 n!2kk!(n 2k)!
Proof. The subgraph induced by any collection of m vertices (for 1 m n) is Km. Of
these, only K1 and K2 are also trees, so no block of a Ft-partition may contain more than
2 elements. We can count the number of Ft-partitions of Kn by counting the number of
partitions of f1;2;:::;ng containing no blocks of size 2, exactly one block of size 2, exactly
two blocks of size 2, and so on, up to exactly bn2c blocks of size 2.
16
In Kn, there is one Ft-partition with no blocks of size 2. There are n2 ways to choose
one block of size 2, so there are precisely that manyFt-partitions containing exactly 1 block
of size 2. There are 12! n2 n 22 ways to choose blocks of size 2, irrespective of order, so there
are precisely that many Ft-partitions containing exactly 2 blocks of size 2. The number of
ways to select k blocks of size 2, irrespective of order, is 1k!Qk 1i=0 n 2i2 . Notice, however,
that Qk 1i=0 n 2i2 collapses:
Qk 1
i=0
n 2i
2
= n!
2(n 2)!
(n 2)!
2(n 4)!
(n 4)!
2(n 6)!
(n 2k+4)!
2(n 2k+2)!)
(n 2k+2)!
2(n 2k)!
= n!2k(n 2k)!
Thus, the number ofFt-partitions with exactly k blocks of size 2 is n!2kk!(n 2k)!. Summing
over k gives the result.
Remark. Counting the Ft-partitions of Kn is equivalent to partitioning an n-element
set into (unordered) sets of size 1 and 2, so it is unsurprising that this is not the rst time
this problem has arisen. Other interpretations can be found at [6].
3.2 Trees
Theorem 3.2. If H is a simple graph and v 2V(H) a pendant vertex, then B(H;Ft) =
2B(Hnv;Ft).
Proof. If p is a Ft-partition of Hnv then we can form a new partition by inserting v either
in a singleton set or in a block with its neighbor in H. This new partition will be a Ft-
partition of H, so from each Ft-partition of Hnv we can create two Ft-partitions of H.
These partitions will clearly be distinct. The reader can easily verify that all Ft-partitions
of H are obtained in this way.
Theorem 3.3. If G is a tree on n vertices, then B(G;Ft) = 2n 1.
17
Proof. Since G is a tree on n vertices, G can be built from a single vertex by sequentially
appending pendant vertices n 1 times. Since B(K1;Ft) = 1, B(G;Ft) = 2n 1.
3.3 Cycles
Theorem 3.4. If Cn is a cycle on n vertices (n 3), then B(Cn;Ft) = 2n (n+ 1).
Remark. We have opted to prove this using mathematical induction and 3.2. The in-
terested reader may notice a shorter, direct proof.
Proof. Observe that B(C3;Ft) = 4, so the claim is true for n = 3. To proceed inductively, the
following argument requires n 4. It can be easily veri ed that B(C4;Ft) = 11, so the state-
ment is true for a base case. Assume now that for some n2N, n> 4, B(Cn 1;Ft) = 2n 1 n.
We will count B(Cn;Ft) by constructing Ft-partitions of Cn from the Ft-partitions of
Cn 1. Let V(Cn) =f1;2;:::;ng and V(Cn 1) =f1;2;:::;n 1g. A Ft-partition p of Cn 1
will be called \good" if 1 and n 1 do not appear in the same block. Otherwise, the partition
is \bad".
In a good p, n 1 is either in a block with n 2 or it is in a block by itself. Likewise,
1 is either in a block with 2 or in a block by itself. Notice that, except for the partition
p = ff1;2;:::;n 1gg, every Ft-partition of Pn 1 (a path on n 1 vertices) is a good
Ft-partition of Cn 1, and every good partition is aFt-partition of Pn 1. Therefore, there are
B(Pn 1;Ft) 1 good Ft-partitions of Cn 1.
From each good Ft-partition of Cn 1, we can construct three Ft-partitions of Cn: n
can be inserted as a singleton block, n can be inserted into a block with n 1, and n can
be inserted into a block with 1. In good partitions, n 1 and 1 are in separate blocks,
18
so each choice produces a distinct partition. The partitions are Ft-partitions of Cn since a
block inducing a tree in Cn 1 also induces a tree in Cn, and keeping 1 and n 1 apart has
avoided inducing cycles. And so, good Ft-partitions produce a total of 3(B(Pn 1;Ft) 1)
Ft-partitions of Cn.
In a bad Ft-partition, 1 and n 1 appear in a block together, which means that block
induces two disjoint paths in Cn. However, by inserting n into such a block, since n is a
neighbor of both 1 and n 1 in Cn, the block now induces a tree. In Ft-partitions of Cn 1,
since 1 and n 1 either appear together in a block or in two separate blocks, we know that
there must be B(Cn 1;Ft) (B(Pn 1;Ft) 1) bad Ft-partitions of Cn 1. Each of these
yields exactly one Ft-partition of Cn, and each Ft-partition produced is distinct.
Recall the partition p. Being that it is not a Ft partition of Cn 1, it is neither good
nor bad. However, the block f1;2;:::;n 1g induces a tree in Cn and this block does not
appear in any good or bad partitions. The only way to construct from p a Ft-partition of
Cn is to form p[ffngg.
Every Ft-partition of Cn is counted in this way. This produces
B(Cn;Ft) = 3(B(Pn 1;Ft) 1) +B(Cn 1;Ft) (B(Pn 1;Ft) 1) + 1
= 2B(Pn 1;Ft) +B(Cn 1;Ft) 1
Since Pn 1 is a tree, B(Pn 1;Ft) = 2n 2. By the inductive step, B(Cn 1;Ft) = 2n 1 n,
so
B(Cn;Ft) = 2 2n 2 + 2n 1 n 1 = 2n (n+ 1):
19
Remark. Like 3.1, this theorem again provides new interpretation for an integer se-
quence. Other interpretations can be found at [6].
3.4 Combinations of Graphs
Theorem 3.5. If G is a graph with components H1 and H2, then B(G;Ft) = B(H1;Ft)B(H2;Ft)
Proof. If p is aFt-partition of H1 and q is aFt-partition of H2, then p[q is aFt-partition of
G. Conversely, if r is aFt-partition of G then each block of r contains vertices either strictly
from V(H1) or strictly from V(H2), so r may be viewed as the union of aFt-partition of H1
and a Ft-partition of H2.
Theorem 3.6. Suppose G is a graph with cut vertex v, and let H1;H2;:::;Hk be the
components of Gnv. De ne Ij to be the subgraph of G induced by V(Hj)[fvg. Then
B(G;Ft) = Qkj=1B(Ij;Ft)
Proof. For 1 j k, let pj denote a Ft-partition of Ij and bj denote the block of pj
containing vertex v. Let p =[kj=1pj and b =[kj=1bj. Form a new set collection q:
q = (pnfb1;b2;:::;bkg)[fbg
Observe that q is a Ft partition of G, and q is distinct for distinct choices of pj.
Every Ft-partition of G is obtained in this way. Let q be a Ft-partition of G. Denote
by b the block containing v. For each block c 6= b, there is a j 2f1;2;:::kg such that
c V(Hj). For each j, de ne bj =fu2b : u2V(Ij)gand pj =fc2q : c V(Hj)g[fbjg.
This yields a collection p1;p2;:::;pk of partitions of the vertex sets of I1;I2;:::;Ik. It is
20
straightforward that each pj is aFt-partition of Ij and that q arises from p1;p2;:::;pk in the
way described above.
Theorem 3.7. Suppose G is a connected graph with cut edge e, and let H1;H2 be the
components of Gne. Then B(G;Ft) = 2B(H1;Ft)B(H2;Ft).
Proof. If either end of e has degree 1, the result follows from 3.2. Assume that the ends of
e have degree larger than 1.
In a Ft-partition of G, the end points of e are either in a block together or they are in
separate blocks. TheFt-partitions of G where the end points of e are in separate blocks are
exactly theFt-partitions of Gne, so there are precisely B(H1;Ft)B(H2;Ft)Ft-partitions of
G of this type. The Ft-partitions of G where the end points of e appear in the same block
correspond to the Ft-partitions of the graph G e obtained by contracting the end points
v1;v2 of e to a single vertex w. Because e was a cut edge, w2V(G e) is a cut vertex. Let
J1 be the subgraph of G e induced byfwg[V(H1)nfv1g, and J2 be the subgraph of G e
induced by fwg[V(H2)nfv2g. Then B(G e;Ft) = B(J1;Ft)B(J2;Ft). But clearly J1 is
isomorphic to H1 and J2 to H2, so B(H1;Ft)B(H2;Ft) = B(J1;Ft)B(J2;Ft). This gives us
B(G;Ft) = B(Gne;Ft) +B(G e;Ft)
B(G;Ft) = 2B(H1;Ft)B(H2;Ft)
Questions Which familiesF of graphs with K12F share some or all of the properties
of Ft expressed in 3.2, 3.5, 3.6 or 3.7?
21
Chapter 4
The Bell Number of a Graph
With Respect to the Family Ff
Ff :=fF : F is a forest g
Many properties of Ft are lost by extending the family to forests, largely because the
family contains graphs which are not connected. For example, Theorem 3.2 does not hold for
the familyFf as it does forFt. To illustrate, let G be a K3 with a pendant vertex attached.
If 3.2 held, then
B(G;Ff) = 2B(K3;Ff)
B(K3;Ff) = 4, so we would nd B(G;Ff) = 8. However, we may nd B(G;Ff) quickly
by considering all (ordinary) partitions of the set V(G), of which there are b4 = 15, and elim-
inating those where a block induces K3. There are exactly 2 of those: the partition consisting
of V(G) and the partition where the pendant vertex is isolated and the vertices of K3 are in
a block. Clearly, B(G;Ff) = 136= 2B(G;Ff).
Ff is an incredibly permissive family. It excludes only blocks which induce non-acyclic
graphs. This makes it surprisingly easy to estabish Bell numbers, but less easy to identify
22
convenient properties.
For example, supppose G is any forest and jV(G)j = n. Then B(G;Ff) = bn because
absolutely every partition of V(G) is a Ff-partition. If G = Cn, then B(G;Ff) = bn 1
because only V(Cn) itself fails to be a Ff-partition. If G = Kn, then B(G;Ff) = B(G;Ft)
since it is still the case that the only valid partitions are those whose blocks consist only of
singletons and doubletons.
Theorem 4.1. Suppose G is a unicyclic graph with jV(G)j = n and the cycle has size k.
Then B(G;Ff) = bn bn k+1
Proof. The only partitions of V(G) which are not Ff-partitions are those in which some
block induces a non-acyclic subgraph. De ne G0 to be the graph obtained by identifying the
vertices of the k-cycle in G as the single vertex v. Then B(G0;Ff) is the number of partitions
of this graph, and each of these corresponds to a non-Ff-partition of G. Since G0 is a tree
on n k + 1 vertices, B(G0;Ff) = bn k+1. The result follows.
The idea of shrinking cycles to single vertices allows this theorem to generalize.
Theorem 4.2. Let G be a graph where jV(G)j= n and V(G) has pairwise disjoint subsets
W1;W2;:::;Wl such that the subgraph of G induced by Wi (1 i l) is a cycle, and suppose
that there is no other subset of V(G) whose induced subgraph is a cycle. Refer to these cycles
as Ck1;Ck2;:::;Ckl (where each ki is the cycle length), and let K =fk1;k2;:::;klg. Then
B(G;Ff) = bn +
lX
j=1
( 1)j
X
S K
jSj=j
bn (Px2S x)+j
Proof. Let Ai denote the collection of (ordinary) partitions p of V(G) such that some block
of p induces a subgraph containing Cki. Let [l] =f1;2;:::;lg. If we know the size ofSli=1Ai,
then we know how many partitions of V(G) are notFf-partitions of G. The size of a union
23
is well known to be
j
l[
i=1
Aij=
lX
j=1
( 1)j 1
X
R [l]
jRj=j
j
\
r2R
Arj
From here, consider the sizes of these di erent sets. The size of Ai, for any 1 i n, is
bn ki+1. Identify all vertices of Cki as a single vertex ci. Consider the (ordinary) partitions
of this new vertex set of size n ki+1. Each of these partitions corresponds to a partition of
V(G) in which Cki is in a block, and the subgraph of G induced by that block will contain Cki.
For i;j2[l];i6= j; the size of Ai\Aj can be found by shrinking the cycles Cki and Ckj
to single vertices ci and cj, respectively. The resulting graph has n ki kj + 2 vertices,
and there are bn ki kj+2 (ordinary) partitions of that vertex set.
For R [l], the size of Tr2RAr can be found by, for each r2R, shrinking the cycle Cr
to a single point cr. Then the number of partitions of that vertex set is bn (Pr2Rkr)+jRj.
24
Chapter 5
Families F and Their Properties
Throughout this chapter, F will denote a family of graphs containing K1.
We have seen the families F0 and Ft exhibit a variety of properties. We now turn our
attention to identifying other families that might share these properties.
5.0.1 Situations where B(G;F) is Maximum
Recall that for any familyF and any graph G withjV(G)j= n, B(G;F) bn. Equality
occurs when every induced subgraph of G is a member ofF. We also found that B(G;Ff) =
bjV(G)j for every G2Ff, but it was not the case that B(G;Ft) = bjV(G)j for every G2Ft.
Observe the following.
Theorem 5.1. If F is a family of graphs containing K1, then B(G;F) = bjV(G)j for all
G2F if and only if F is closed under the operation of taking induced subgraphs.
Proof. Suppose that B(G;F) = bjV(G)j for all G2F. Then for all G2F, every subgraph
of G is a member of F. So, F is closed under the operation of taking induced subgraphs.
Conversely, if F is closed under the operation of taking induced subgraphs, then for every
G2F, all of its induced subgraphs are members of F. Therefore, B(G;F) = bjV(G)j.
5.0.2 Families with a Multiplicative Property
Theorem 5.2. Let G be a graph with connected components H1;H2;:::;Hn. IfF is a family
of connected graphs, then B(G;F) = Qni=1B(Hi;F).
25
Proof. Recall the proof of 3.5 used only that each member of the family is a connected graph.
The proof here is similar.
5.0.3 Families with a Cut Vertex Property
In this section, G will be a graph with a cut vertex v such that Gnv has con-
nected components H1;H2;:::;Hk; respectively subgraphs I1;I2;:::;Ik of G are induced
by V(H1)[fvg;V(H2)[fvg;:::;V(Hk)[fvg, respectively. For the sake of brevity, we will
abridge this by referring to these special induced subgraphs as the v-induced subgraphs
of G.
Recall the proof of 3.6. We began with a graph G with cut vertex v and v-induced
subgraphs I1;I2;:::;Ik. From Ft-partitions p1;p2;:::;pk of I1;I2;:::;Ik (respectively), we
constructed a Ft-partition of G by de ning the block of q containing v to be the union of
the blocks of p1;p2;:::;pk containing v. There are two reasons this construction is valid in
proving 3.6. First, the construction of the block containing v in q requires that any time
X;Y 2Ft, if x2V(X) and y2V(Y) then the graph X Y obtained by identifying x = y is
also a member ofFt. Additionally, it is necessary that the graphs ofFt be connected as this
means the only block of q containing vertices of each of I1;I2;:::;Ik is the block containing
v. This observation of the essential properties of Ft used in the proof of 3.6 leads to the
following generalization.
A familyF of graphs containing K1 will be said to have the Cut Vertex Property if and
only if the statement obtained from 3.6 by replacing Ft by F is true.
Theorem 5.3. Suppose thatF is a family of connected graphs with the following properties.
(1) For every X;Y 2F, if x2V(X) and y2V(Y) then the graph X Y 2F where X Y
26
is the graph obtained by identifying the vertices x = y. (2) For any X2F with cut vertex x,
the v-induced subgraphs of X are each members of F. Then F has the Cut Vertex Property.
Proof. The proof proceeds essentially the same as the one for Ft.
Our interest will be in identifying families F with the Cut Vertex Property, but some
of them can be observed right now, thanks to 5.3.
fK1g, a trivial family
Ft, the family of all trees
Fc, the family of all connected graphs
The relationship fK1g Ft Fc gives rise to several questions.
Is there a family fK1g F Ft with this cut vertex property?
Are there familiesfK1g F Fc with the cut vertex property other than the family
Ft ?
What are the necessary and su cient conditions for the cut vertex property?
Theorem 5.4. If F is a family of graphs such that fK1g F Ft, then F does not have
the cut vertex property.
Proof. Let T 2FtnF be such that jV(T)j is minimal among all trees in FtnF.
Case 1. T 6= K2.
Observe that T has a cut vertex v. Consider B(T;F). Since T 2FtnF is of minimal order,
every tree of order smaller than T is in F. Therefore, the only subtree of T not in F is the
tree induced by V(T). Consequently, B(T;F[fTg) = B(T;Ft) since every subtree of T is
a member of F[fTg. If T has v-induced subgraphs I1;I2;:::;Ik then
27
B(T;F) = B(T;F[fTg) 1 =
kY
j=1
B(Ij;F) 16=
kY
j=1
B(Ij;F)
Thus we see that F does not have the cut vertex property.
Case 2. T = K2
By way of contradiction, assume that F does have the cut vertex property.
Let R be any tree with jV(R)j 3. Since R is a tree, it has at least 2 leafs. Let v
be a vertex adjacent to a leaf, and suppose it has m neighbor leafs. Let R have v-induced
subgraphs I1;I2;:::;Ik ordered so that jV(Ii)j jV(Ij)j whenever i j. Since there are m
neighbor leafs to v, the subgraphs I1;I2;:::;Im will all be isomorphic to K2. Since K2 =2F,
B(K2;F) = 1. As F has the cut vertex property,
B(R;F) =
kY
j=1
B(Ij;F) =
kY
j=m+1
B(Ij;F):
We see that each leaf contributes nothing to the Bell number with respect to F. Since
each of Im+1;Im+2;:::;Ik are trees larger than K2, the process applied to R can be iterated
on each of them. The iterations halt when all v-induced subgraphs are isomorphic to K2,
and this leads us to conclude B(R;F) = 1. But this tree R was arbitrary, so we see that the
Bell number of any tree with respect toF must be 1. That meansF =fK1g, but we began
by assuming fK1g F.
Corollary 5.1. If fK1g F Ft then F fails to have at least one of the properties (1)
and (2) in 5.3.
We have enough information to conclude that there are families fK1g F Fc with
the Cut Vertex Property other than the family Ft. For example, let G be a collection of
graphs (possibly nite), not all trees. Generate a larger collection G (containing K1) by
applying the operations suggested by 5.3 properties (1) and (2). That is, for any graphs
28
H;K2G and any h2V(H) and k2V(K), the graph obtained by identifying h and k as
a single vertex (\gluing" h and k) is also a member of the new collection. Moreover, if L is
a member of the new collection and v is a cut vertex of L, then the v-induced subgraphs of
L must be members of the new collection. And if L1 and L2 are both members of the new
collection, any graph obtained through a \gluing" manipulation (using only one vertex of
each graph) must also be in the new collection.
In this way, we can see that there will indeed be many more distinct families with the
Cut Vertex Property. For example, if fC4g is our initial collection, then applying the oper-
ations suggested by (1) and (2) will generate a family distinct from both Ft and the family
of all connected graphs.
Remark. The Cut Edge Property of Ft can be considered for generalization as well.
At the time of this writing, we will content ourselves with the discovery of the existence of
families with the Cut Vertex Property apart from fK1g;Ft; and Fc.
29
Bibliography
[1] H. Wilf, Generatingfunctionlogy, Academic Press Inc., 1994, pp. 26.
[2] B. Duncan and R. Peele, Bell and Stirling numbers for graphs, J. Integer Seq., 12 (2009),
Article 09.7.1
[3] B. Duncan, Bell and Stirling numbers for disjoint unions of graphs, Congressus Numer-
antium, 206 (2010), 215-217
[4] B. Duncan, Generalized Bell numbers for trees, submitted
[5] N.J.A. Sloane, J. H. Conway, The On-Line Encyclopedia of Integer Sequences,
http://oeis.org/A000085
[6] N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences,
http://oeis.org/A000295
[7] D. West, Graph Theory, Prentice Hall, 2001, pp. 220-221.
30