Altitude of regular graphs with girth at least five Original Research Article

The altitude of a graph image is the largest integer image such that for each linear ordering image of its edges, image has a (simple) path image of length image for which image increases along the edge sequence of image. We determine a necessary and sufficient condition for cubic graphs with girth at least five to have altitude three and show that for image, image-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.