Premium
On the maximum number of pairwise compatible euler cycles
Author(s) -
Fleischner H.,
Hilton A. J. W.,
Jackson Bill
Publication year - 1990
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.3190140106
Subject(s) - mathematics , eulerian path , combinatorics , pairwise comparison , conjecture , euler characteristic , euler's formula , graph , block (permutation group theory) , multigraph , euler number (physics) , set (abstract data type) , discrete mathematics , mathematical analysis , euler equations , backward euler method , computer science , statistics , lagrangian , semi implicit euler method , programming language
B. Jackson [4] made the following conjecture: If G is an Eulerian graph with δ( G ) ≥ 2 k , then G has a set of 2 k ‐ 2 pairwise compatible Euler cycles (i.e., every pair of adjacent edges appears in at most one of these Euler cycles as a pair of consecutive edges). We verify this conjecture in the case where every circuit of G is a block of G .