Chordality And Hyperbolicity Of A Graph

Graph theory is an important component of discrete mathematics. Studyingthe structural properties of a graph can help us have a more clear understanding ofthe internal structure and also have some help to solve the computer and biologicalissues, as well as other disciplines. In the many structural properties of a graph, thispaper mainly discusses the relationship between the chordality and hyperbolicityof a graph.Let G be a connected graph with the usual shortest-path metric d. The graphG isδ-hyperbolic provided for any vertices x,y,u,v in it, the two larger of the threesums d(u,v) + d(x,y),d(u,x) + d(v,y) and d(u,y) + d(v,x) di?er by at most 2δ.The graph G is k-chordal provided it has no induced cycle of length greater than k.Brinkmann, Koolen and Moulton find that every 3-chordal graph is 1-hyperbolicand is not 21-hyperbolic if and only if it contains one of two special graphs as anisometric subgraph. For every k≥4, we show that a k-chordal graph must be -hyperbolic and there does exist a k-chordal graph which is not-hyperbolic.Moreover, we prove that a 5-chordal graph is 12-hyperbolic if and only if it does notcontain any of a list of six special graphs (See Fig. 2.2) as an isometric subgraph.To further study the hyperbolicity of a graph, we will briefly introduce the relationsbetween the graph center and the hyperbolicity.Chapter 1 brie?y introduces the real-life applications of the tree structure.And describes the research background and current situations of the chordalityand hyperbolicity of a graph.Chapter 2 gives the main results and their corollaries about the chordality andhyperbolicity of a graph in the paper.Chapter 3 discusses the tree-likeness parameters that are related to the hyper-bolicity.Chapter 4 presents the proof of the main results in Chapter 2. In the proof, without loss of generality, we firstly give two assumptions and then make the pro-found structural analysis for the geodesic quadrangle Q(x,u,y,v) that satisfies theminimum condition. Finally, we complete the proof and get all the extreme graphsthat satisfy the conditions that 5-chordal graphs are 1/2-hyperbolic.Chapter 5 proposes some problem related to the center of a graph and sum-marizes conclusions of the relationship between the center and the hyperbolicity.