Star-Uniform Graphs And Connectivity Of Cages

Extremal graph theory, in its strictest sense, is a branch of graph theory developed and loved by Hungarians. Its study, as a subject in its own right, was initiated by Turan in 1940, and the main exponent has been Paul Erdos who has virtually created the subject. In extremal graph theory one is interested in the relations between the various graph invariants, such as order, size, connectivity, minimum degree, diameter and so on. We are also interested in the values of these invariants which ensure that the graph has certain properties. Often, given a property (?) and an invariantμfor a class (?) of graphs, we wish to determine the least value m for which every graph G in (?) withμ(G)＞m has property (?). Those graphs G in (?) without the property (?) and withμ(G) = m are called the extremal graphs for the problem. For instance, every graph of order n and size at least n contains a cycle, and the extremal graphs are the trees of order n. Having said this, I emphasize that in this thesis extremal graph theory is interpreted in a broader sense, including in its scope various structural results.Two extremal problems are studied in this thesis. One is star-uniform graphs, and the other one is about cages. Some basic definitions and the history of the related topics are introduced in Chapter 1.A star is a tree isomorphic to K_1,nfor some n≥1. A star-factor of a graph G is a spanning subgraph of G such that each component of which is a star. An edge-weighting of G is a function w : E(G)→N⁺, where N⁺ is the set of all positive integers. For a subgraph H, the weight of H underωis the sum of all the weight values for edges belonging to H, i.e.,ω(H)=∑_e∈E(H)ω(e). A graph G is called star-uniform if there is an edge-weightingωof G such that every star-factor of G has the same weight underω. Hartnell and Rall [24] posed an open problem to characterize all the star-uniform graphs. In Chapter 2, we use Gallai-Edmonds Matching Structure Theorem to give a complete characterization of all the star-uniform graphs under a constant edge-weighting function. Subsequently, all the star-uniform graphs of girth at least five are characterized under a general edge-weighting function. A k-regular graph with girth g is called a (k, g)-graph. A (k, g)-cage is a (k, g)-graph with the fewest number of vertices for given k and g. Cage problem is one of the oldest problems in graph theory. Cages were introduced by Tutte [52] in 1947, and have been extensively studied. However, this topic is very challenging; even to estimate the bounds on the order of a (k, g)-cage is very difficult for k≥3 and g≥5. Recently, many researchers pay attention to the structural properties of cages, for instance, connectivity. In particular, it has been conjectured [Fu, Huang and Rodger, Connectivity of cages, J. Graph Theory, 24(1997), 187-191] that all (k, g)-cages are k-connected for every k≥3. In Chapter 3, based on known results, we will proceed to work on the connectivity of cages.