
Citation 
 Permanent Link:
 http://digital.auraria.edu/AA00006085/00001
Material Information
 Title:
 Size bounds and Ramseytype numbers
 Creator:
 Weigand, John ( author. )
 Publication Date:
 2006
 Language:
 English
 Physical Description:
 1 electronic file (ix, 196 leaves) : ;
Subjects
 Subjects / Keywords:
 Ramsey numbers ( lcsh )
Graphic methods ( lcsh ) Graphic methods ( fast ) Ramsey numbers ( fast )
 Genre:
 bibliography ( marcgt )
theses ( marcgt ) nonfiction ( marcgt )
Notes
 Review:
 This dissertation is concerned with the problem of calculating size and independence ratio bounds for various classes of graphs, and then using them to establish upper bounds for Ramseytype numbers. Expressions that yield coefficients for multiple size bounds or multiple independence ratio bounds are of particular importance. For example, if we let m â‰¥ 3, and define [special characters omitted] then, with one exception for the case m = 5, any connected G âˆˆ [special characters omitted] (m) satisfies [special characters omitted] Given this size bound, we immediately obtain the independence ratio bound [special characters omitted] These results are sharpened for members of [special characters omitted] (6) and nonregular members of [special characters omitted] (7).
 Review:
 An infinite class of size bounds that hold for all graphs is introduced and the set of independence ratios for which each is tight is established. The more difficult problem of defining tight size bounds for classes of graphs that satisfy a forbidden clique constraint, but no maximum degree constraint is also studied. These bounds are shown to be closely related to an independence ratio bound introduced by Fajtlowicz.
 Thesis:
 Thesis (Ph.D.)University of Colorado at Denver and Health Sciences Center, 2006.
 Bibliography:
 Includes bibliographical references (leaves 195196).
 Statement of Responsibility:
 by John Weigand.
Record Information
 Source Institution:
 University of Colorado Denver
 Holding Location:
 Auraria Library
 Rights Management:
 All applicable rights reserved by the source institution and holding location.
 Resource Identifier:
 987858660 ( OCLC )
ocn987858660

Downloads 
This item has the following downloads:

