Advanced search
Start date
Betweenand
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

ransversals of longest cycles in partial k-trees and chordal graph

Full text
Author(s):
Gutierrez, Juan [1]
Total Authors: 1
Affiliation:
[1] Univ Ingn & Tecnol UTEC, Dept Ciencia Computac, Jr Medrano Silva 165, Lima 15063 - Peru
Total Affiliations: 1
Document type: Journal article
Source: JOURNAL OF GRAPH THEORY; v. 98, n. 4 JUL 2021.
Web of Science Citations: 0
Abstract

Let lct ( G ) be the minimum cardinality of a set of vertices that intersects every longest cycle of a 2-connected graph G. We show that lct ( G ) <= k - 1 if G is a partial k-tree and that lct ( G ) <= max [ 1 , omega ( G ) - 3 ] if G is chordal, where omega ( G ) is the cardinality of a maximum clique in G. Those results imply that all longest cycles intersect in 2-connected series-parallel graphs and in 3-trees. (AU)

FAPESP's process: 15/08538-5 - Graph transversals
Grantee:Juan Gabriel Gutierrez Alva
Support type: Scholarships in Brazil - Doctorate