Premium
Hamilton weights and Petersen minors *
Author(s) -
Lai HongJian,
Zhang CunQuan
Publication year - 2001
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.10003
Subject(s) - petersen graph , combinatorics , mathematics , cubic graph , graph minor , eulerian path , graph , discrete mathematics , voltage graph , line graph , lagrangian , pure mathematics
A (1, 2)‐eulerian weight w of a cubic graph is called a Hamilton weight if every faithful circuit cover of the graph with respect to w is a set of two Hamilton circuits. Let G be a 3‐connected cubic graph containing no Petersen minor. It is proved in this paper that G admits a Hamilton weight if and only if G can be obtained from K 4 by a series of Δ↔ Y ‐operations. As a byproduct of the proof of the main theorem, we also prove that if G is a permutation graph and w is a (1,2)‐eulerian weight of G such that ( G, w ) is a critical contra pair, then the Petersen minor appears “almost everywhere” in the graph G . © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 197–219, 2001