Nonempty intersection of longest paths in series-parallel graphs

详细信息    查看全文

• 作者：Guantao Chen^a ; ^{gchen@gsu.edu} ; Julia Ehrenmü ; ller^b ; ^{julia.ehrenmueller@tuhh.de} ; Cristina G. Fernandes^c ; ^{cris@ime.usp.br} ; Carl Georg Heise^b ; ^{carl.georg.heise@tuhh.de} ; Songling Shan^a ; ^{sshan2@gsu.edu} ; Ping Yang^a ; ^{pyang5@gsu.edu} ; Amy N. Yates^a ; ^{ayates2@gsu.edu}
• 刊名：Discrete Mathematics
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：340
• 期：3
• 页码：287-304
• 全文大小：606 K
• 卷排序：340

文摘

In 1966 Gallai asked whether all longest paths in a connected graph have nonempty intersection. This is not true in general and various counterexamples have been found. However, the answer to Gallai’s question is positive for several well-known classes of graphs, as for instance connected outerplanar graphs, connected split graphs, and 2-trees. A graph is series–parallel if it does not contain K4K4 as a minor. Series–parallel graphs are also known as partial 2-trees, which are arbitrary subgraphs of 2-trees. We present two independent proofs that every connected series–parallel graph has a vertex that is common to all of its longest paths. Since 2-trees are maximal series–parallel graphs, and outerplanar graphs are also series–parallel, our result captures these two classes in one proof and strengthens them to a larger class of graphs. We also describe how one such vertex can be found in linear time.