Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Hyperbolicity and chordality of a graph. | Hyperbolicity and chordality of a graph Yaokun Wu and Chengpeng Zhang Department of Mathematics Shanghai Jiao Tong University 800 Dongchuan Road Shanghai 200240 China Submitted Oct 27 2009 Accepted Feb 7 2011 Published Feb 21 2011 Mathematics Subject Classifications 05C05 05C12 05C35 05C62 05C75 Abstract Let G be a connected graph with the usual shortest-path metric d. The graph G is J-hyperbolic provided for any vertices x y u v in it the two larger of the three sums d u v d x y d u x d v y and d u y d v x differ 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-hyperbolic and that graph is not 2-hyperbolic if and only if it contains one of two special graphs as an isometric subgraph. For every k 4 we show that a k-chordal graph must be I k I . . I -21 . . -hyperbolic and there does exist a k-chordal graph which is not 2 -hyperbolic. Moreover we prove that a 5-chordal graph is 1 -hyperbolic if and only if it does not contain any of a list of five special graphs as an isometric subgraph. Keywords isometric subgraph metric tree-likeness. 1 Introduction Tree-likeness Trees are graphs with some very distinctive and fundamental properties and it is legitimate to ask to what degree those properties can be transferred to more general structures that are tree-like in some sense 28 p. 253 . Roughly speaking tree-likeness stands for something related to low dimensionality low complexity efficient information deduction from local to global information-lossless decomposition from global into simple pieces and nice shape for efficient implementation of divide-and-conquer strategy. For the very basic interconnection structures like a graph or a hypergraph tree-likeness is naturally reflected by the strength of interconnection namely its connectivity homotopy type or cyclicity acyclicity or just the degree of deviation from some characterizing conditions of a .
