DC FieldValueLanguage
dc.contributor.authorChen, Guantao-
dc.contributor.authorEhrenmüller, Julia-
dc.contributor.authorFernandes, Cristina G.-
dc.contributor.authorHeise, Carl Georg-
dc.contributor.authorShan, Songling-
dc.contributor.authorYang, Ping-
dc.contributor.authorYates, Amy N.-
dc.date.accessioned2019-12-18T07:33:45Z-
dc.date.available2019-12-18T07:33:45Z-
dc.date.issued2017-
dc.identifier.citationDiscrete Mathematics 3 (340): 287-304 (2017)de_DE
dc.identifier.issn1872-681Xde_DE
dc.identifier.urihttp://hdl.handle.net/11420/4169-
dc.description.abstractGallai 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.en
dc.language.isoende_DE
dc.publisherElsevierde_DE
dc.relation.ispartofDiscrete mathematicsde_DE
dc.subject.ddc510: Mathematikde_DE
dc.titleNonempty intersection of longest paths in series–parallel graphsde_DE
dc.typeArticlede_DE
dc.type.diniarticle-
dcterms.DCMITypeText-
tuhh.abstract.englishGallai 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.de_DE
tuhh.publisher.doi10.1016/j.disc.2016.07.023-
tuhh.publication.instituteMathematik E-10de_DE
tuhh.type.opus(wissenschaftlicher) Artikel-
dc.type.driverarticle-
dc.type.casraiJournal Article-
tuhh.container.issue3de_DE
tuhh.container.volume340de_DE
tuhh.container.startpage287de_DE
tuhh.container.endpage304de_DE
dc.identifier.scopus2-s2.0-84995404082-
datacite.resourceTypeJournal Article-
datacite.resourceTypeGeneralText-
item.grantfulltextnone-
item.cerifentitytypePublications-
item.openairetypeArticle-
item.creatorOrcidChen, Guantao-
item.creatorOrcidEhrenmüller, Julia-
item.creatorOrcidFernandes, Cristina G.-
item.creatorOrcidHeise, Carl Georg-
item.creatorOrcidShan, Songling-
item.creatorOrcidYang, Ping-
item.creatorOrcidYates, Amy N.-
item.languageiso639-1en-
item.creatorGNDChen, Guantao-
item.creatorGNDEhrenmüller, Julia-
item.creatorGNDFernandes, Cristina G.-
item.creatorGNDHeise, Carl Georg-
item.creatorGNDShan, Songling-
item.creatorGNDYang, Ping-
item.creatorGNDYates, Amy N.-
item.fulltextNo Fulltext-
item.openairecristypehttp://purl.org/coar/resource_type/c_6501-
item.mappedtypeArticle-
crisitem.author.deptMathematik E-10-
crisitem.author.parentorgStudiendekanat Elektrotechnik, Informatik und Mathematik (E)-
Appears in Collections:Publications without fulltext

#### Page view(s)

113
Last Week
1
Last month
3
checked on Dec 7, 2022

#### SCOPUSTM Citations

12
Last Week
0
Last month
0
checked on Jun 30, 2022