Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9512668 | Discrete Mathematics | 2005 | 17 Pages |
Abstract
The altitude of a graph G is the largest integer k such that for each linear ordering f of its edges, G has a (simple) path P of length k for which f increases along the edge sequence of P. We determine a necessary and sufficient condition for cubic graphs with girth at least five to have altitude three and show that for r⩾4, r-regular graphs with girth at least five have altitude at least four. Using this result we show that some snarks, including all but one of the BlanusËa type snarks, have altitude three while others, including the flower snarks, have altitude four. We construct an infinite class of 4-regular graphs with altitude four.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
C.M. Mynhardt, A.P. Burger, T.C. Clark, B. Falvai, N.D.R. Henderson,