On The Center And Longest Paths Of Chordal Graphs

Chordal graphs are of great importance,since several problems that are hard on other classes of graphs,such as graph coloring,may be solved in polynomial time when the input is chordal.A classical result about the center of chordal graphs is that the diameter of the center of a chordal graph does not exceed 3.For all possible diameter-radius pairs of the center,we determine all chordal graphs with the minimum order.In 1966,Gallai asked whether all longest paths in a connected graph share a common vertex.While the answer is already known to be negative for graphs in general,there are some particular graph classes which have a positive answer to Gallai's question.A motivating question for present research is that whether Gallai's question has positive answer for chordal graphs.We prove that the intersection of all longest paths is not empty for connected chordal graphs of order less than or equal to 10.