La Trobe

Intersecting longest paths in chordal graphs

Download (224.6 kB)
journal contribution
posted on 2025-01-30, 03:13 authored by Daniel J. Harvey, Michael PayneMichael Payne
We consider the size of the smallest set of vertices required to intersect every longest path in a chordal graph. Such sets are known as longest path transversals. We show that if ω(G) is the clique number of a chordal graph G, then there is a transversal of order at most [Formula presented]. We also consider the analogous question for longest cycles, and show that if G is a 2-connected chordal graph then there is a transversal intersecting all longest cycles of order at most [Formula presented].

Funding

This research was partially funded by the Australian Government through the Australian Research Council (DE160100250) .

History

Publication Date

2023-04-01

Journal

Discrete Mathematics

Volume

346

Issue

4

Article Number

113284

Pagination

7p.

Publisher

Elsevier

ISSN

0012-365X

Rights Statement

© 2022 Elsevier B.V. All rights reserved. This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/by-nc-nd/4.0/

Usage metrics

    Journal Articles

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC