TUHH Open Research (TORE)https://tore.tuhh.deTORE captures, stores, indexes, preserves, and distributes digital research material.Sun, 04 Jun 2023 04:21:31 GMT2023-06-04T04:21:31Z5011Nonempty intersection of longest paths in series–parallel graphshttp://hdl.handle.net/11420/4169Title: Nonempty intersection of longest paths in series–parallel graphs
Authors: Chen, Guantao; Ehrenmüller, Julia; Fernandes, Cristina G.; Heise, Carl Georg; Shan, Songling; Yang, Ping; Yates, Amy N.
Abstract: 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 K4 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.
Sun, 01 Jan 2017 00:00:00 GMThttp://hdl.handle.net/11420/41692017-01-01T00:00:00Z