A broadcast is a function f that assigns an integer value to each vertex of a graph such that, for each v ∈ V , f (v) ≤ e (v), where e(v) is the eccentricity of v. The broadcast number of a graph is the minimum value of ∑ f(v) among all broadcasts f with the property that for each vertex u ∈ V, there exists some v ∈ V with f(v) > 0 such that d(υ,v) ≤ f(v). We present a new upper bound for the broadcast number of a graph in terms of its irredundance number and a new dual property of the broadcast number called the multipacking number of a graph. / Graduate

An edge ordering of a graph G = (V,E) is an injection f : E → R, where R denotes the set of real numbers. A path in G for which the edge ordering f increases along its edge sequence is called an f-ascent; an f-ascent is maximal if it is not contained in a longer f-ascent. The depression of G is the smallest integer k such that any edge ordering f has a maximal f-ascent of length at most k. In this dissertation we discuss various results relating to the depression of a graph. We determine a formula for the depression of the class of trees known as double spiders. A k-kernel of a graph G is a set of vertices U ⊆ V (G) such that for any edge ordering f of G there exists a maximal f-ascent of length at most k which neither starts nor ends in U. We study the concept of k-kernels and discuss related depression results, including an improved upper bound for the depression of trees. We include a characterization of the class of graphs with depression three and without adjacent vertices of degree three or higher, and also construct a large class of graphs with depression three which contains graphs with adjacent vertices of high degree. Lastly, we apply the concept of ascents to edge colourings using possibly fewer than |E(G)| colours (integers). We consider the problem of determining the minimum number of colours for which there exists an edge colouring such that the length of a shortest maximal path of edges with increasing colors has a given length. / Graduate / 0405

In the first part of this thesis we investigate the automorphism groups of regular trees. In the second part we look at the action of the automorphism group of a locally finite graph on the ends of the graph. The two part are not directly related but trees play a fundamental role in both parts. Let T_n be the regular tree of valency n. Put G := Aut(T_n) and let G₀ be the subgroup of G that is generated by the stabilisers of points. The main results of the first part are : Theorem 4.1 Suppose 3 ≤ n < N₀ and α ϵ T_n. Then G_α (the stabiliser of α in G) contains 2^2N0 subgroups of index less than 2^2N0. Theorem 4.2 Suppose 3 ≤ n < N₀ and H ≤ G with G : H |< 2^N0. Then H = G or H = G₀ or H fixes a point or H stabilises an edge. Theorem 4.3 Let n = N₀ and H ≤ G with | G : H |< 2^N0. Then H = G or H = G₀ or there is a finite subtree ϕ of T_n such that G(_ϕ) ≤ H ≤ G{_ϕ}. These are proved by finding a concrete description of the stabilisers of points in G, using wreath products, and also by making use of methods and results of Dixon, Neumann and Thomas [Bull. Lond. Math. Soc. 18, 580-586]. It is also shown how one is able to get short proofs of three earlier results about the automorphism groups of regular trees by using the methods used to prove these theorems. In their book Groups acting on graphs, Warren Dicks and M. J. Dunwoody [Cambridge University Press, 1989] developed a powerful technique to construct trees from graphs. An end of a graph is an equivalence class of half-lines in the graph, with two half-lines, L₁ and L₂, being equivalent if and only if we can find the third half-line that contains infinitely many vertices of both L₁ and L₂. In the second part we point out how one can, by using this technique, reduce questions about ends of graphs to questions about trees. This allows us both to prove several new results and also to give simple proofs of some known results concerning fixed points of group actions on the ends of a locally finite graph (see Chapter 10). An example of a new result is the classification of locally finite graphs with infinitely many ends, whose automorphism group acts transitively on the set of ends (Theorem 11.1).

The crossing number of a graph is the minimum number of pairwise crossings of edges among all planar drawings of the graph. A graph G is k-crossing critical if it has crossing number k and any proper subgraph of G has a crossing number less than k. The set of 1-crossing critical graphs is is determined by Kuratowski’s Theorem to be {K5, K3,3}. Work has been done to approach the problem of classifying all 2-crossing critical graphs. The graph V2n is a cycle on 2n vertices with n intersecting chords. The only remaining graphs to find in the classification of 2-crossing critical graphs are those that are 3-connected with a V8 minor but no V10 minor. This paper seeks to fill some of this gap by defining and completely describing a class of graphs called fully covered. In addition, we examine other ways in which graphs may be 2-crossing critical. This discussion classifies all known examples of 3-connected, 2-crossing critical graphs with a V8 minor but no V10 minor.

Research Doctorate - Doctor of Philosophy (PhD) / Interconnection networks form an important research area which has received much attention, both in theoretical research and in practice. Design of interconnection networks is much concerned with the topology of networks. The topology of a network is usually studied in terms of extremal graph theory. Consequently, from the extremal graph theory point of view, designing the topology of a network involves various extremal graph problems. One of these problems is the well-known fundamental problem called the degree/diameter problem, which is to determine the largest (in terms of the number of vertices) graphs or digraphs of given maximum degree and given diameter. General upper bounds, called Moore bounds, exist for the largest possible order of such graphs and digraphs of given maximum degree ∆ (respectively, out-degree d) and diameter D. However, quite a number of open problems regarding the degree/diameter problem do still exist. Some of these problems, such as constructing a Moore graph of degree ∆ = 57 and diameter D = 2, have been open for over 50 years. Another extremal graph problem regarding the design of the topology of a network is called the construction of EX graphs, which is to obtain graphs of the largest size (in terms of the number of edges), given order and forbidden cycle lengths. In this thesis, we obtain large graphs whose sizes either improve the lower bound of the size of EX graphs, or even reach the optimal value. We deal with designing the topology of a network, but we are also interested in the issue of fault tolerance of interconnection networks. This leads us to another extremal graph problem, that is, connectivity. In this thesis, we provide an overview of the current state of research in connectivity of graphs and digraphs. We also present our contributions to the connectivity of general regular graphs with small diameter, and the connectivity of EX graphs.

Thesis (Ph. D.)--Rutgers University, 2007. / "Graduate Program in Operations Research." Includes bibliographical references (p. 132-138).

Thesis (MSc)--University of Stellenbosch, 2007. / Bibliography. Also available via the Internet.

Thesis (Ph.D.)--Tufts University, 1988. / Submitted to the Dept. of Mathematics. Includes bibliographical references. Access restricted to members of the Tufts University community. Also available via the World Wide Web;

Thesis (Ph.D.)--Auburn University, 2007. / Abstract. Vita. Includes bibliographic references (ℓ.42-43)

Thesis (Ph.D.)--McMaster University (Canada), 1996. / Source: Dissertation Abstracts International, Volume: 58-06, Section: B, page: 3071. Adviser: G. Slade.