Partitioning vertices of 1-tough graphs into paths

DOI10.1016/S0304-3975(00)00247-4zbMath0973.68188OpenAlexW1983119025MaRDI QIDQ5941518

Hao Li, Amel Harkat-Benhamdine, Cristina Bazgan, Mariusz Woźniak

Publication date: 20 August 2001

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(00)00247-4

zbMATH Keywords

1-tough graphpartition into paths

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (11)

On path-factor critical deleted (or covered) graphs ⋮ Path factors in subgraphs ⋮ The existence of \(P_{\geq3}\)-factor covered graphs ⋮ Path factors and neighborhoods of independent sets in graphs ⋮ A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two ⋮ Two Sufficient Conditions for Graphs to Admit Path Factors ⋮ Some sufficient conditions for path-factor uniform graphs ⋮ Toughness and isolated toughness conditions for \(P_{\ge 3}\)-factor uniform graphs ⋮ Some results about component factors in graphs ⋮ The existence of path-factor covered graphs ⋮ On \(P_{\geq 3}\)-factor deleted graphs

Cites Work

• Unnamed Item
• On a connection between the existence of k-trees and the toughness of a graph
• Not every 2-tough graph is Hamiltonian
• Tough graphs and Hamiltonian circuits.
• Toughness and the existence ofk-factors

This page was built for publication: Partitioning vertices of 1-tough graphs into paths