Premium
Smallest (1, 2)‐eulerian weight and shortest cycle covering
Author(s) -
Zhao Cheng
Publication year - 1994
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.3190180206
Subject(s) - eulerian path , combinatorics , mathematics , zhàng , graph , order (exchange) , discrete mathematics , pure mathematics , finance , lagrangian , political science , law , china , economics
The concept of a (1, 2)‐eulerian weight was introduced and studied in several papers recently by Seymour, Alspach, Goddyn, and Zhang. In this paper, we proved that if G is a 2‐connected simple graph of order n (n ≧ 7) and w is a smallest (1, 2)‐eulerian weight of graph G , then | E w=even | n ‐ 4, except for a family of graphs. Consequently, if G admits a nowhere‐zero 4‐flow and is of order at least 7, except for a family of graphs, the total length of a shortest cycle covering is at most | V(G) | + | E(G) |‐ 4. This result generalizes some previous results due to Bermond, Jackson, Jaeger, and Zhang.