Some Extremal Problems In Graphs

In 1984, Naddef and Pulleyblank introduced the (0,l)-polytope and showed that if the graph G(P) of a (0,l)-polytope is bipartite graph, then G(P) is a hypercube; if G(P) is non-bipartite graph, then G(P) is hamilton connected. The class of (0,l)-polytope includes many well-known classes of polytope, such as: matching polytope, matorid basis polytope, stable set polytope and permutation polytope. Now, we study some extremal problems of perfect matching polytope.In the case that G has a perfect matching, extensive work has been done on the graph, in which the basic result is that in 1947, Tutte give a characterization of a graph G with perfect matchings. Recently, in order to investigate Tutte sets (or barrier) and extreme sets of graph G with perfect matchings, a new graph operator called the D-graph D(G) of graph G was introduced by Bauer, Broersma, Morgana, and Schmeichel, many interesting properties are obtained. The level of a graph G is defined to be the smallest integer k>0 such that D^k+1(G)≌D^k(G), taking D⁰(G)=G. We consider the level of some kinds of graphs, and give the characterization of the D-graph D(G) for some special graphs. The numeration of perfect matchings is also one of main focus of matching theory. We consider some classes of chain polygonal cacti and study their matchings and independent sets. Wiener index is an important topological index in theoretical chemistry, we study Wiener indices of some polyphenyl systems.This thesis consists of six chapters. In the first chapter, we introduce some definitions and notations about graphs and matching theory. Then we summarize recent main results and investigation progresses about matching theory, perfect matching graph, D-graph, and Wiener index. In the end of this chapter, the main results of this thesis are listed.In Chapter 2, we characterize the bipartite graphs whose graph of perfect matching polytope is bipartite graph. A sharp upper bound of the number of lines for this type of graphs is obtained, and the extremal graphs are constructed.In Chapter 3, we characterize the non-bipartite graphs G whose graph of perfect matching polytope is bipartite. A sharp upper bound of the number of lines for this type of graphs is obtained, and the extremal graphs are constructed.In Chapter 4, we first explore the level of elementary graphs, and show that for any non-bipartite elementary graph whose D²(G) is a complete graph. Moreover,we also give the characterization of the D-graph D(G) of the saturated graph G. Secondly, according to a canonical decomposition of arbitrary bipartite graphs, we give the explicit construction of the D-graph for bipartite graph with perfect matchings, and also give the characterization of a bipartite graph G with level(G)=0 and level{G)=1, respectively. Finally, we characterize the saturated graph G having unique perfect matching with level(G)=0 and give the sharp upper bound of the number of lines of the D-graph D(G) of the graphs with unique perfect matching.In Chapter 5, we consider some classes of chain polygonal cacti and study their matchings and independent sets . Explicit recurrences are derived for their matching and independence polynomials and the number of defect-d matchings for some values of d. We also determine the extremal chain polygonal cacti with respect to the number of matchings and of independent sets.In the last chapter, we determine the polyphenyl chains with minimum and maximum Wiener indices among all the polyphenyl chains with h hexagons, and the tree-like polyphenyl system with maximum Wiener index. Moreover, explicit formulae for Wiener indices of extremal polyphenyl chains are obtained.