Path partitions and P_n-free sets

DOI10.1016/J.DISC.2004.07.012MaRDI QIDQ1763347zbMATH OpenOpenAlexFDO

Authors Jean E. Dunbar, Marietjie Frick, Frank Bullock

Publication date 22 February 2005

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2004.07.012

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

The detour order \(\tau(G)\) of a graph \(G\) is the number of vertices of a longest path of \(G\). If \(S\) is a subset of vertices of a graph \(G\) such that the graph induced by \(S\) has detour order at most \(n\), then \(S\) is called a \(P_{n+1}\)-free set in \(G\). The path partition conjecture can be stated as follows: For any graph \(G\) and any positive integer \(n<\tau(G)\), there exists a \(P_{n+1}\)-free set \(S\) in \(G\) such that \(\tau(G-S)\leq\tau(G)-n\). In Theorem 2.1 the authors prove: Let \(G\) be a graph and \(n\) an integer with \(2\leq n<\tau(G)\). If \(X\) is a maximal \(P_{n+1}\)-free set in \(G\), then \(\tau(G-X)\leq\tau(G)-\frac{2}{3}(n+1)\). In addition, they show that if the graph \(G\) has no cycle of length less than \(n\) or greater than \(\tau(G)-n+2\), then \(\tau(G-X)\leq\tau(G)-n\) for every maximal \(P_{n+1}\)-free set in \(G\). As a corollary of the latter result, the authors prove the path partition conjecture for the special class of connected and weakly pancyclic graphs.

Recommendations

Cites work

Cited in

(22)

This page was built for publication: Path partitions and \(P_{n}\)-free sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1763347)