Premium
Minimum path decompositions of oriented cubic graphs
Author(s) -
Reid K. B.,
Wayland Keith
Publication year - 1987
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.3190110115
Subject(s) - combinatorics , mathematics , cubic graph , vertex (graph theory) , conjecture , graph , path (computing) , decomposition , discrete mathematics , line graph , voltage graph , computer science , programming language , ecology , biology
Pullman [3] conjectured that if k is an odd positive integer, then every orientation of a regular graph of degree k has a minimum decomposition which contains no vertex which is both the initial vertex of some path in the decomposition and the terminal vertex of some other path in the decomposition. In this paper, the conjecture is established for cubic graphs, and its connection with Kelly's conjecture for tournaments is described.