Full Text 
SIZE BOUNDS AND RAMSEYTYPE NUMBERS
by
John Weigand
B.A. Mathematics, University of Colorado at Boulder, 1971 M.S. Computer Science, University of Colorado at Denver, 1996
A thesis submitted to the University of Colorado at Denver and Health Sciences Center in partial fulfillment of the requirements for the degree of Doctor of Philosophy Department of Mathematical Sciences
2006
This thesis for the Doctor of Philosophy degree by John Weigand has been approved
by
Michael Ferrara
Thomas Altman
Weigand, John (Ph.D., Applied Mathematics) Size Bounds and RamseyType Numbers Thesis directed by Professor Michael Jacobson
ABSTRACT
Staton introduced the notion of Ramseytype numbers in his 1977 dissertation. He defined the Ramseytype number Rd{rti, n) to be the smallest integer for which, any graph of order RD(m,n) and maximum degree at most D, must contain a clique of size m or an independent set of size n. Independence ratios, which are define by /i(G) = play an important role in this theory. If we let Qo (m) denote the class of Kmfree graphs of maximum degree at most D, then a lower bound for the independence ratios of such graphs yields an upper bound for the Ramseytype number Roirn^n). Lower bounds for independence ratios follow from size bounds of the form e (G) > av{G) + ba(G).
This dissertation is concerned with the problem of calculating size and independence ratio bounds for various classes of graphs, and then using them to establish upper bounds for Ramseytype numbers. Expressions that yield coefficients for multiple size bounds or multiple independence ratio bounds are of particular importance. For example, if we let m > 3, and define
am = 2 m 3 and bm
2,
111
then, with one exception for the case m = 5, any connected G Â£ Qm (m) satisfies
e (G) > amu(G) + bma(G).
Given this size bound, we immediately obtain the independence ratio bound
, 3m ~ 6 ^ 3m2 7 m + 4
These results are sharpened for members of Qe (6) and nonregular members of
&(7).
An infinite class of size bounds that hold for all graphs is introduced, and the set of independence ratios for which each is tight is established. The more difficult problem of defining tight size bounds for classes of graphs that satisfy a forbidden clique constraint, but no maximum degree constraint is also studied. These bounds are shown to be closely related to an independence ratio bound introduced by Fajtlowicz.
This abstract accurately represents the content of the candidates thesis. I recommend its publication.
Signed
IV
CONTENTS
Figures .......................................................... vii
Tables............................................................ ix
Chapter 1 2 3 4
1. Introduction...................................................... 1
1.1 Basic GraphTheoretic Definitions............................... 1
1.2 History of RamseyType Numbers.................................. 8
1.3 An Overview of This Dissertation............................... 18
2. Size Bounds...................................................... 21
2.1 Size Bounds and RamseyType Numbers............................ 21
2.2 Size Bound Operators .......................................... 23
2.3 Turan Bounds................................................... 26
2.4 Forbidden Cliques.............................................. 32
3. Proof Techniques................................................. 35
3.1 Specialized Definitions........................................ 35
3.2 Diagramming Conventions........................................ 38
3.3 The Induction Method........................................... 39
3.4 Graph Parameters............................................... 41
4. Two Elementary Size Bounds ...................................... 57
4.1 A Size Bound for Q (5)......................................... 57
4.2 A Size Bound for Q (3)......................................... 70
v
5. Size Bounds for Qm (m)............................................. 75
5.1 Introduction....................................................... 75
5.2 Establishment of Bounds for Qm (m) ................................ 76
5.3 Comparison to ABT.................................................. 96
5.4 The Origin of the Bound............................................ 96
6. K6Free Graphs..................................................... 99
6.1 A Size Bound for Qe (6) 99
6.2 A Size Bound for Q (6)............................................ 127
7. K7Free Graphs.................................................... 136
8. Butterflies....................................................... 173
8.1 3m 2A = 5....................................................... 173
8.2 An Associated Size Bound.........._............................. 175
8.3 3m 2A = 4....................................................... 179
9. Conclusions....................................................... 189
References............................................................ 195
vi
FIGURES
Figure
1.1 BUILDING BLOCKS FOR R3(3,n)CRITICAL GRAPHS .... 12
1.2 THE EXCEPTIONAL GRAPHS OF ABT ........................ 13
1.3 THE (4,3,5)CRITICAL GRAPH ........................... 15
2.1 RESTRICTED TURAN SIZE BOUND OPERATORS................. 31
3.1 F(x) = K8\E(K2,3)....................................... 39
4.1 6(G) = 4 ............................................... 60
4.2 6(G) = 5, a(F(x)) = 3 63
4.3 6(G) = 5, a(F(x)) = 2 64
4.4 THE UNIQUE (Qh (5), 9,2)MINGRAPH....................... 68
5.1 THE CRITICAL GRAPHS OF ABT ............................. 76
5.2 THE EXCEPTIONAL CONFIGURATION........................... 87
5.3 N [N [x}\ PRIOR TO MERGE.............................. 88
5.4 N [N [x]] AFTER MERGE................................. 90
5.5 THE 5REGULAR EXCEPTION .............................. 92
5.6 N [N [p0]] ........................................... 94
5.7 N [N [g0]] ........................................... 95
6.1 Pend (N [x] ;p) = 5 ................................. 104
6.2 M[p;x] = 3 .......................................... 105
6.3 M[p;x] = 5 .......................................... 106
vii
6.4 a(F(x)) = 3 .................................................... Ill
6.5 a(F(U)) = 3 .................................................... 112
6.6 F(x) = K7\E(K2,4)............................................... 120
6.7 G(ll,2)......................................................... 126
6.8 G(12,2)......................................................... 134
7.1 M(p,g0;*] = 8 142
7.2 M[pl9o;z] = 6, (W)= K6....................................... 143
7.3 (W)/ K6, w0^z0 ............................................ 147
7.4 (W) K6, w0 = z ............................................... 148
7.5 (R) = K5........................................................ 153
7.6 (R) K5........................................................ 155
7.7 N[g2,z] < 12................................................. 159
7.8 N [17]  = 38 163
7.9 G(13,2)......................................................... 170
vm
TABLES
Table
5.1 Comparison of (5m to ^ .
8.1 3m2A = 5, 1 < k < 5
8.2 3m 2A = 4, 1 < k < 4
96
177
187
IX
1. Introduction
This dissertation is concerned with the development of techniques for calculating bounds for Ramseytype numbers, but, before addressing this issue, it is necessary to present some background information.
This chapter is organized as follows: Notational conventions and basic graphtheoretic definitions are introduced in Section 1.1. Historical information pertaining to research in the area of Ramseytype numbers is presented in Section 1.2. This material includes the definition of Ramseytype numbers, citations of relevant research and an informal introduction to established proof techniques. Section 1.3 contains a chapter by chapter summary of the contents of this dissertation.
1.1 Basic GraphTheoretic Definitions
A collection of basic graph theoretic definitions is presented in this section. Most of this material can be found in an introductory graph theory text such as West [23], however several notational conventions that will be used throughout this paper, and a few specialized concepts are also introduced. In particular, the use of ordinal numbers as indexing sets is somewhat unusual. These numbers arise frequently in the following chapters, and in some of the definitions presented in this section, we begin with a brief explanation of their use.
We let N denote the set of nonnegative integers, and we assume that, in addition to being a number, each n N is also a set. Specifically, we let n = {0,1,..., n 1} (In particular, notice that 0 = 0). Given this convention,
1
we axe using N to denote the set of finite ordinal numbers. Since members of N are both numbers and sets, peculiarlooking notation such as the following may arise:
Uie5^i, 3ien, Vj G 2, {piYeri and {qj}3ek+2 (1.1)
No confusion should result as long as the reader remains aware that both arithmetic and settheoretic operations are applicable to ordinal numbers.
Sizes of finite sets play an important role in Ramsey theory. A set S is defined to be finite if there is a bijection between it and some n Â£ N. In this case, n is unique. Furthermore, we say that S has size n, and we write Sj = n. Since \S\ is a set, statements such as Q = {
We now present some basic graphtheoretic definitions. All of this material will be used in the following chapters.
Definition 1.1
1. A graph is defined to be an ordered pair G = (V (G), E(G)); where V (G) is a finite set and E(G) is a collection of two element subsets ofV (G).
2. V (G) is said to be the vertex set of G.
3. E(G) is said to be the edge set of G.
4 Q denotes the class of all graphs.
If {u, u} E(G), then we simply write uv G E(G), and we say that u and v are adjacent. In this case, we may also write u +> w, furthermore the edge uv is said to be incident with u and v, and u and v axe said to be its endpoints. If u and v are not adjacent, then we write />. It is possible for the vertex set of
2
a graph to be empty, in this case, we refer to the resulting graph as the empty graph.
Sizes of vertex and edge sets of graphs are of great importance in graph theory. Notation for these two graph parameters is introduced in the following:
Definition 1.2 Let G = (V (G), E(G)) G Q.
1. Define v(G) = V (G). i'(G) is said to be the order of G.
2. Define e(G) = E(G). e(G) is said to be the size of G.
If a pair of graphs have distinct vertex sets, then they are technically different objects, but it is convenient to blur this distinction and consider two graphs to be identical if they have the same structure. The notion of isomorphism allows us to make this statement precise.
Definition 1.3 Let Go, Gi G Q. Assume that there exists a bijection $ : V (Go) V (Gi) such that
In this dissertation, we do not distinguish between isomorphic graphs, so that we are actually considering structures of isomorphism classes of graphs.
Several of the proofs in the following chapters proceed by induction on order, with the empty graph providing the base case. The induction step involves splitting the graph into two pieces, and then considering the structures of the resulting pair of graphs. The notions of subgraphs and induced subgraphs, which we introduce next, are therefore of considerable importance.
3
Definition 1.4 Let G and H be graphs.
1. H is defined to be a subgraph of G, i/V (H) C V (G) and E(H) C E(G). In this case we write H < G.
2. Assume that H < G, and H ^ G. Then H is said to be a proper subgraph of G, and we write H < G.
3. Assume that H < G such that uv G E(H) if and only ifu,vEV (H) and uv G E(G). Then H is said to be an induced subgraph of G.
4 If S C V (G), then we define (S) to be the graph with vertex set V ((S')) = S and edge set E((5)) = {uv \ u,v G S and uv G E(G)}. (S) is said to be the subgraph of G induced by S.
5. Define the graph G = (V (G), E(G)) by V (G) = V (G) and uv G E(G) exactly when uv E(G). G is said to be the complement of G.
Definition 1.5 Let uGV (G) and U, W C V (G).
1. The open neighborhood of u is defined by N (u) = {n G V (G)  v }.
2. N (u) U {u} is defined to be the closed neighborhood of u. We denote this set by N [u].
3. The closed neighborhood ofU is defined by N [U] = UuS[/N [it].
4 Define NV (u) = N (u) fl W. Nw (u) is said to be the open neighborhood of u relative to W.
4
5. The set M \W\ U] = {u G N [W]  v Â£ N [[/]} is said to be the neighborhood difference ofW and U.
The first three items of Definition 1.5 introduce concepts that arise frequently in graphtheoretic literature, while the last two are required for the proofs presented in this paper. The structure introduced in (1.5.5) is always used within the context where l/CN [W]. Now that open neighborhoods have been defined, we may introduce the concept of degree.
Definition 1.6 Let G be a graph, u G V (G) and W C V (G).
1. The degree of u is defined by d(u) = N (it).
2. Define d(lT) = ^2ueW d (u). d(VD) is said to be the degree sum ofW.
3. Define 5(G) = min{d(u)  u 6 V (G)}. 5(G) is said to be the minimum degree ofG.
4 Define A(G) = max{ d(u)  u V (G)}. A(G) is said to be the maximum degree ofG.
5. If 5(G) = A(G) = m, then G is said to be mregular.
6. Define dw(u) = Nw (u)\. dw(w) is said to be the degree of u relative to W.
7. Define MinDeg(G) = {v G V (G)  d(v) = <5(G)}. MinDeg(G) is said to be the minimum degree vertex set for G.
8. Let D > 1, and define Qd {G G Q \ A(G) < D}.
5
The notions of independent sets and cliques are fundamental concepts in Ramsey theory, and independence ratios, as defined in (1.7.4), play a particularly important role in the study of Ramseytype numbers.
Definition 1.7 Let U CV (G).
1. U is defined to be independent ifu,v Â£ U ==> ujAd.
2. The set of independent subsets ifW (G) is denoted by Indep (G).
3. The independence number of G is defined to be the size of a maximum independent subset ofV (G). We denote this number by a(G).
q(G)
4 The independence ratio of G is defined by p(G) =
Definition 1.8 Let K CV (G).
u{GY
1. K is defined to be a clique if u,v E K
u v.
2. The set of cliques ofV (G) is denoted by Clique (G).
3. The clique number of G is defined to be the size of a maximum clique in V (G). We denote this number by lj(G).
4 Let m > 0. A graph G is said to be Kmfree if u{G) < m.
Cliques, as defined in 1.8.1, are sets of vertices. Given such a set K, we may also refer to (K) as a clique. When considering graphs to be cliques, it is clear that two such graphs are isomorphic exactly when they have the same order. Therefore no ambiguity arises if we let Km denote the clique of order m. Additionally, if a given graph is K3free, we may refer to it as being trianglefree.
6
Definition 1.9 Let G be a graph.
1. If it is possible to partition V (G) into a pair of disjoint, nonempty sets S and T such that S and T are independent, then G is said to be bipartite and S and T are referred to as partite sets.
2. Let G be a bipartite graph, and let S, T C V (G) as in (1), Assume that S = m, and \T\ = n. If s e S and t G T imply s t, then G is said to be a complete bipartite graph. In this case we write G = Km}Tl.
3. If one of the partite sets of a complete bipartite graph G has size one, then G is said to be a star. The member of that partite set is said to be the center of the star, and the members of the other partite sets are said to be its points. When both partite sets contain only one vertex, the star is said to be degenerate; in this case, either vertex may be designated the center.
If G is an incomplete bipartite graph, then the partite sets need not be unique, but they are always unique if G is complete. The next definition generalizes (1.9.1) and (1.9.2).
Definition 1.10 Let G be a graph and let r > 2.
1. If it is possible to partition V (G) into r pairwisedisjoint, nonempty sets {5j}ier such that each Si is independent, then G is said to be rpartite. In this case the sets Si are said to be partite sets.
2. If G is an rpartite graph with partite sets {5i}ier such that sl < whenever i,jÂ£r,i^ j, sl E Si and sJ (E Sj, then G is said to be a complete rpartite graph.
7
3. Let G by an rpartite graph satisfying the property that any two partite sets differ in size by at most one, then G is said to be a balanced rpartite graph.
4. If the rpartite graph G is both balanced and complete, then G is said to be a Turan graph. In the case that u(G) = n, we write G = Tnj.
In the next chapter, it will be shown that complements of Turan graphs play an important role in the theory of Ramseytype numbers.
Several of the theorems in the following chapters are applicable to graphs that axe Kmfree for a particular value of m. In addition, we may also require graphs to satisfy upper bounds on their maximum degree. The final definition of this section provides notation for these two classes of graphs.
Definition 1.11 Let D > 1, and let m> 2.
1. Let Q (m) denote the class of Kmfree graphs.
2. Define QD (m) = {G Q (m)  A(G) < D}.
The notation introduced in this definition will be used frequently in the next section when discussing results obtained by various authors, but it should be noted that none of them used this particular notation in their publications.
Additional graphtheoretic definitions that pertain specifically to the proof techniques used in this dissertation are introduced in Chapter 3.
1.2 History of RamseyType Numbers
This section contains a synopsis of the published work in the field of Ramseytype numbers. There are several classes of numbers that are called Ramseytype
8
numbers; in this paper, we only consider Ramseytype numbers as defined by Staton [21] in his 1977 dissertation. He introduced these numbers in order to gain some insight into the problem of determining Ramsey numbers.
It is appropriate to begin with a brief discussion of Ramseys original work. In 1930, he introduced a class of numbers that have come to bear his name. While he was able to establish the existence of these numbers via an elegant double induction argument, the calculation of their values has proved to be extremely difficult. There is a subclass of the Ramsey numbers, known as the classical, twocolor Ramsey numbers, which can be defined in graphtheoretic terms. These numbers constitute the simplest class of Ramsey numbers, yet only minimal progress has been made in this area. This class of Ramsey numbers can be informally defined in terms of edge colorings of graphs as follows:
Let If be a complete graph, and assign to each edge of K either the color blue or the color red. We say that a subset W of V (K) induces a blue (red) clique if each edge joining members of W is assigned the color blue (red). In this context, Ramseys Theorem states that, given any pair of positive integers m and n, there exists a smallest integer R(m,n) satisfying the property that, given any edge coloring of the complete graph K of order R(m,n), there exists either a subset of V (K) of size m that induces a blue clique or a subset of size n that induces a red clique. The number R(m, n) is said to be a Ramsey number.
There is an alternative formulation of this problem that is phrased in terms of clique and independence numbers: Given an edge coloring of the complete graph K, we define a subgraph G by letting V (G) = V (K) and taking the edge set of G to consist exactly of those edges of K that are assigned the color
9
blue. Now, if W C V (G), then W is a clique in G exactly when each edge that has both endpoints in W is assigned the color blue, and it is independent in G exactly when each edge that has both endpoints in W is assigned the color red. This observation allows us to formally define the classical, twocolor Ramsey numbers.
Definition 1.12 (Classical, TwoColor Ramsey Numbers) Let m,n> 2.
1. Define R(m, n) to be the smallest integer satisfying the property that, given a graph G of order R(m, n), either u>(G) > m or a(G) > n. The numbers R(m, n) are said to be the classical, twocolor Ramsey numbers.
2. Let G be a graph and assume that i/(G) = R(m,n) 1, u/(G) < m and a(G) < n. Then G is said to be (m,n)critical.
Tight lower bounds for Ramsey numbers are generally established by exhibiting critical graphs.
Since any graph either does or does not contain an edge, the numbers R(2, n) follow immediately, but numbers of the form R(3, n) are much more difficult to obtain. The problem of determining R(3,3) appeared on a Putnam exam several years ago. In 1955 Greenwood and Gleason [10] calculated R(3,4) = 9, i?(3,5) = 14, and R(4,4) = 18 and Kalbfleisch included the calculation of R(3,7) = 23 and R{3,9) = 36 in his 1966 dissertation. The Ramsey number R(4,5) = 25 was obtained by MacKay and Radziszowski [17] in 1995, and no new numbers have been computed since. Known bounds for several Ramsey numbers are included in Radziszowskis Dynamic Survey in the Electronic Journal of Combinatorics [18]. The large differences between known lower and upper bounds for relatively
10
small values of m and n, as reported in that survey, attest to the difficulty of this problem.
The classical, twocolor problem has proved to be so difficult that graph theorists have proposed several simplifications of it. In this dissertation, we utilize Statons notion of Ramseytype Numbers. He suggested restricting the problem size by imposing a maximum degree constraint, as specified in the following:
Definition 1.13 (RamseyType Numbers) Let D > 1, and let m,n> 2.
1. Define Ro(m,n) to be the smallest integer for which, given a graph G, v{G) Ro(m,n) and A(G) < D imply that either u>(G) > m or a(G) > n. RD(m,n) is said to be a Ramseytype number.
2. If G is a graph for which i/(G) = R(m,n) 1, A(G) < D, u>(G) < m and a(G) < n, then G is said to be (D,m,n)critical.
Staton additionally calculated the Ramseytype numbers R3(3,n), for all values of n. The existence of Ramsey numbers clearly ensures the existence of Ramseytype numbers. In fact we have
Ro{rn,n) < R(m,n), (1.2)
for any choices of D,m and n. While Definition 1.13 yields a simplification of the original problem, only a few classes of these numbers have been determined.
Independence ratios, which were introduced in Definition 1.7.4, played an important role in Statons work. He showed that, for each Geft (3),
MG) > y4 (1.3)
11
If we let n > 2, then (1.3) immediately implies
#3(3, n) <
H(nl)
+ 1.
(1.4)
Fajtlowicz, Statons advisor, had previously constructed the order14 graph depicted in Figure 1.1. Since this graph belongs to Q3 (3) and has independence five, the tightness of Statons independence ratio bound follows. Sums of these graphs yield critical graphs for numbers of the form (3, 5k + 1), and sums of these graphs plus one of the other graphs depicted in Figure 1.1 yield critical graphs for the remaining independence numbers.
I o
a 1 a = 2 a = 3
a = 4
These graphs are used in the construction of critical graphs for the Ramseytype numbers J23(3, n) as follows: If n 1 = 5k, then we form a sum consisting of k copies of the oraer14graph. Otherwise we form a sum consisting of copies of that graph and one copy of a graph of smaller independence.
Figure 1.1: BUILDING BLOCKS FOR R3(3, n)CRITICAL GRAPHS
12
An interesting result pertaining to independence ratios was published in 1976 by Albertson, Bollobas and Tucker [1]. They showed that, for each m > 3, any connected, mregular, Kmfree graph satisfies the bound p(G) > They also showed that, with the exception of the two graphs depicted in Figure 1.2, this bound is strict. We shall refer to these authors as ABT.
These two graphs are the unique connected, Kmfree graphs for which A = m and n = when m > 3. They were constructed by Albertson, Bollobas and Tucker in 1976.
This theorem does not yield upper bounds for the Ramseytype numbers Rm(m,n), because its hypothesis requires graphs to be regular. This problem was remedied in 1977 by Fajtliwicz [4], when he showed that any Kmfree graph G of maximum degree A satisfies the bound
G(8,2)
G(10,2)
Figure 1.2: THE EXCEPTIONAL GRAPHS OF ABT
(1.5)
He established the tightness of this bound for of graphs of independence two in
13
the case that
3m 2A = 5, (1.6)
and showed that it is not tight if
3m 2A > 5. (1.7)
He returned to this problem in 1984 [5], and showed that, given (1.6), independence two is necessary in order to attain tightness, and, in that case, it is yielded by a unique graph. He called these graphs butterflies because they have large chromatic numbers and possess a great deal of symmetry. In his review of this article, Albertson noted that Catlin used butterflies as counterexamples to Hayoss conjecture.
In his 1977 article, Fajtlowicz stated that the independence ratio bounds fj(G) > are not tight when m > 7, and, with the exception of the two graphs exhibited by ABT, the bounds for the cases m = 4,5 also fail to be tight.
In her 1982 dissertation. Fraughnaugh [6], another of Fajtlowiczs students, followed Staton by calculating all Ramseytype numbers i?4(3,n). She accomplished this by showing that the independence ratio of any member of C?4 (3) must be at least The graph illustrated in Figure 1.3 establishes tightness.
She derived this independence ratio bound by showing that any G E C/4 (3) satisfies the size bound
e (G) > 6v(G) 13a(G). (1.8)
Since each G Â£ Q4 (3) also satisfies
2v(G) > e (G), (1.9)
14
a = 4
This graph has order 13, independence 4 and is 4regular. Given that independence ratios of trianglefree graphs with A < 4 must be at least we see that this graph is (4,3,5)critical. Since R(3,5) = 14, this graph is also (3,5)critical.
Figure 1.3: THE (4,3,5)CRITICAL GRAPH
the desired result follows by juxtaposing the preceding two inequalities and solving for fi(G). Kreher and Radziszowski [19], unaware of Fraughnaughs work, showed that (1.8) holds for all K3free graphs regardless of maximum degree. The technique of deriving independence ratio bounds from size bounds has become the primary tool for computing upper bounds for Ramseytype numbers.
Staton did not use a size bound to obtain the A independence ratio bound, but Fraughnaugh [15] did use this technique in an alternate proof by showing that
e{G)>^u(G)Ua(G) (1.10)
for each member of G3 (3), and noting that
/(G)>e(G). (1.11)
Additional independence ratio bounds were obtained by Fraughnaugh in
15
collaboration with Locke. In 1994 [7], they proved that each G G Q3 (3) satisfies the bound
(1.12)
thereby showing that Statons bound is not tight when u(G) > 14. They used a variation of the size bound technique to establish (1.12) by defining
7(G) = e (G) 7u(G) + 15o(G) (1.13)
and showing that
7(G) > 2.
(1.14)
They also constructed graphs of arbitrarily large order that satisfy the bound
11 1
M 30 15i
(1.15)
and thereby obtained a tightness result.
In 1997, [9] they published the following three size bounds for I<4free graphs:
e (G) > u(G) a(G), (1.16)
e (G) > 2u(G) 3a(G) (1.17)
e(G) >bu(G)l2a(G). (1.18)
By imposing the additional constraint that graphs have maximum degree at most 4, they were able to use (1.18) to obtain an alternative proof that the independence ratio of any member of Q4 (4) must be at least They then used this bound to compute the Ramseytype numbers #4(4, n).
16
They also obtained some interesting tightness results for these size bounds. They showed that (1.16) is tight for independence ratios between  and 1, (1.17) is tight for independence ratios between  and  and (1.18) is tight for independence ratios between 1 and . This is the only publication in which the problem of multiple size bounds for a given class of graphs has been addressed.
Locke and Lou [16] considered the problem of finding independence ratio bounds for 4regular, K4free graphs. They showed that
a(G) >
7u(G) 4 26
(1.19)
holds for this class of graphs, and thereby obtained ^ as an asymptotic lower bound for independence ratios. They also established the existence of arbitrarily large graphs that satisfy the bound yy with equality. The tight independence ratio bound therefore lies in a narrow interval; there has been no subsequent improvement upon their results.
Griggs and Murphy [11] developed an efficient algorithm for finding independent sets of size at least yyi/(G) for any nonregular G 6 Q3 (3). This algorithm is easily modified to work for 3regular graphs by removing an edge before applying it. It is clear that removing edges from a graph, while holding order constant tends to increase the independence ratio, but they are the only authors who have attempted to quantify this relationship. They established relationships between the edge densities of graphs, which are defined by jj^, and independence ratios.
In his 1998 dissertation, Sandberg [20], a student of Griggs, introduced two bounds for independence numbers that follow from variations of size bounds.
17
He showed that each G G Q5 (5) satisfies
a(G) >
11 v(G)6
52
(1.20)
and obtained ^ as an independence ratio bound for members of Q5 (5), in agreement with ABT. He also showed that
a(G) >
81y(G) 1 45
(1.21)
for each G G Q6 (6). By applying this bound and using special arguments for graphs of order at most 17, he was able to obtain
MG) > ^ (122)
for each member of that class of graphs. He also exhibited a member of (6) that has order 11 and independence two.
In 2001 Heckman and Thomas [12] published a simple proof of Statons independence ratio bound, but there have been no new bounds published since Sandbergs 1998 dissertation.
1.3 An Overview of This Dissertation
This dissertation addresses some open problems pertaining to size and independence ratio bounds and their relationship to Ramseytype numbers. Some general results concerning size bounds are presented in Chapter 2. In that chapter, it is shown that the size bounds (1.16) and (1.17) introduced by Fraughnaugh and Locke [9] are the first two terms in an infinite sequence of size bounds, each of which holds for all graphs. This sequence is specified and the range of independence ratios for which each bound is tight is established.
18
The techniques for establishing size bounds that are used in this dissertation
are an abstraction and refinement of the techniques used by Praughnaugh and Locke [9]. Chapter 3 contains an informal overview of the proof inductive method used here, followed by a rigorous development of the proof techniques. This material provides the foundation upon which all of the theory developed in this dissertation is built. For this reason, it should be considered to be an integral part of that research.
Two size bounds are established in Chapter 4. These two proofs, which are relatively simple, and yet yield previously unpublished results, are intended to provide the reader with examples of how the proof techniques developed in Chapter 3 are used in this dissertation.
In Chapter 5, it is shown that, if m > 3, G Â£ Qm (m), G is connected and G is not the graph G'(K), 2), that is depicted in Figure 1.2, then
For each m > 7, this yields an improvement over the previous best known bound of A4 > and when m = 5, with the exception of G(10,2), we obtain ^ as an independence ratio bound. This is an improvement upon the previous best
specific to the class of graphs in question are used to establish this result.
Chapters 6 and 7 are devoted to the establishment of size bounds for K6 and Kyfree graphs, respectively.
In Chapter 8, issues pertaining to Fajtlowiczs Independence ratio bound
(1.23)
known bound of // > . Techniques from Chapter 3 and a symmetry argument
(1.24)
19
are addressed. His tightness results for the case 3m2 A = 5 are briefly reviewed and new results for the case 3m 2A = 4 are introduced.
Chapter 9 contains a summary of the material presented in this dissertation and suggestions for further study.
20
2. Size Bounds
In the first chapter, it was noted that upper bounds for Ramseytype numbers follow from lowrer bounds for independence ratios, which, in turn, follow from lower bounds for size. Formalizations of these relationships axe presented in Section 2.1. The traditional definition of size bounds, as presented in that section, is used throughout the following chapters but, when comparing two size bounds, as is done in this chapter, an alternative definition proves useful; this definition is presented in Section 2.2. An infinite collection of size bounds, each of which holds for all graphs, is constructed in Section 2.3, and it is shown that each is tight over a range of independence ratios. Issues pertaining to size bounds when a forbidden clique constraint is imposed are discussed in Section 2.4.
2.1 Size Bounds and RamseyType Numbers
We begin by offering a formal definition of size bounds.
Definition 2.1 LetC be a nonempty collection of graphs and assume that a > 0 and b < 0.
1. If e (G) > au(G) t ba(G) for each G Â£ C, then a and b are said to yield a size bound for C.
2. If there exists G Â£ C such that equality holds in (1), then the bound is said to hold tightly at G. In this case, the bound is also said to hold tightly at (i'(G),cy(G)) and at p(G).
21
The conditions a > 0 and b < 0, as imposed in the preceding definition, are reasonable because increasing order while keeping independence fixed yields an increase in size, while increasing independence while holding order fixed corresponds to a decrease in size. For the remainder of this chapter, we assume that a and b satisfy these properties.
The following pair of lemmas are used to convert size bounds into upper bounds for RamseyType numbers.
Lemma 2.2 Let a > 0, b < 0 and D > 1, Assume that G satisfies the inequality stated in Definition 2.1.1 and A(G) < D. Then
KG) =
<*(G) ot u(G) ~ b
(2.1)
Proof: It is clear that
Du(G)
2
> e(G).
(2,2)
Now combine Definitiori (2.1.1) and (2.2) and solve to obtain the desired inequality.
Lemma 2.3 Let a > 0, b < 0, m>3 and D, > 1, Assume that there exists a constant c such that
At(G)>c, VGefo(m). (2.3)
Then
i?c(m,n) < [c x(n 1)J + 1.
(2.4)
Proof: It is clear that a (D, m, n)critical graph can have order no larger than c1(n 1)J.
22
When using size bounds to compute upper bounds for Ramseytype numbers n), we fix D and m and establish a relationship between n and Rc(m, n). This is done by showing that a particular size bound holds for all members of Gd (m), applying Lemma 2.2, so as to obtain an independence ratio bound, and then applying Lemma 2.3.
2.2 Size Bound Operators
Consider the right hand side of the inequality stated in Definition 2.1.1. For fixed a and b we may view the sum
au(G) + ba(G) (2.5)
as a function that takes orders and independence numbers of graphs as parameters. When considering collections of size bounds, it is convenient to express each of them in terms of a function that incorporates (2.5) into its definition. Furthermore, when comparing two size bounds, it is instructive to extend the domains of these functions, so as to allow for noninteger arguments. For these two reasons we introduce the following:
Definition 2.4 Let a > 0 and b < 0.
1. Define BD = {(x, y) 6 R2  x, y > 0 and y < x}. BD is said to be the size bound domain.
2. Define Ba,b BD > M by Ba>b{x, y) = ax + by. Ba^ is said to be a size bound operator.
3. Given a graph G, the expression e(G) > Ba^(v(G),a(G)) is said to be a size inequality.
23
In this definition, we let x correspond to order and y to independence so that, given any graph G, we have (v(G),a(G)) G BD. For fixed a and b, it is clear that
e (G) > au(G) + ba{G) =* e (G) > BaJb(u(G), a(G)). (2.6)
Therefore we have a natural correspondence between size bounds and size bound operators. The following lemma, whose proof is obvious, yields a fundamental relationship between two size bounds.
Lemma 2.5 Let a,c> 0 and b, d < 0 such that b ^ d and let (x,y) G BD. Then
B.Ax,y) = Bc,d(x,y) <=> = ?rT (27)
x a b
Whenever two bounds are compared in this dissertation, it is always the case that a > c exactly when b < d and
0 c < !, (2.8)
so that yields an independence ratio. Therefore, if Ba b and Bca are equal exactly on a ray that is contained in BD, then one bound is dominant for independence ratios that lie above that ray and the other is dominant for independence ratios that lie below it.
When considering bounds of any sort, tightness is always an important issue. This problem is particularly difficult when considering size bounds, because, a complete answer to the question of tightness often requires the specification of an infinite collection of bounds (This problem will be addressed in the following two sections); furthermore there remain some unresolved issues that make the
24
problem of simply defining a precise notion of tightness difficult. The following definition yields three different formalizations of this concept.
Definition 2.6 Let C be a class of graphs and let Ba^ be a size bound operator
1. Then Ba,b is said to yield a Csize bound if the inequality specified in Definition 2.4.3 holds for each G E C.
2. Assume that Ba$ yields a Csize bound and let G E C. Then Ba^ is said to hold tightly at G if e(G) = Ba^(i'(G),a(G)). In this case we also say that Bat holds tightly at (u(G),ct(G)) and at p(G).
If a bound holds tightly at (n,r), then it also holds tightly at the independence ratio but it appears that it might not hold tightly at (no, ?"o) where ^ represents ^ reduced to lowest terms. Such situations will arise in the following chapters.
Fraughnaugh and Locke introduced the notions of (n, r)graphs and (n, r)mingraphs. The following definition associates those concepts with a particular class of graphs.
Definition 2.7 Let C be a collection of graphs, let n,r E N such that 0 < r < n and let G E Q such that i/(G) = n and a(G) = r.
1. Then G is said to be an (n, r)graph.
2. If G E C then G is said to be a (C,n,r)graph.
3. IfG is a (C, n, r)graph and e (G) < e (H) whenever H is a (C, n, r)graph, then said to be a (C,n,r)mingraph.
25
The characterization of mingraphs that correspond to particular sets of parameters is an important aspect of the study of Ramseytype numbers.
2.3 Turan Bounds
It was noted in Chapter 1 that Fraughnaugh and Locke [9] established the following pair of size bounds for K4free graphs:
e(G) > v{G) a{G) (2.9)
and
e (G) > 2v{G) 3a(G). (2.10)
Since their proofs did not utilize the fact that only K4free graphs were being considered, they actually showed that these bounds hold for all graphs. They additionally obtained an interesting pair of tightness results, which we combine into a single theorem.
Theorem 2.8 Let r,n E N be such that 0 < r < n.
1. There exists a (Q,n,r)graph G for which (2.9) holds with equality exactly
when
1 r < < 1 2 n (2.11)
and, in this case
(2r n) Ki + (n r) K2 (2.12)
yields the unique (Q,n,r)mingraph.
2. There exists a (Q, n, r)graph G for which (2.10) holds with equality exactly when
1 r 1 < < 3 n 2
(2.13)
26
and, in this case,
(3r n) K2 + (n 2r) K3 (214)
yields the unique (Q,n,r)mingraph.
This pair of size bounds suggests the following generalization. Establish the existence of an infinite sequence of size bound operators {Baitthat satisfies the following four conditions:
1. Baitbl and Ba^b2 correspond to (2.9) and (2.10) respectively.
2. e{G)>Bai 1.
3. There is a (Q, n, r)graph for which Bahbl holds tightly exactly when <
^ < j.
n l
4. In the case that ^ satisfies the preceding inequality, there exist constants c and d such that tightness is yielded uniquely by a graph of the form cKt + d K;+j.
The remainder of this section is devoted to establishing that such a sequence of operators does indeed exist. In order to simplify notation, we shall write Bi in place of Bai$r
It is clear that a graph is the unique (Q, n, r)mingraph exactly when its complement is the unique graph of order n and clique number r of maximum size; Turans theorem states that this graph is the Turan graph Ti7. (This graph was defined in (1.10.4). We immediately obtain the following corollary to Turans Theorem:
27
Corollary 2.9 Let n,r E N such that 0 < r < n. then Tnj is the unique {Q,n, r)mingraph.
In order to satisfy condition 4, it is necessary that Bi hold tightly at both K; and Kj+i. Therefore the coefficients ai and bi are computed by solving the following linear system.
We obtain
1 ( \ ai f(A
+ 1 b V1) l(T)j
ai = l and bi = ( T)
(2.15)
(2.16)
Notice that when l = 1 and 1 = 2, the resulting size bound operators correspond to the size bounds (2.9) and (2.10), respectively.
We now show that each Bi yields a C?size bound.
Lemma 2.10 Let l > 0 and assume that 0 < n < r. Then
r 1
and
Proof:
Bi(n,r) = Bw(n,r)
B,(n,r) > Bi+1(n,r)
n l + 1
r 1 >
n l + l
Bi(n, r) Bl+1(n, r) = ln ^ r ((1 + !)n ~ (^ r)
= 22) (T'
f (l + 2)(l + 1) (/ + l)/\
= n +  r
= n+ (1 + l)r.
(2.17)
(2.18)
(2.19)
(2.20)
(2.21)
(2.22)
28
Clearly
n + (/ + l)r > 0 (2.23)
n l + l
Now (2.17) follows by continuity.
Theorem 2.11 Let G Q and let l > 1. Then Bi yields a Qsize bound that is tight at the independence ratio Â£ exactly when
1 r 1
< < .
l+l n l
(2.24)
Furthermore, if (2.24) IS satisfied, then Tnr is the unique (G, n, r)mingraph. Proof: First assume that (2.24) holds and define c and d by
(2.25)
 \ ( \ / \
1 1 c = r
V l + l , \n/
We have
c = (l + 1 )r n and d n Ir. (2.26)
Both c and d are integers, both are nonnegative exactly when 77 < ^ < j and they cannot be simultaneously equal to zero. Therefore
G = cKi + dKi+i (2.27)
is a well defined graph. It is the complement of a Turan graph because it is a balanced sum of cliques. We also have
1'(G) = lc+ (l + 1 )d = l((l + l)r n) + (/ + l)(n Ir) = n (2.28)
and
a(G) = c + d = (/ + l)r n + n Ir = r. (2.29)
29
Therefore
G = T
nj'
(2.30)
The bound Bi was defined so as to hold tightly for both K* and K;+1. Since the order (size, independence number) of a sum of graphs equals the sum of the orders (sizes, independence numbers) of the terms, it follows that Bi holds tightly at Tn
Say
1 1 zTT7 '
1 r 1
< < .
k +1 n k
(2.31)
(2.32)
Now Bk(n,r) yields a tight bound at independence ratio and it follows by Lemma 2.10 and a simple induction that Bi provides a bound that is not tight for independence ratios outside of the interval [^, j].
If we restrict Bi to {(l,r)  0 < r < 1} and view it as a function of r, then we obtain a function that is evaluated at, independence ratios. Figure 2.1 illustrates the graphs of such restrictions of Bi, 1 < l < 5. Notice that Bi = Bi+i at independence ratio j and Bi dominates the other bounds over the interval [/+! jl figure provides insight into Lemma 2.10 and the induction used in the proof of the preceding theorem.
Definition 2.12 The size bound operators {Biare said to be Turan size bound operators, and we refer to the associated size bounds as Turan size bounds.
30
Size
This figure illustrates graphs of Turan bounds Bi, 1 < l < 5 restricted to the
set {(l,r)  0 < r < 1}. The graphs for each Bi and J3/+1 cross when the independence ratio is equal to j, with Bi dominating Bi+\ over smaller independence ratios. This figure provides an illustration of Theorem 2.11.
Figure 2.1: RESTRICTED TURAN SIZE BOUND OPERATORS
31
Let (x,y) G BD, and define
B(x, y) = max Bi(x, y). (2.33)
Then, for each G G
e(G) > Â£(j/(G),a(G)). (2.34)
In addition, for each (n, r) G BD, Tnj is the unique graph for which (2.34) holds with equality. We have constructed a tight, piecewiselinear lower bound for sizes of graphs. While this construction is relatively simple, the analogous problem, when a forbidden clique constraint is imposed, is extremely difficult.
2.4 Forbidden Cliques
We now consider the problem of obtaining size bounds for the class of Kmfree graphs. Fraughnaugh and Locke [9] showed that any K4free graph satisfies the size bound
e(G) > bu(G) 12a(G), (2.35)
and it is easily verified that (2.35) does not hold for all graphs (simply consider K4). They also showed that, if \ < Â£ <  and r is even, then there exists a member of f?4 (4) of order n and independence r that satisfies (2.35) with equality, but, in the case that r is odd, the issue of tightness remained open. The notion of tightness at the independence ratio Â£ does not necessarily coincide with the notion of tightness at (n, r), because, when r is odd we still obtain tightness at ^ from tightness at (2n, 2r). As long as this problem remains unresolved, it appears that a precise formulation of the notion of tightness, as it applies to size bounds, will remain a difficult problem.
32
We next show that, given m > 3, no size bound operator yields a tight size bound for arbitrarily small independence ratios as follows: Let a > 0 and b < 0 and consider the size bound operator Ba^. We have
Sa,6(l,0) = a, (2.36)
while
5/(1,0) = /, (2.37)
for each Turan operator Bi. Therefore for sufficiently small independence ratios, Ba b is strictly dominated by an infinite collection of Turan operators.
We wish to generalize the preceding construction, so as to obtain analogous results for Kmfree graphs. Notice that Turan operators satisfy the following three properties:
1. (Completeness) Given an independence ratio c, there exists a Turan operator that holds tightly at c.
2. (Minimality) If we exclude some 5/ from the consideration, then there exists an independence ratio c0 for which none of the remaining operators hold tightly.
3. (Uniqueness) No other collection of operators satisfies 1 and 2.
We have used the weaker notion of tightness in stating the preceding completeness condition, in order to gain generality. While this restriction is not required for Turan bounds, there are some results that suggest it may be necessary in other contexts.
33
Intuition suggests that, given m > 3, a unique, minimal complete sequence of size bound operators should exist for Q (m), but there is no proof that this is so. However, in the case that the sequence {Bap.bp}^ = does satisfy
these properties, we may define
Bm(x, y) = max B(x, y), (2.38)
so as to obtain a tight, piecewiselinear lower bound for sizes of graphs belonging to Q (m). In addition, if each B holds tightly exactly for independence ratios between x and y, then analysis of the following four sequences could yield valuable information about Ramseytype and Ramsey numbers.
K*}Â£i. mi = 100, W=P {yn~i (2.39)
Some of the authors cited in Chapter 1 have made contributions to this problem, and additional information is provided in this dissertation, but, at the present time, there is not enough data available to facilitate such an analytic approach.
34
3. Proof Techniques
It was shown in Chapter 2, that upper bounds for Ramseytype numbers follow from size bounds via applications of Lemmas 2.2 and 2.3. With the exception of Turan bounds, which were also presented in that chapter, all of the size bounds established in this dissertation follow by an induction on order. This chapter provides the foundation for those proofs.
The basic graphtheoretic material presented in Chapter 1 is augmented, in Section 3.1, by the introduction of a collection of definitions that pertain specifically to the proof techniques developed in this chapter. Diagramming conventions for illustrating graphs are introduced in Section 3.2. Section 3.3 contains an informal overview of the inductive method, and Section 3.4 contains a rigorous exposition of the associated proof techniques.
3.1 Specialized Definitions
There is a complex hierarchy of cases and subcases associated with the inductive proof, and several of the subcases are specified by stating that a particular graph G is obtained by excluding certain configurations of edges from a clique. In the next definition, we introduce some notational conventions that pertain to excluded edges. Since it is natural to associate such structures with the complement of G, overlines are included in the following notation in order to emphasize this relationship.
Definition 3.1 Let G G Q
35
1. Let u.v V (G) such that u ^ v and uv E(G). then uv is said to be a red edge of G. The set of all such edges is denoted by E(G).
2. Define e(G) = E(G). e(G) is said to be the complementary size of G.
3. Letu e V (G) andW C V(G). Define Nw () = {w W\u  iw ^ u}. Nw (u) w said to be the complementary open neighborhood of u relative to to W.
4. Let u V (G) and W C V (G). Define dw(u) = N^ (u)\, dw(u) is said to be the complementary degree of u relative to to W.
5. Let U,W C V (G). Define dw(U) = Ylucu dw(w). dw(U) is said to be the complementary degree sum ofU relative to to W.
Expression (3.1) provides an example of how a graph may be defined by excluding edges from a clique:
G= K8\E(K2i3). (3.1)
In this example, G is obtained by excluding the edges of the complete bipartite graph K2)3 from the clique K5
We may also define a graph H by excluding one or more vertices from a graph G as in the following example:
H = G\x. (3.2)
When excluding vertices from a graph, it is clearly necessary to also exclude incident edges, but when excluding edges, their endpoints are retained.
36
The notion of edges being incident with vertices has already been introduced, and it follows naturally that edges may also be incident with sets of vertices. The next definition yields some variations on this concept.
Definition 3.2 Let G E Q and let IT C V (G).
1. Define Inc (IT) = {uv E E(G)  {u,u} HIT ^ 0}. Inc (IT) is said to be the set of edges of G that are incident with IT.
2. Define Int (IT) = {uv E E(G)  u, v E IT}. Int (IT) is is said to be the set of edges of G that are internal to W.
3. Define Pend (IT) = {uv E E(G)  {u,u} nW = 1}. Pend (IT) is is said to be the set of edges of G that are pendant to IT.
4 Assum that U C IT, and define Pend (IT; U) = {ivv E Pend (IT)  {u, u} D U 7^ 0}. Pend(IT;C/) is said to be the set of edges of G that are pendant to W at U.
Definition 3.3 Let S C V (G). Define
DegEx (S) = d(S) 6(G) S. (3.3)
DegEx (S) is said to be the degree excess of S.
The importance of pendant edges and degree excess will be established in Section
5.
The following pair of graphs play fundamental roles in the induction described in Section 3.3.
37
Definition 3.4 Let G G Q, and let U G Indep(G). Define
1. F(V) = <(N [Â£/])>.
2. //{Â£/)= <(V(G)\N[E7])).
3.2 Diagramming Conventions
In expression (3.1) we defined a graph by specifying the edges that did not belong to it, and occasions shall arise in which it is instructive to illustrate a graph by exhibiting such edges. In particular, when depicting graphs induced by the closed neighborhood of some reV (G), only red edges are specified, and it is assumed that all unspecified edges belong to F(x). Such illustrations utilize home plate shaped boxes, such as the one depicted in Figure 3.1. We strictly adhere to the following conventions when using these boxes: Vertex x resides at the point of the box, members of N (x) reside to its right and nonedges between vertices are illustrated by dotted lines. For example, in the figure, d(x) = 7 and exactly six edges are excluded from F(x). Since these red edges are configured as the edges of the complete, bipartite graph K2,3, we see that F(x) possesses the structure specified in expression (3.1).
If a collection of vertices is not contained in a pentagonal box, and both solid and dotted lines occur in the illustration, then a solid line joining two vertices indicates that there is an edge joining them, a dotted line indicates the absence of such an edge and, if there remain pairs of vertices with neither type of edge joining them, then we make no assumption as to whether or not those vertices are adjacent. If only solid lines occur in a diagram, then, as is customary, it is
38
This graph is a clique from which the edges of a complete bipartite graph have been removed. It has size 22.
Figure 3.1: F(x) = K8\E(K2!3)
assumed that a pair of vertices is adjacent exactly when there is a line joining them.
3.3 The Induction Method
Size bound operators were studied in Chapter 2, but from this point forward, we shall only consider size bounds of the form
e (G) > au(G) + ba(G), (3.4)
where a > 0, b < 0 and G belongs to a given collection of graphs C, We shall additionally restrict our attention to the cases C = Q (m) and C = Qd (m) where m > 3 and D > 2. It is clear that the empty graph belongs to any such class, and, since the order, size and independence number of this graph are each equal to zero, it clearly satisfies (3.4) with equality.
The proof technique described in this section is an abstraction of a technique used by Fraughnaugh and Locke [9]. When utilizing this technique, we consider
39
a collection of graphs C and establish the size bound by induction on order. In all cases, the empty graph provides the base and the induction step is performed by removing the closed neighborhood of an independent set U, applying the induction hypothesis to H(U) and using information about the structure of F(U) to complete the induction (Recall that F(U) and H(U) were defined in Definition 3.4).
Since we always remove the closed neighborhood of U from G, any independent subset of V (H(U)) can be extended to an independent subset of V (G) by adjoining U. Therefore we obtain
a(G) >a(H(x)) + \U\. (3.5)
This inequality may be strict, but this does not create difficulties when applying the induction hypothesis because b < 0.
The induction step is partitioned into cases and subcases, with the value of 8(G) providing the coarsest partition. The initial choice for U is always a vertex of minimum degree x. We clearly have
Inc(N[*]) > ^ g (36)
As long as 8(G) < m 2, this yields sufficiently many edges to complete the induction, but this is not generally so when 8(G) > m 1. In such cases we have v(F(x)) > m and, since we assume graphs to be Kmfree, it follows that
a(F(x)) > 2. (3.7)
We next consider independent sets U, where U is in subset of N (x) of size at least two. In practice, fc is considerably larger than \a\, so that we gain an
40
advantage by increasing independence so long as the accompanying increase in size is not to great. We now identify a collection of independent sets, show that N [x] must contain at least one of them and then try to show that there are enough edges incident with the closed neighborhood of each so as to establish the induction. If this does not yield the bound, then it becomes necessary to consider additional choices for independent sets. Should this situation arise, the ensuing choices are context specific, and a complex hierarchy of subcases generally results.
3.4 Graph Parameters
In order to implement the induction described in the preceding section, it is necessary to quantify certain properties of graphs. In this section, we introduce five functions and a collection of lemmas that pertain to them. These functions and lemmas are used to manage the subcase hierarchy and establish individual subcases.
The following definition, hypothesis and conclusion provide a means of incorporating the induction hypothesis into the hypothesis of each of the lemmas proved in this section.
Definition 3.5 Let a > 0 and b < 0, and define ra,b to be the class of graphs that satisfy inequality (3.f).
Hypothesis 3.6 Let G be a graph and assume that H 6 ra!t whenever H < G Conclusion 3.7 G 6 Ta^
Each lemma proved in this section includes Hypothesis 3.6, along with some additional assumptions in its hypothesis and asserts that Conclusion 3.7 follows.
41
It is therefore permissible to assume that the hypothesis of any such lemma does not hold. Statements of such assumptions, which immediately follow related lemmas, are numbered in the same manner as definitions and theorems so that they can be easily referenced. By appealing to these assumptions, we are able to focus our attention on configurations that require specialized arguments. Throughout this dissertation, these assumptions axe not considered to be in force, unless they are explicitly invoked.
We assume that a and b satisfy the constraints specified in Definition 3.5. Each of the following functions incorporates a and b into its definition and, throughout this chapter, each function is subscripted by these variables to emphasize that dependency. But, when these functions are applied in the following chapters, these values will be clear from context, and the subscripts will be omitted.
We next introduce some notational conventions associated with function arguments. The variables 5, n and r all represent nonnegative integers and each function takes at least one of them as an argument in its definition. These functions are always used within the context where we are considering a graph G, and we have excluded the closed neighborhood of an independent set U from it. In this setting, these three variables correspond to 6(G), N [C7] and \U\, respectively. The reader might find it instructive to compare arguments, as used in function definitions, to arguments, as used in the lemmas that immediately follow them.
The first function specifies the number of edges incident with N [U] that suffice to establish (3.4), given that this bound it is satisfied by H(U).
42
Definition 3.8 Define
Ca,6(w,r) = \an + br]. (3.8)
Lemma 3.9 Assume Hypothesis 3.6, and let U G Indep(G). If
Inc(N[t/]) >C.i.{N[Â£/], [t/), (3.9)
then Conclusion 3.7 follows.
Proof: Assume the hypothesis of the lemma. Then
e (G) = e (H(U)) + Inc (N [C/]) (3.10)
> e (H(U)) + C.,6(N [U] I, \U\) (3.11)
> au{H{U)) + ba(H(U)) + aN [U]\ + b\U\ (3.12)
= av(G) + b(a(H(U)) + \U\) (3.13)
>au(G) + ba{G). (3.14)
Notice 3.14 holds because
a(G) > a(H(U)) + \U\ and b < 0. (3.15)
Lemma 3.9 clearly justifies the following:
Assumption 3.10 Suppose that Hypothesis 3.6 is in force, and U G Indep (G). Then
line(N[[/])
It is clear that
Inc(N[C7])>
5(G) N[t/]
(3.16)
(3.17)
43
This observation motivates the following:
Definition 3.11 Define
^a,b{S,n,r) =
n8
(3.18)
Lemma 3.12 Assume Hypothesis 3.6 and let U Indep(G). If
N[[7],t/) > 0,
(3.19)
then Conclusion 3.7 follows.
Proof: Apply (3.17) and Lemma 3.9.
Assumption 3.13 Assume Hypothesis 3.6 and let U G Indep(G). Then
fi>a,b(8(G), N [i/], C/) < 0. (3.20)
When ip(6(G), N [t/], u) < 0, we obtain a measure of the amount by which Lemma 3.12 fails to yield Conclusion 3.7. This value is used in Definition 3.23 and, in the event that U consists of a single vertex of minimum degree x, it also yields an upper bound for the values of e(F(x)) that require specialized argument.
Lemma 3.14 Assume Hypothesis 3.6 and let x G MinDeg(G). If
e(F(x)) > tl>aib(6{G),6(G) + l,l), (3.21)
then Conclusion 3.7 follows.
44
Proof: Assume the hypothesis and let v G N (x). Since d(x) = 6(G), v must have at least as many neighbors outside of N [x] as it has nonneighbors within that set. Therefore
Pend (N [x]) > 2e(F(x)). (3.22)
This implies
Inc (N [x]) = Int (N [x]) + Pend (N [x]) (3.23)
> (<5(G)+ ') e(F(x)) + 2S(F(x)) (3.24)
> (^ + ') MHG), S(G) + 1,1) (3.25)
= (aJS(G)J(G) + 1,1). (3.26)
Now apply Lemma 3.9.
Assumption 3.15 Assume Hypothesis 3.6 and let x MinDeg(G). Then
e (F(x)) < i/JaMG), 6(G) + 1,1). (3.27)
The next lemma and assumption allow us to exclude closed neighborhoods of x from consideration if there are a large number of edges pendant to them.
Lemma 3.16 Assume Hypothesis 3.6 and let x e MinDeg(G'). If
Pend (N [x]) > 2ipa,b(6(G),6(G) + 1,1) 1, (3.28)
then Conclusion 3.7 follows.
Proof: Assume the hypothesis. First notice that Assumption 3.15 implies e (F(x)) 1 > ^(<5(0,5(G) + 1,1). (3.29)
45
Now calculate
Inc (N [x]) = Pend (N [x]) + Int (N [x])) (3.30)
> 21>aMG),6{G) + 1,1) ~ 1 + e (F(x)) (3.31)
> 2,6(J(G),5(G) +1,1) + (
e(F(x)) 1 (3.32)
> 2*Pa,b(f>(G),5(G) + 1,1) + ( ^ )
+V\tWG),<5(G) + U) (3.33)
= (i(G2+ ') +1,1) (3.34)
= Ca(*(G),(G) + l,l). (3.35)
In this calculation, we have invoked Assumption 3.15 in order to obtain (3.33). Now apply Lemma 3.9.
Assumption 3.17 Assume Hypothesis 3.6 and let x G MinDeg(G). Then
Pend (N [x))\ < 2
If x G MinDeg(G), then
Inc(N[z])> (
and we may view /0(<5(G), 5(G) + 1,1) as a function of 5(G). When the hypothesis of the following lemma is satisfied, this function is monotonically decreasing and inequality (3.4) can then be established for several values of 5(G) in one step.
Lemma 3.18 Assume Hypothesis 3.6 and let k N such that
5(G) < k < a 1, (3.38)
46
and
4>a,b(k,k + 1,1) > 0. (3.39)
Then Conclusion 3.7 follows.
Proof: If 5(G) = k, then it suffices to apply Lemma 3.12. Next assume the hypothesis and let 6(G) = k 1. Upon removing ceiling operations we obtain
ipa,b(k, k + 1,1) = ^ ^ \a(k + 1) + 61 (3.40)
< ^ akab (3.41)
and
ipa,b(k l,k, 1)= Qj \ak + b] (3.42)
> (2) ~akb L (3.43)
Therefore
ifa,b(k 1, k, 1) ipa,b(k, k + 1,1) > akb 1 (3.44)
ak + a b'j (3.45)
= alk (3.46)
> 0. (3.47)
This establishes the lemma for the case 5(G) = A: 1. Now iteratively apply
the same argument using successively smaller values of 5(G).
There shall arise situations in which we evaluate 'ifa,b(&(G), N [f/], t/) where 5(G) and \U\ are held fixed and N [C7] is allowed to vary. In such instances, we are essentially evaluating a function of the single variable N[[/].
47
The next lemma asserts that this function is monotonically decreasing whenever its hypothesis is satisfied.
Lemma 3.19 Let k,r,n,8 Â£ N such that r
6 3
0Â£2 + 2'
(3.48)
Then
ipatb{8,k,r) > ij)a,b(8,n,r).
Proof: The conclusion of the lemma is clearly equivalent to
(3.49)
ipa,b(8(G),k,r) 4>a,b{8(G),n,r) > 0.
(3.50)
In order to establish this inequality we need only prove the lemma for the case k = n 1 and apply an induction.
It follows directly from the definitions of ipa^ and (a,6 that
il>a,b{8{G),n,r) = <
2
8(G)
n
\an + br]
n Han br
2 2
(3.51)
(3.52)
and
Ajb(8(G),n 1 ,r) =
>
(n 1)
6(G) 8(G)
2 U 2
\a(n 1) + hr]
an + a br 1.
(3.53)
(3.54)
The following calculation serves to complete the proof.
48
1>aj>(6{G)t n 1, r) ip(5(G), n, r) >
5(G) 5(G)
2 2 an + a hr 1
(5(G) 1 \ V 2 2 ) (3.55)
5(G) 3 2 2 (3.56)
(3.57)
In the esse that the hypothesis of Lemma 3.19 is satisfied, Definition 3.20 yields notation for the largest value of N [U]\ for which ip(5(G), N [f/], \U\) is nonnegative, and Assumption 3.22 allow us to restrict our attention to closed neighborhoods of larger size.
Definition 3.20 Assume that the hypothesis of Lemma 3.19 is satisfied. Define Va,b(5, r) = max {n  ipa,b(6, n, r) > 0} . (3.58)
Lemma 3.21 Assume Hypothesis 3.6, assume that
a > \ + \ (3.59)
and let U E Indep(G). If
N[C/]
then Conclusion 3.7 follows.
Proof: Assume the hypothesis and apply Lemmas 3.19 and 3.12.
Lemma 3.21 clearly justifies the following:
49
Assumption 3.22 Assume hypothesis 3.6, and assume that a >  +  and U Indep (G). Then
N[E7]>iK*(G),tf). (3.61)
Assumption 3.22 allows us to disregard cases where N[C/] is small. The next function allows us to disregard independent subsets of N [x] that have large closed neighborhoods.
It follows directly from the definition of ipaib that, should N [x] induce a clique, the existence of %l;a^(6(G),6(G) + 1,1) edges pendant to N [x] implies the existence of Â£a^(6(G) + 1,1) edges incident with N [x]. It therefore follows from Assumption 3.10 that
Pend (N [x]) < tpa,b(S{G), 6(G) + 1,1) 1 (3.62)
whenever (N [x]) = K,5+i. As we successively remove edges from F(x), we increment the number of pendant edges that are required in order to obtain Ca,b(6(G) + 1,1) incident edges. Lemma 3.24 allows us to assume the existence of a bound for the number of edges pendant to N [x] at a set S C N (x) that depends of the number of red edges that have both endpoints in that set. The utility of this lemma follows from the fact that the existence of red edges that have one or both endpoints in N [x] \S does not invalidate the bound. This is so because the degree of each v G N (x) is at least as large as that of x, so that v must have at least as many neighbors outside of N [x] as it has nonneighbors within that set. Therefore, for each red edge that has an endpoint in N (x) \ S, there must be at least one edge pendant to N [x] at that endpoint. We formalize this argument as follows:
50
Definition 3.23 Let k > 0. Define
pa,b(8, k) = max {0 Va,b(8, 8 + l,l)l + k} . (3.63)
Lemma 3.24 Assume that Hypothesis 3.6 holds. Let x MinDeg(G) and S C N (x). Let k > 0 such that
e ((S)) < k. (3.64)
If
Pend (N [x]; S)\ > Pajb(8{G)t k) + 1, (3.65)
then Conclusion 3.7 follows.
Proof: Assume the hypothesis. It is clear that we need only consider the case
ip(8(G),6(G) + 1,1) > 0. (3.66)
The hypothesis of this lemma involves red edges that have both endpoints in S, but we must also consider red edges that have at most one endpoint in S. We denote this set by T. Now we have
Int(N[x])> fi(G)+1) ~(k + \T\). (3.67)
Assume that v & N (x). We clearly have d(u) > d(x). Therefore
I Pend (N [x]; v) > dN[l](u), (3.68)
and it follows that
Pend (N [x] ;N [x] \ S)\ > T. (3.69)
51
Now (3.67) and (3.69) yield
Inc (N [a;]) = Int (N [x]) + Pend (N [x]) (3.70)
= Int (N [a;]) + Pend (N [x]; S)\
+ Pend(N[x];N[x] \S)\ (3.71)
> ('5(G)+ *) m + Pend (N [*]; S) + T (3.72)
>( ^ ) ) k + pa,b( +1 (3.73)
= ('5(G) +1)~ MUG) AG) + 1,1) (3.74)
= 0*(i(G) + l,l). (3.75)
Apply Lemma 3.9.
We are now able to assume the following pair of bounds:
Assumption 3.25 Assume Hypothesis 3.6. Let x Â£ MinDeg(G) and S C N (x). Assume that e(G(S)) < k. Then
1. Pend (N [x]; 5) < f.afi(5(G),k).
2. N [5] < N [x] + pQ,&(<5(G), k).
Lemma 3.24 justifies (1), and then (2) follows because
M [S',x]\ < Pend (N [x]; 5). (3.76)
While the existence of red edges that have endpoints outside of S does not affect the calculation of p, it may be necessary to consider the existence of additional red edges that have both end points in S. For example, if G is Kmfree and d(x) = 6(G) m, then it is necessary that N [x] contain either three
52
independent vertices or a disjoint pair of independent sets of size two. Now assume that a(F(x)) = 2 and {po,Qo}, {pi>9i} are independent and disjoint. If we let S = {po> Qo,Pu Qi}, then it is possible for there to be two additional red edges, say po9i and p\, q0, that have both endpoints in S without increasing independence. Therefore we may have as many as p(5(G),4) edges pendant to N [x] at S. Given this configuration, symmetry allows us to assume that
This situation will arise frequently on the following chapters.
There are two ways in which Lemma 3.12 can be sharpened. The calculation of VVb is based on the assumptions that all members of N [U] have degree equal to 5(G), and all edges incident with N [U] are internal. The notions of pendant edges and degree excess were introduced in Definitions 3.2 and 3.3, respectively. The following definition, lemma and assumption provide a means for exploiting these concepts.
Definition 3.26 Define
DegEx (N [[/]) + Pend (N [C/]) > Aa,6(*(G), N [U}\, \U\), (3.79)
(3.77)
Aa,b(<5, n, r) = 2fatb(n, r) 5n 1.
(3.78)
Lemma 3.27 Assume Hypothesis 3.6, and let U G Indep(G). If
then Conclusion 3.7 follows.
Proof: Assume the hypothesis. It follows from Definition 3.3 that
d(N [[/]) = 5n + DegEx (N [U])
(3.80)
53
and Definition 3.26 implies
in = 2C,t(N [t/], (7) X.MG), N [tr], t/) 1. (3.81)
Each pendant edge contributes one to d(N [[/]). Therefore
2 Int (N [u]) = 6n + DegEx (N [17]) Pend (N [Â£/]) (3.82)
= 2Ca,6(N [U], C/) AaMG), N [U]\, t/) 1
+DegEx (N [Â£/]) Pend (N [U])\. (3.83)
If we were to have
DegEx (N [Â£/]) + Pend (N [t/]) = AaJ>(6{G), N [U}\, C/), (3.84)
then it would follow that
2 Int (N [u]) = 2(Ca,fc(N [U)\, t/) Pend (N \U])\) 1, (3.85)
and this is clearly impossible. The hypothesis therefore allows us to assume that DegEx (N [Â£/]) + Pend(N [[/]) > Aa,b(5(G), N [U]\\,\U\) + 1. (3.86)
The following calculation utilizes
Inc (N [C/]) = Pend (N [t/]) + Int (N [U])\ (3.87)
= Pend (N [t/]) + + De^Ex ^ ~ Pend (N [^])l (3.88)
Notice that (3.88) implies (3.91) and (3.81) implies (3.93).
54
Ca,fc(N [U]\, C/) < Inc (N [f/]) 2Ca,t(N [t/], t/) < 2 Inc (N [U])\
(3.89)
(3.90)
=* 2Ca,fc(N [U]\,\U\)<2 Pend (N [U})\ + 5n
+DegEx (N [U]) Pend (N [U})\ (3.91)
^ 2Ca,fc(N [U],\U\) <5n + DegEx (N [[/]) + Pend (N [Â£7]) (3.92)
*= 2Ca,6(N [U\I,\U\) < 2Ca,fc(N [U]I, \U\) XaMG), IN [U}\,\U\)
1 + DegEx (N [Â£/]) + Pend (N [U])\ (3.93)
<= XaMG), N [U] , \U\) + 1 < DegEx (N [U]) + Pend (N [f/]). (3.94)
Now apply Lemma 3.9.
Assumption 3.28 Assume Hypothesis 3.6 and let U Â£ Indep(G). Then
DegEx (N [U]) + Pend (N [t/]) < Aa,6(5(G), N [t/],\U\). (3.95)
The following lemma, which generalizes a technique introduced by Fraughnaugh and Locke [9], provides for the establishment of size bounds when 5(G) is sufficiently large.
Lemma 3.29 Assume Hypothesis 3.6 and let x Â£ MinDeg(G). If 5(G) > a, then Conclusion 3.7 follows.
Proof: Assume the hypothesis of the lemma and consider the graph G\x.
55
Now
e(G)= d(x) + e{G\x) (3.96)
> g + o,{y(G 1) + bot(G \ x) (3.97)
> au(G) + ba{G). (3.98)
The last inequality follows because
a(G) > a(G\x) and b < 0. (3.99)
A considerable amount of technical information has been introduced in this chapter, and the reader has yet to be presented with an application; two relatively simple size bounds are proved in the next chapter.
56
4. Two Elementary Size Bounds
Two size bounds are established in this chapter. Each holds tightly for a clique and a graph that Fajtlowicz [5] calls a butterfly (The topics of butterflies and generalizations of these two bounds will be studied in Chapter 8). The more difficult of the two proofs is presented in Section 4.1. This proof includes explanations of how the techniques developed in Chapter 3 are being applied and how they generalize to other proofs. The proof presented in Section 4.2, which is quite simple, is written in the style of the proofs presented in the following chapters. These two proofs are included in order to present the reader with original results while providing relatively uncomplicated applications of the techniques developed in the preceding chapter..
4.1 A Size Bound for Q (5)
We show that any K5free graph G satisfies the size bound
e(G)>yi/(G)20a(G), (4.1)
and we show that this bound holds tightly for independence ratios between  and j. The imposition of the maximum degree constraint, A(G) < 5, then yields  as an independence ratio bound for Q5 (5). The size bound and tightness result are original results, while the independence ratio bound is well known. Theorem 4.1
1. Let G eG (5). Then e (G) > u(G) 20a(G).
Z
2. Let G Â£ G5 (5). Then n(G) >
5
57
1 f 1
3. Let Then there exists G E G5 (5) such that 1/(G) = n, a(G) =
0 n 4
~13 20T.
r, and e (G) =
4. Let k> 2. Then
Tn
i2s(5, /c) =
5(k 1) + 1 if k is odd
5(Jfc 1)
if k is even
(4.2)
Proof: We prove (1) by induction on v{G). This inequality clearly holds for the empty graph. Now assume that G is not empty and (1) holds for members of G (5) of smaller order. We consider cases determined by 5(G), and, in each case, we assume that x G MinDeg(G).
Case I (5 < 3)
We begin with the required parameter evaluations.
Parameter Evaluation 4.2
1. C(4,1) = j 4 20 = 6.
2. V(3,4,1) = Q C(4,l) = 0.
We first assume that 5(G) = 3, so that
N [x]  = 4. (4.3)
The induction hypothesis asserts that (1) holds for H(x), and Evaluation 4.2.1 asserts that the theorem follows for G if there are at least Â£(4,1) = 6 edges incident with N [x]. F(x) is of minimum size uniquely when it is equal to K4, and, in that case, we obtain exactly the required number of edges (This fact
58
is reflected in Evaluation 4.2.2). Therefore (1) follows when 8(G) = 3, by an application of Lemma 3.12. Now, since the hypothesis of Lemma 3.18 is satisfied, t/>(5(G), 8(G) + 1,1) is decreasing and it follows that (1) also holds for smaller values of 5(G).
Case II (8 = 4)
The following parameter evaluations are required for this case.
Parameter Evaluation 4.3
1. C(5,l) =
2. #1,5,1) =
3. p(4,1) = 3. I C(8,2) =
v8
 20 1 = 13.
C(5,l) = 3.
8 20 2 2
= 12.
5. #1,8,2)
48
C(8,2) = 4.
6. r/(4,2) = 8
Evaluation 4.3.1 asserts that (1) holds for G if there are at least 13 edges incident with N [x], but the minimum degree condition guarantees the existence of only 10 such edges (Notice that Evaluation 4.3.2 specifies this disparity). We must consider an alternative independent set. Since N [x] = 5, and G is K5free, N (x) must contain a pair of nonadjacent vertices p and q.
It follows from Evaluation 4.3.3 and Assumption 3.25 that
lNMI < N[x] +p(4,1) = 8. (4.4)
59
If this inequality does not hold, then we obtain at least Â£(5,1) = 13 edges incident with N [x] and (1) follows by Lemma 3.9.
Since 8(G) = 4 and {p,
0(4, n + 1,2) < 0(4, n, 2) 4, (4.5)
and we obtain positive valuations whenever N[p0,<7o] < 8, so that (1) again follows. Figure 4.1 illustrates this case.
The edge pq has been excluded from N [x]. Evaluation 4.3.3 and Assumption 3.25 yield M [p, q\ x] < 3. This implies N [p, g] < 8 = r/(4, 2).
Figure 4.1: 8(G) 4
In this example, the bound for N [p, g], as stated in (4.4), yields a positive valuation for 0(4, N [p, g], 2), and this case follows via an application of Lemma
60
3.19. But, in the following chapters, it will often occur that the bound for N [Â£/], as stated by the analogue of (4.4), yields a negative valuation for ip. In such cases, we determine the largest value of N [U]\ that yields a positive valuation for ip(5(G), N [t/], C/) (Recall that we denote this value rj(5(G), [/)), and apply
are no larger than r)(8(G), C/). Next, context specific arguments are used for each value of N [Â£/] between r](8(G), t/) + 1 and the upper bound specified by the analogue of (4.4). When making such arguments, it is clearly essential that 5(G) and \U\ remain fixed.
Case III (6 = 5)
We begin by calculating the required parameters.
Parameter Evaluation 4.4
Lemma 3.21. This serves to establish the size bound for values of N [C/] that
1. C(6,1) = 6 20 = 19.
3. p(5,3) = 0(5,6,1) 1 + 3 = 6.
I p(5,4) = ip(5,6,1) 1 + 4 = 7.
5. C(9,2) = 9202 =19.
6.1>{5,9,2)= ^ C(9,2) = 4.
7. 17(5,2) = 9.
8. C(14,3) = ^ 14 203 = 31.
Z
61
9. 0(5,14,3) =
514
2
C(14,3) = 4.
10. 77(5,3) = 14.
Since G is Ksfree, N (x) must contain either three independent vertices or a disjoint pair of independent sets, each of size two. This is so because the only remaining possibility is to exclude the edges of a star, and, because N [x] = 6, the members of N [x] other than the center would then induce K5. We next partition the current case based upon these two possibilities. Notice that we have offered an explanation as to why the next level of partitioning takes all possibilities into consideration. Since subcase hierarchies tend to become quite complex, the argument that all possible subcases have been considered consists of several such brief explanations, each offered immediately prior to the next partition of the current case or subcase.
Case III.A (a(F(x)) > 3)
Assume that U = {iq}ie3 (E Indep (F(x)). Assumption 3.25 and Evaluation
4.4.3 yield
N[C/]<N[x] + p(5,3) = 12. (4.6)
The bound now follows by Evaluation 4.4.10 and Lemma 3.21. Figure 4.2 illustrates the configuration under consideration.
It is possible that a(F(o;)) > 3, but there is no need to consider this eventuality. We simply let U consist of any three independent vertices in N (x), apply Assumption 3.25, so as to obtain a bound for the size of N [U], and then apply Lemma 3.21 as we have done here. When the function p was defined in Chapter 3, it was established that the existence of red edges that have one or
62
The set U is independent and has no more than p(3) = 6 neighbors outside of N [x]. This implies N [Z7] < 12 < 77(5,3).
Figure 4.2: 5(G) = 5, a(F(x)) = 3
both endpoints outside of the set S, as defined in that discussion, do not affect the valuation of p(5(G), e ((S))). Therefore we simply equate the set U, in this argument, with that S, and it follows that the existence of larger independent sets is irrelevant. In general, it suffices to determine the smallest value of \U\ for which Lemma 3.21 yields the size bound, and establish that case. The bound will then hold for independent sets of larger size.
Case III.B (a(F(x)) = 2)
Now assume that a(F(x)) = 2, and N (x) contains a disjoint pair of independent sets {po, 9o} and {pi,
It is possible to have two additional red edges with both endpoints in
63
{Po,9o.Pi.9i} without obtaining a(F(x)) = 3. Therefore we may assume that
Pend(N[x];po,g0.Pi.9i) < p(5,4) (4.7)
and, by symmetry,
Pend (N [a:] ;p0,9o) <
P(5,4)
2
Using Evaluation 4.4.4, we obtain
N[po,9o] < N[x] +
P( 5,4) 2
= 9 < 77(5,2).
(4.8)
(4.9)
Now apply Lemma 3.21 to complete the proof for this case. Figure 4.3 illustrates one possible configuration.
In this example, M [p09o! ^] < 3 so that N[p0,?o] < 9 = 77(5,2), and the bound follows.
Figure 4.3: 6(G) = 5, a(F(x)) = 2
The preceding argument is generally used when F(x) is configured as stated, but there is an alternate proof for this particular case. Evaluation 4.4.2 and
64
Assumption 3.15 yield
e(F(x)) < 3 < p(5,4)
(4.10)
as depicted in the figure, but, since this approach does not work in general, we simply invoke (4.7). Notice that, in the current situation, both techniques yield the same bound for N [p0) 9o]Case IV (S = 6)
We may again assume that N [x] contains either three independent vertices or a disjoint pair of independent sets, each of size two. Although neither of these conditions suffice to make G K5free, it is still necessary that one or the other of them hold. The following partition into subcases is based upon these two possibilities. Since this case is similar to Case III, additional explanations are omitted.
We first calculate the pertinent parameters.
Parameter Evaluation 4.5
1. C(7,l)= y 720 = 26.
3. p(6,3) = 0(6,7,1) 1+ 3 = 7.
I p(6,4) = V>(6,7,l)l + 4 = 8.
5. C(ll,2)= y 11202 = 32.
0
6. 11,2) = 11 C(11,2) = 1.
65
7. 77(6,2) = 11.
8. Â£(14,3) = ^14203 = 31.
z
9. t6,14,3) = iiiC(14,3) = ll.
10. 77(6,3) = 14.
Case IV.A (a(F(a:)) > 3)
Assume that U {uj}ie3 Indep (F(x)). Assumption 3.25 and Evaluation
4.5.3 imply
N [U}\ < N [x]\ + p(6,3) = 14 = 77(6,3). (4.11)
Now apply Lemma 3.21.
Case IV.B (a(F(x)) = 2)
We assume that a(F(x)) = 2, and let {poqo} and {pi,q\} be a pair of disjoint, independent subsets of N (z). Evaluation 4.5.4, Assumption 3.25 and a(F(x)) = 2 imply
Pend(N[z];p0,go,Pi,9i) < p(6,4) = 8, (4.12)
and symmetry allows us to assume that
N [po, 9o] < N [x] + 4 = 11 = 77(6,2). (4.13)
Lemma 3.21 yields the desired result.
Case V (8 > 7)
Apply Lemma 3.29.
In this case we have decreased order by one and size by at least [y], while we have not increased independence. Now the induction follows readily from the linearity of the bound.
66
This completes the proof of (1), and we immediately obtain (2) by an application of Lemma 2.2.
We next establish (3). Given positive integers n and r such that  ^
we wish to show that there exists a graph G Â£ Â£5 (5) of order n and independence r that satisfies (1) with equality. We consider two cases based on the parity of n.
Case I (n is even)
It is easily verified that K4 and G(10,2) both satisfy the (1) with equality. Therefore so must any sum of the form
c K4 t d G(10,2).
Let n = 2k, and solve the following linear system.
/. 0\ f \ / \
1 2  c r
d 10J w \2k)
This yields
c = 5r 2k and
d = k 2r.
Both numbers are integers, and we have
c> 0
1 r
 < 
5 n
and
It is now clear that
r 1
d > 0 <=$ < .
n 4
G = cK4 + dG(lO, 2)
(4.14)
(4.15)
(4.16)
(4.17)
(4.18)
(4.19)
67
is a well defined graph. G is a member of Go (5), and it is constructed so as to have the required order and independence. This establishes tightness when n is even.
Case II (n is odd)
The graph in Figure 4.4 has order nine, independence two and size 19. We refer to this graph as G(9,2). Since
we see that G(9,2) fails to satisfy (1) with equality, but exceeds this bound by only one half.
(4.20)
G(9,2)
Figure 4.4: THE UNIQUE (& (5), 9,2)MINGRAPH
Let n = 2k + 9 and define
G G(9,2) + cK4 + dG(10,2),
(4.21)
where
c = 5r 2k 10 and d k 2r + 4.
(4.22)
68
These coefficients are obtained by solving the following linear system:
u 2 ^ (\ C < o\ r 2
l4 10) [dj 2k )
In this case, we have used one copy of G(9,2) and applied the preceding construction to obtain a graph of order n 9 and independence r 2.
This establishes tightness for independence ratios between ^ and Tightness does not hold for independence ratios larger than  because the Turan bound, e(G) > 4v(G) 10o:(G)), is strictly dominant in that case. The problem of tightness remains open for independence ratios smaller than
Finally, we establish (4). As mentioned in Chapter 1, it follows from the combined work of ABT and Fajtlowicz that  yields a tight independence ratio bound for (5), and G(10, 2) is the unique connected graph for which tightness holds. Therefore all of the information required for the computation of the Ramseytype numbers /?5(5,n) was available at that time, but this result has never been published. These numbers are computed as follows:
First notice that Lemma 2.3 implies
R5(5,fc) < 5(fc1) + 1. (4.24)
We now consider the following two cases:
Case I (k is odd)
Let k = 2j 41. We have
i/0'G(10,2)) = 10j = 5(fcl) (4.25)
and
a(jG(lO,2)) = 2j
69
The existence of this critical graph establishes tightness.
Case II (k is even)
Let k = 2j. In order for (4.24) to hold with equality, a critical graph must have order 5(2j 1); furthermore, the independence ratio of each component must equal A. Since G(10,2) is the unique connected member of Q5 (5) that possesses the required independence ratio, the order of any critical graph must be a multiple of 10, and we obtain a contradiction. Therefore
R5(5,k) <5(kl). (4.27)
Now the graph
(jl)G(10,2)+ K4 (4.28)
is critical.
It will be shown in Chapter 5, that any connected G (5) other than
G(10,2) satisfies the size bound
e (G) < 7v(G) 22a(G) (4.29)
and the independence ratio bound
KG) > Ij. (4.30)
4.2 A Size Bound for Q (3)
Fraughnaugh and Locke [9] established the size bounds (1.16) and (1.17). Both hold for trianglefree graphs, and the first holds with equality for trianglefree graphs when independence ratios are assumed to be at least , but neither holds tightly for smaller independence ratios. In this section we establish a size
70
bound that holds for all trianglefree graphs, and, moreover, holds with equality for independence between  and Theorem 4.6
1. Let G Â£ G (3). Then e(G) > 3u(G) ba(G).
2. Let G Â£ G2 (3). Then n(G) >
5
2 r 1
3. Let Then there exists G Â£ G2 (3) such that r'(G) = n, a(G) =
5 n 2
r and e (G) = 3n 5r.
4 Let k > 2. Then (3, k) =
+ 1.
Proof:
We prove (1) by induction on order. The empty graph clearly provides the base for the induction. Now let G Â£ G2 (3) such that v(G) > 0, and assume that (1) holds for members of G2 (3) of smaller order. The proof is partitioned into cases based on minimum degree, and, in each case, we assume that x Â£ MinDeg(G).
Case I (6(G) < 1)
The following parameter evaluations are applicable:
Parameter Evaluation 4.7
1. C(2,l) = 325 = 1.
2. tf(l,2,l)= Q <(2,1) = 0.
71
Evaluation 4.7.2 and Lemma 3.12 yield the desired result when d(x) = 6(G) = 1, and it follows when d(x) = 6(G) = 0, because the hypothesis of Lemma 3.18 is satisfied.
Case II (5(G) = 2.)
The following parameter evaluations are used in the proof of this case. Parameter Evaluation 4.8
1. C(3,l) = 335 = 4
2. ^(2,3,1) = Q C(3,1) = 1.
3. p(2,l) = ^(2,3,1) 1 + 1 = 1.
4. Â£(4,2) = 3 4 52 = 2.
5. il>(2,4,2) = ~ C(4, 2) = 2.
It follows from Evaluation 4.8.2 that it does not suffice to simply consider N [x]. We let N (x) = {p, q}, and note that p / q because G is trianglefree. It follows from Evaluation 4.8.3 and Assumption 3.25 that
NMI<N[x]+p(2,1) = 4. (4.31)
Now (1) follows by Evaluation 4.8.5 and Lemma 3.12 win the case that equality holds in (4.31), and it holds for closed neighborhoods of smaller size by Lemma 3.19.
Case III (5(G) > 3)
Apply Lemma 3.29.
72
This completes the proof of (1). Now (2) follows upon the imposition of the maximum degree constraint, A(G) < 2, and an application of Lemma 2.2.
We next establish (3). Assume that r,nÂ£ N such that 1 < r < n and
2 r 1
5 n 2
(4.32)
Since K2 and C5 both satisfy (1) with equality, so must sums of these two graphs. Define c and d by
(4.33)
(\ ( \
c r
\d) KnJ
We obtain
c = 5r 2n and d = n 2r. Both c and d are integers, and they satisfy the inequalities
c > 0
and
r 2
>7,
n 5
d > 0
r 1
n 2
(4.34)
Therefore
G = c K2 + d C5
is a well defined graph, it clearly belongs to G G Â£2 (3), and we have
(4.35)
(4.36)
(4.37)
v(G) = n and a(G) = r (4.38)
by construction. This completes the proof of (3).
We finally consider (4). Since the bound yielded by (2) and Lemma 2.3 coincides with the right side of (4), it suffices to exhibit critical graphs.
73
Case I (k is odd)
Let k = 2j + 1. It is easily verified that j C5 is critical.
Case II (k is even)
Let k = 2j. Now A: 1 is odd and the floor operation in (4) has an effect. In this case (jf 1) C5 H K2 yields a critical graph.
74
5. Size Bounds for Qm (m)
Improvements upon existing independence ratio bounds for Qm (m) are established in this Chapter. Pertinent historical information from Chapter 1 is briefly reviewed in Section 5.1, and the bounds are established in Section 5.2. These results are compared to the bound ^ in Section 5.3. Section 5.4 contains an explanation of how the coefficients for these bounds were obtained.
5.1 Introduction
In 1976, Albertson, Bollobas and Tucker (ABT) [1] showed that, given m > 3, if G is a connected, Kmfree, mregular graph, then
MG) > (5.1)
m
They also showed that this inequality is strict unless G is one of the two graphs illustrated in Figure 5.1.
Two years later, Fajtlowicz [4] improved upon this result by showing that
MG)>
2
m 1 A(G)
(5.2)
for each G G Q (m). Upon assuming that A (G) < m, we immediately obtain an extension of (5.1) to nonregular graphs. In that same article he asserted that A does not yield a tight bound if m > 7 or if m G {4, 5} and the two graphs depicted in Figure 5.1 are excluded from consideration, but he did not offer a proof, nor did he state that specific bounds had been calculated.
75
G(8,2)
G(10,2)
These are the only two connected, members of Km, m > 3 for which the independence ratio bounds ^ hold with equality.
Figure 5.1: THE CRITICAL GRAPHS OF ABT
In the next section, it will be shown that, if m > 3, G e Qm (m), G is connected and G ^ C(10.2), then
If m = 3, or m = 6, then the resulting bounds are weaker then those obtained by Staton [21] and Sandberg [20], and, in the case that m 4, the bound y.>\
other than G(10,2) and, for each m > 7, (5.3) yields a bound that is strictly
5.2 Establishment of Bounds for Qm (m)
Each of the independence ratio bounds proved in this section follow from a size bound. We begin by defining the coefficients.
(5,3)
again follows. We obtain fi > jr as a bound for connected members of Q5 (5)
larger than Therefore the cases m = 5 and m > 7 are of primary interest.
76
Definition 5.1 Let m> 3 and define
3 7
am = 2m 3 and bm = m2 H2.
2 m
We next introduce the corresponding independence ratio bounds.
Definition 5.2 Let m > 3 and define
a 3m 6 m 3m2 7m + 4
(5.4)
(5.5)
Theorem 5.3 Let m > 3 and assume that that G is a connected member of Qm (m) and, in the case that m = 5, additionally assume that G ^ (7(10,2). Then
1. e ((7) > amu(G) + bma(G).
2. /r((7) > /5m.
3. Rm(m,n) <
3m2 7m + 4
(n 1)
+ 1.
3m 6
Proof: First notice that (2) follows from (1) by Lemma 2.2, and (3) follows from (2) by Lemma 2.3.
We prove (1) by induction on order. This inequality clearly holds for the empty graph, so let i'(G) > 0, and assume that it holds for all connected members of Qm (m) of smaller order. Throughout this proof we assume that x G MinDeg(G).
Case I (6
The case S = m 2 follows by Evaluation 5.4.2, and Lemma 3.12, and then Lemma 3.18 yields the result for smaller values of 6.
77
Parameter Evaluation 5.4
1.
C(m 1,1) = (m 1 )am + bm
3 7
= (m 1)(2 m 3) m2 + m 2
Z Z
3 7
= 2m2 5m + 3 m2 + m 2
Z Z
1 2 3
= mm + 1.
2 2
^(m 2,m 1,1) = ^2 J ~ ~ 1,1)
1 2 3 , (\ o 3
= _m + __m + i
= 0.
Case II (6 = m 1)
We begin with the standard calculations.
Parameter Evaluation 5.5
1.
Â£(m, 1) = amm + bh
3 7
= 2m2 3m m2 + m 2 z z
1 2 1
= m + m 2.
2 2
(5.6)
(5.7)
(5.8)
(5.9)
(5.10)
(5.11)
(5.12)
(5.13)
(5.14)
(5.15)
78
2.
0(m 1, m, 1) =  C(m, 1)
1 2 1 1 2 1
= mm m m + 2
2 2 2 2
= nn + 2 >0.
3. p(m 1,1) = ?/>(m 1, m, 1) = m 2.
Since N [x]  = m, N (x) must contain a pair of nonadjacent vertices, q. Assumption 3.25 and Evaluation 5.5.3 imply
M [p, q,x]\ < p{m 1,1) = m 2,
and therefore
N [p, 5] < N [x] + m 2 = 2m 2.
It is clear that
v{H(p,q)) = v(G) N [p, q] 
and
a(H(p,q))
The proof of this case now follows upon showing that
ip(m 1,2m 2,2) > 0,
and then applying Lemma 3.19. The following evaluations yield (5.24).
(5.16)
(5.17)
(5.18)
(5.19)
p and
(5.20)
(5.21)
(5.22)
(5.23)
(5.24)
79
Parameter Evaluation 5.6
1.
C(2m 2,2) = (2m 3)(2m 2) + 2
(_3m2 + lm 2
= 4m2 10 m + 6 3m2 + 7m 4
(5.25)
(5.26)
= m2 3m + 2.
(5.27)
ip(m 1,2m 2,2) = ^) ^2m 2,2) (5.28)
Z
= m2 2m + 1 (m2 3m + 2) (5.29)
= m 1. (5.30)
Case III (8 = m)
This final case is considerably more difficult than its predecessors. We first show that the bound follows unless the closed neighborhood of each vertex induces a particular graph, and then use a symmetry argument to establish that case.
Parameter Evaluation 5.7
1.
C(m +1,1) = am{rn + 1) + bm (5.31)
3 7 = (2m 3 )(m + 1) m2 + m 2 Z Z (5.32)
3 7 = 2m2 m 3 m2 + m 2 2 2 (5.33)
1 2 5 = m + m 5. (5.34)
80
2.
ip(m,m + 1,1) = ^ C(m + 1) 1) (535)
= ]m2 + ^m ^m2 + 5 (5.36)
Z Â£ L ~
= 2m + 5. (5.37)
3. p(m, 3) xp(m l,m, 1) 1 + 3 = 2m 3.
Jy. p(m, 4) = ^(m l,m, 1) 1 + 4 = 2m 2.
Since G is Kmfree, N [x] must contain an independent set of size three or a pair of disjoint independent sets, each of size two. This observation yields the following partition into subcases.
Case III.A (a(F(x)) > 3)
Let U E Indep(F(x)) and assume that \U\ = 3. Assumption 3.25 and Evaluation 5.7.3 imply
N [t/] < N [x] + p(m, 3) = 3m 2. (5.38)
We also have
a(H{U)) < a(G) 3. (5.39)
Now calculate
Parameter Evaluation 5.8
1.
C(3m 2,3) = (2m 3) (3m 2) +
m +m
9 21
= 6m2 13m + 6 m2 + m 6
3 (5.40)
(5.41)
(5.42)
81
2.
3m 2,3)
m(3ra 2)
C(3m2,3)
m mm + m
2 2 2
'3
2m '
(5.43)
(5.44)
(5.45)
An application of Lemma 3.21 now yields the bound for the current subcase. Case III.B (a(F(x)) = 2 and {po, 9o}, {Pi, 9i} G Indep(G))
We assume that a(F(x)) = 2 and {poi9o} and {pi,qi} are a disjoint pair of independent subsets of N (x). Now p0qo and p\q\ are red edges, each has both endpoints in {po> 9o>Pii <7i} and it is possible to have two additional red edges, say p0<7i and p\qo, without obtaining a(F(x)) 3. Assumption 3.25 and Evaluation 5.7.4 yield
Pend (N [x] ;po,9o,Pi>9i) < 2m 2, (5.46)
and, by symmetry, we may assume that
\M\p0,q0,x]\ < M [pi,g!;x]. (5.47)
Therefore Evaluation 5.7.4 implies
Nbo.?]<NN + ^i = 2m. (5.48)
We apply the induction hypothesis to H(po,qo) and consider the structure of F(p0,q0).
82
Parameter Evaluation 5.9
1.
((2m, 2) = (2m 3)2m +
(5.49)
= 4m2 6m 3m2 + 7m 4
(5.50)
= m2 + m 4.
(5.51)
2t77,2
tp(m,2m,2) =((2m, 2) (5.52)
2
= m2 m2 m + 4 (5.53)
= m + 4. (5.54)
Lemma 3.12 yields the desired result in the case that m < 4. Therefore we may assume
m > 5. (5.55)
The following evaluations and Lemma 3.19 suffice to establish the theorem in the case that N [p0,9o] < 2m 1.
Parameter Evaluation 5.10
1.
C(2m 1,2) = (2m 3)(2m 1) + + \m 2)2
= 4m2 8m + 3 3m2 + 7m 4
= m2 m 1.
(5.56)
(5.57)
(5.58)
83
2.
?/>(m, 2 m 1,2) =
m(2m 1)
C(2m 1,2)
m
m m+m + 1
m
T
+ i.
(5.59)
(5.60)
(5.61)
We have shown that the theorem follows unless,
NM > 2m
(5.62)
for each nonadjacent pair p,q E N (x). For each such pair we have
Pend (N [x] ;p, g) > M [p, 5; x] > m 1.
(5.63)
It now follows from (5.46) that
M[po,5o;z] = M[pi,gi;x] = m 1.
(5.64)
We introduce the following:
Notation 5.11
1. M [po;x] = k.
2. M [g0;x] = m 1 k = l.
3. k > l.
If inequality (5.46) were to be strict, then (5.63) would not hold for p0 and go, and the bound would follow. We therefore assume that
e((po,9o.Pi,9i)) = 4. (5.65)
84
In order for this equality to hold, it is necessary that
Pi *b Qji Vi,je 2. (5.66)
Now (5.64) and (5.66) imply
M[pi;x] = A: and M [gi; a:] = l. (5.67)
Next, mregularity implies
Pend(N[a:] ;v) = dN[x](v), VveN(i). (5.68)
Therefore we may denote the members of N (x) that are not neighbors of p0 by
Q = {<&Fefc, (569)
and the members of N (x) that are not neighbors of qo by
P={Pi}iel. (5.70)
It follows from a(F(x)) = 2 that P and Q induce cliques. Inequality (5.63) implies
Pend(9j;x) > Z, Vj k, (5.71)
and we obtain
e (N [x]) > kl. (5.72)
Recall that + 1,1) = 2m 5, so that Assumption 3.15 implies
e (F(x)) < 2m 6. (5.73)
We now consider possible values for k. Since po,Pi Â£ Pwe must have
k < m 3. (574)
85
If equality holds, then we obtain kl = 2m 6, and if not, then l < k implies
kl > 2m 6. Therefore, in order to satisfy (5.73), it is necessary that
k = m 3 and l = 2 (5.75)
The second equality implies
Mfe#;*] = 2, Vj e k. (5.76)
In order to satisfy all of these constraints it is necessary that
F(x)= Km+1\E(KU_3). (5.77)
This configuration is illustrated in Figure 5.2.
We introduce the following:
Definition 5.12 Let m > 5 and let G Qm (m). Then G is said to be exceptional if it is mregular, given any vertex x, F(x) has the structure specified in (5.77) and
M \pi',x] fl M [qj] x] = 0, Vi E k, Vj Z. (5.78)
If the closed neighborhood of some vertex were to induce a graph whose
structure is different from that specified in (5.77), then we could consider that vertex in place of x and the theorem would follow by the previous arguments. We have justified the following:
Assumption 5.13 G is exceptional.
The following notational conventions will be in effect for the remainder of the proof. Figure 5.3 illustrates this notation for the case m = 7.
86
This figure illustrates the structure of the graph induced by closed neighborhood of a vertex of an exceptional graph. The dotted lines indicate red edges, and there are exactly 2m 6 of them. These edges correspond to the edges of a complete bipartite graph with partite sets P = {pi}162 and Q = Po
and pi each have m 3 neighbors outside of N [x] and each qj has two such neighbors.
Figure 5.2: THE EXCEPTIONAL CONFIGURATION
Notation 5.14 Let x Â£ V (G) and consider the vertices ofG that are of distance two or less from it. Definition 5.12 implies the existence of a red K2,m_3 for F(x). We denote the partite set of size two by P = {pi}ie2 and the partite set of size l by Q = {<7j}j6i. Regularity implies that for each i Â£ 2 p* must have exactly l m 3 neighbors outside of N [x]; we denote each such set by Y{ = {Ps}86*Similarly, for each j Â£ l, we let Zj {zJt}te2 denote the neighbors of qj that do not reside in N [x]. Finally, we let r denote the unique member of N (x) that does not belong to either P or Q.
When we remove N [p0, qo] from G, we exclude 2m vertices and reduce the independence of the remaining graph by at least two. Therefore the bound
87
2/o y\ y\ y\ vl vl vl vl
This figure illustrates the configuration of vertices of distance two or less from x for an exceptional graph when m = 7. Clearly N (x) = {r,p0,pi, q0, 91, 92,93} and N[r] = N[x]. P = {po,Pi}, Q = {90,91,92,93}, both P and Q induce cliques and there are no edges joining members of these two sets. For each i G 2, Yi = {i/s}s64, and, for each / Â£ 4, Zi = {zlt}te2.
Figure 5.3: N [N [z]] PRIOR TO MERGE
follows by Evaluation 5.9.1 and Lemma 3.9 if
Inc (N [p0, 9o]) > m2 + m 4.
(5.79)
F(x) is obtained by excluding 2m 6 edges from Km+i and this yields
Pend (N [:r]) = 4m 12. (5.80)
Therefore
Inc (N [x])\ = ^ ^ + 2m 6 (5.81)
^m2 + \m + 2m 6 (5.82)
= \m2 + ^m 6. (5.83)
Z Z
88
Upon applying (5.79) and (5.83), we see that the theorem follows if
Inc (M [p0, <7o; z]) \Inc (N [x]) > m2 + m 4 f ^m2 + 6^ (5.84)
(5.85)
1 2 3
= 2m 2m + 2
Next, we let n denote the number of edges that have one endpoint in N [x] and the other in M [p0) Qo', %] Since G is mregular,
d(M \p0,q0]x]) = m(m 1).
(5.86)
Therefore
Inc(M[p0, m^n ^(5.87)
It follows immediately from Lemma 5.15, whose proof is deferred until the end of this section, that
n = 2m 2. (5.88)
Lemma 5.15 Assume that G is exceptional. Then
1. Yq = Y\, and this set induces Km_3.
2. There is a complete matching ofQ that satisfies the property, that whenever Qjo 7^ Qji i we have Zj0 = Zj1 if q]Q and qn are matched and Zj0 fl Zj, = 0 otherwise. Furthermore each Zj induces K2.
This lemma implies that each vertex of distance two from x is specified twice in Figure 5.3; Figure 5.4 illustrates the effect of merging them.
Since Q = m 3, and the members of Q are matched, we see that there are no exceptional graphs when m is even. This observation and (5.55) justify
89
Comparison of this figure to Figure 5.3 illustrates the effect of applying Lemma 5.15. Now each vertex of distance two from x has been specified only once, and each has two neighbors in N (2:). We have Yo = Y\ with the members of this set labeled as members of Y0. Also, in this example, Z0 = Z\ and Z2 = Z3.
Figure 5.4: N [N [x]] AFTER MERGE
the following:
m > 5 and m is odd. Substitution of (5.88) into (5.87) yields
(5.89)
Inc (M [po, q0; z]) \ Inc (N [x]) > ^ ^ ^ (5.90)
(m. f \
n 2) (5.91)
13
= 2m *2m + 1 (5.92)
and we fail to attain the required number of edges, as specified in (5.85), by one. But, this situation can arise only if
(M [p0,9o;z]) = Km_!. (5.93)
90
This is so because mregularity requires that, each member of M [p0, q0; x] has exactly as many neighbors outside of N [p0, Qo] as it has nonneighbors within M [po, qo] %] Therefore we obtain two edges pendant to N [p0, qo] at M [p0, g0; x] for each edge excluded from (M \p0, qo; x]). In this argument, we have used the facts that each v E M [p0.g0; x\ has two neighbors in N [x], and there are m 2 vertices in M [p0, qo]x] other then v.
We have now arrived at the point in the proof where the case m = 5 requires special treatment. We first assume that m ^ 5. By symmetry, Lemma 5.15 allows us to assume that Z0 = Z\ and therefore Z2 ^ Z0. We apply the preceding argument with q0 replaced by g2, and we see that the bound follows unless (M \po,q2]x\) = Km_i, so assume that this is so. This implies
{Po,Pi,y?, i 2/m4> zoi21.2o zi) C N (yg) (5.94)
and we obtain a contradiction to A(G) = m. The theorem now follows whenever m^5.
Next, we let m = 5, and examine how the preceding proof fails for this case. Let x G V (G) and consider the structure of F(x). This graph is depicted in Figure 5.5.
Using Notation 5.14, we have
N(x) = {r,po,Pi,9o,5i} (595)
By construction, N [r] = N [x], and the red edges of F(x) are exactly those that have one endpoint in {po,Pi} and the other in {<7o>9i} Both po and p\ have and y as neighbors that reside outside of N [x] and, similarly, qo and q\ have Zq and as neighbors that reside outside of N [x]. It has been established that
91

Full Text 

