Extremal Results On Cycles, Sizes And Vertex Types Of Graphs

This thesis studies several topics in graph theory including girth,circum?ference,the number of Hamilton cycles,sizes and vertex types.The main results are as follows.1.We prove that(1)the maximum girth of graphs with radius r and di?ameter d is 2r + 1 and(2)every graph of radius r and diameter d has a block whose diameter is at least 2r-d.The result(1)auswers a question of Ostrand posed in 1973 and makes the following classic result obvious:Every Moore graph is self-centered.The result(2)implies immediately the solution by Hrnciar to another problem of Ostrand.2.We prove that the minimum number of Hamilton cycles in a hamilto-nian threshold graph of order n is 2~[(n-3)/2]and this minimum number is attained uniquely by the graph with degree sequence n-1,n-1,n-2,...,[n/2],[n/2],...,3,2 of n-2 distinct degrees.3.We solve the following three problems posed by Beineke,Dunbar and Frick in 2005:(1)What is the smallest order of a detour-saturated graph of girth 4?(2)Let Pr be the graph obtained from the Petersen graph by splitting one of its vertices into three leaves.Is Pr the smallest graph among all triangle-free detour-saturated graphs with at least one cycle?(3)Does there exist a detour-saturated graph with finite girth bigger than 5?4.Zhan posed the following problem in 2007:Determine the maximum possible size of a digraph of order n in which there is at most one walk of length k with the same endpoints and characterize the extremal graphs.For the maximum size we solve the case 4 ? k?n—4 and for the extremal graphs we solve the case 5?k?n 2.5.We give a new and very short proof of Ore's classic theorem which deter-mines the maximum size of graphs with prescribed order and diameter.6.We solve the following three problems posed by Hedetniemi and Lewis in 2013:(1)What is the smallest order n of a graph having n-2 very typical vertices?(2)What is the smallest order n of a graph having n—2 typical vertices?(3)What is the smallest order of a pantypical graph?In fact we determine all the possible orders of the graphs in these three classes.