The Metric Subgraphs,vertex Cuts And Homogeneously Traceable Graphs

This thesis studies several topics in graph theory including metric subgraphs,vertex cuts and homogeneously traceable graphs.The main results are as follows:1.We determine which cardinalities are possible for the center of a graph with given order and radius.2.We study the properties of almost self-centered graphs.We determine the maximum girth of an almost self-centered graph of order n,the maximum independence number of an almost self-centered graph of order n and radius r,and the minimum order of a k-regular almost self-centered graph.3.We study the properties of almost peripheral graphs.We determine the maximum size of an almost peripheral graph of order n,possible maximum degrees of an almost peripheral graph of order n,and the maximum number of vertices of maximum degree in an almost peripheral graph of order n with maximum degree n-4 which is the second largest possible.4.We determine possible orders for the existence of a graph whose metric subgraphs are either all paths,or all cycles,or all connected k-regular graphs.5.We study the minimum vertex cuts of k-connected graphs and improve a result proved by Chartrand and Lesniak in 1986.6.We prove that for every even integer n ≥ 10,there exists a cubic homogeneously traceable nonhamiltonian graph of order n,and for every integer p ≥ 18,there exists a 4-regular homogeneously traceable graph of order p.We also determine the possible maximum degrees of a homogeneously traceable nonhamiltonian graph with a given order.