Premium
A note on shortest cycle covers of cubic graphs
Author(s) -
Hou Xinmin,
Zhang CunQuan
Publication year - 2012
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.20636
Subject(s) - combinatorics , mathematics , cubic graph , disjoint sets , odd graph , graph , discrete mathematics , girth (graph theory) , upper and lower bounds , chordal graph , 1 planar graph , line graph , voltage graph , mathematical analysis
Let SCC 3 ( G ) be the length of a shortest 3‐cycle cover of a bridgeless cubic graph G . It is proved in this note that if G contains no circuit of length 5 (an improvement of Jackson's ( JCTB 1994 ) result: if G has girth at least 7) and if all 5‐circuits of G are disjoint (a new upper bound of SCC 3 ( G ) for the special class of graphs).
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