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
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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom