Premium
Covering 2‐connected 3‐regular graphs with disjoint paths
Author(s) -
Yu Gexin
Publication year - 2018
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22219
Subject(s) - combinatorics , mathematics , disjoint sets , discrete mathematics , path (computing) , conjecture , computer science , programming language
Abstract A path cover of a graph is a set of disjoint paths so that every vertex in the graph is contained in one of the paths. The path cover number p ( G ) of graph G is the cardinality of a path cover with the minimum number of paths. Reed in 1996 conjectured that a 2‐connected 3‐regular graph has path cover number at most ⌈ n / 10 ⌉ . In this article, we confirm this conjecture.