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
Show simple item record

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

Google ScholarTM

Check

Add Files to Item

Note about this record

Cite this record

Export

Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.