View in EDS

Detour trees.

Saved in:
Bibliographic Details
Title: Detour trees.
Authors: Jobson, Adam S.1, Kézdy, André E.1 kezdy@louisville.edu, Lehel, Jenő1, White, Susan C.2
Source: Discrete Applied Mathematics. Jun2016, Vol. 206, p73-80. 8p.
Subjects: Tree graphs, Length measurement, Geometric vertices, Graph connectivity, Paths & cycles in graph theory
Abstract: A detour of a graph is a path of maximum length. A vertex that is common to all detours of a graph is called a Gallai vertex . As a tool to prove the existence of a Gallai vertex, we introduce the concept of a detour tree , a spanning tree of a graph in which the vertex set of any detour of the graph induces a subtree. We give several characterizations of graphs that have a detour tree. We also prove that any compatible tree of a connected dually chordal graph is a detour tree. This, combined with the fact that subtrees of a tree satisfy the Helly property, guarantees that every connected dually chordal graph contains at least one Gallai vertex. Consequently, connected graphs from subfamilies of dually chordal graphs have a Gallai vertex, including the well-studied doubly chordal, strongly chordal and interval graphs. Separately we prove that connected cographs (which are not necessarily dually chordal) have a Gallai vertex. Analogous results for cycles of maximum length follow. [ABSTRACT FROM AUTHOR]
Copyright of Discrete Applied Mathematics is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 114873646
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Detour trees.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Jobson%2C+Adam+S%2E%22">Jobson, Adam S.</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Kézdy%2C+André+E%2E%22">Kézdy, André E.</searchLink><relatesTo>1</relatesTo><i> kezdy@louisville.edu</i><br /><searchLink fieldCode="AR" term="%22Lehel%2C+Jenő%22">Lehel, Jenő</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22White%2C+Susan+C%2E%22">White, Susan C.</searchLink><relatesTo>2</relatesTo>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Discrete+Applied+Mathematics%22">Discrete Applied Mathematics</searchLink>. Jun2016, Vol. 206, p73-80. 8p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Tree+graphs%22">Tree graphs</searchLink><br /><searchLink fieldCode="DE" term="%22Length+measurement%22">Length measurement</searchLink><br /><searchLink fieldCode="DE" term="%22Geometric+vertices%22">Geometric vertices</searchLink><br /><searchLink fieldCode="DE" term="%22Graph+connectivity%22">Graph connectivity</searchLink><br /><searchLink fieldCode="DE" term="%22Paths+%26+cycles+in+graph+theory%22">Paths & cycles in graph theory</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: A detour of a graph is a path of maximum length. A vertex that is common to all detours of a graph is called a Gallai vertex . As a tool to prove the existence of a Gallai vertex, we introduce the concept of a detour tree , a spanning tree of a graph in which the vertex set of any detour of the graph induces a subtree. We give several characterizations of graphs that have a detour tree. We also prove that any compatible tree of a connected dually chordal graph is a detour tree. This, combined with the fact that subtrees of a tree satisfy the Helly property, guarantees that every connected dually chordal graph contains at least one Gallai vertex. Consequently, connected graphs from subfamilies of dually chordal graphs have a Gallai vertex, including the well-studied doubly chordal, strongly chordal and interval graphs. Separately we prove that connected cographs (which are not necessarily dually chordal) have a Gallai vertex. Analogous results for cycles of maximum length follow. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Discrete Applied Mathematics is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=114873646
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.dam.2016.02.002
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 8
        StartPage: 73
    Subjects:
      – SubjectFull: Tree graphs
        Type: general
      – SubjectFull: Length measurement
        Type: general
      – SubjectFull: Geometric vertices
        Type: general
      – SubjectFull: Graph connectivity
        Type: general
      – SubjectFull: Paths & cycles in graph theory
        Type: general
    Titles:
      – TitleFull: Detour trees.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Jobson, Adam S.
      – PersonEntity:
          Name:
            NameFull: Kézdy, André E.
      – PersonEntity:
          Name:
            NameFull: Lehel, Jenő
      – PersonEntity:
          Name:
            NameFull: White, Susan C.
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 19
              M: 06
              Text: Jun2016
              Type: published
              Y: 2016
          Identifiers:
            – Type: issn-print
              Value: 0166218X
          Numbering:
            – Type: volume
              Value: 206
          Titles:
            – TitleFull: Discrete Applied Mathematics
              Type: main
ResultId 1