Transversals of Longest Paths

Márcia R. Cerioli; Cristina G. Fernandes; Renzo Gómez; Juan Gutiérrez; Paloma T. Lima

doi:10.1016/j.endm.2017.10.024

Transversals of Longest Paths

Márcia R. Cerioli, Cristina G. Fernandes, Renzo Gómez, Juan Gutiérrez, Paloma T. Lima

Producción científica: Contribución a una revista › Artículo › revisión exhaustiva

1 Cita (Scopus)

Resumen

Let lpt(G) be the minimum cardinality of a set of vertices that intersects all longest paths in a connected graph G. We show that, if G is a chordal graph, then lpt(G)≤max⁡{1,ω(G)−2}, where ω(G) is the size of a largest clique in G; that lpt(G)≤tw(G), where tw(G) is the treewidth of G; and that lpt(G)=1 if G is a bipartite permutation graph or a full substar graph.

Idioma original	Inglés
Páginas (desde-hasta)	135-140
Número de páginas	6
Publicación	Electronic Notes in Discrete Mathematics
Volumen	62
DOI	https://doi.org/10.1016/j.endm.2017.10.024
Estado	Publicada - nov. 2017
Publicado de forma externa	Sí

Acceder al documento

10.1016/j.endm.2017.10.024

Otros archivos y enlaces

Enlace a la publicación en Scopus

Citar esto

@article{992c2064600a4b19966616c9ddc8530b,

title = "Transversals of Longest Paths",

abstract = "Let lpt(G) be the minimum cardinality of a set of vertices that intersects all longest paths in a connected graph G. We show that, if G is a chordal graph, then lpt(G)≤max⁡{1,ω(G)−2}, where ω(G) is the size of a largest clique in G; that lpt(G)≤tw(G), where tw(G) is the treewidth of G; and that lpt(G)=1 if G is a bipartite permutation graph or a full substar graph.",

keywords = "chordal, longest path, permutation, substars, transversal, treewidth",

author = "Cerioli, {M{\'a}rcia R.} and Fernandes, {Cristina G.} and Renzo G{\'o}mez and Juan Guti{\'e}rrez and Lima, {Paloma T.}",

note = "Publisher Copyright: {\textcopyright} 2017 Elsevier B.V.",

year = "2017",

month = nov,

doi = "10.1016/j.endm.2017.10.024",

language = "English",

volume = "62",

pages = "135--140",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

}

TY - JOUR

T1 - Transversals of Longest Paths

AU - Cerioli, Márcia R.

AU - Fernandes, Cristina G.

AU - Gómez, Renzo

AU - Gutiérrez, Juan

AU - Lima, Paloma T.

PY - 2017/11

Y1 - 2017/11

N2 - Let lpt(G) be the minimum cardinality of a set of vertices that intersects all longest paths in a connected graph G. We show that, if G is a chordal graph, then lpt(G)≤max⁡{1,ω(G)−2}, where ω(G) is the size of a largest clique in G; that lpt(G)≤tw(G), where tw(G) is the treewidth of G; and that lpt(G)=1 if G is a bipartite permutation graph or a full substar graph.

AB - Let lpt(G) be the minimum cardinality of a set of vertices that intersects all longest paths in a connected graph G. We show that, if G is a chordal graph, then lpt(G)≤max⁡{1,ω(G)−2}, where ω(G) is the size of a largest clique in G; that lpt(G)≤tw(G), where tw(G) is the treewidth of G; and that lpt(G)=1 if G is a bipartite permutation graph or a full substar graph.

KW - chordal

KW - longest path

KW - permutation

KW - substars

KW - transversal

KW - treewidth

UR - http://www.scopus.com/inward/record.url?scp=85032434324&partnerID=8YFLogxK

U2 - 10.1016/j.endm.2017.10.024

DO - 10.1016/j.endm.2017.10.024

M3 - Article

AN - SCOPUS:85032434324

SN - 1571-0653

VL - 62

SP - 135

EP - 140

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

Transversals of Longest Paths

Resumen

Acceder al documento

Otros archivos y enlaces

Huella

Citar esto