Record number :
Title of article :
Altitude of regular graphs with girth at least five Original Research Article
Author/Authors :
C.M. Mynhardt، نويسنده , , A.P. Burger، نويسنده , , T.C. Clark، نويسنده , , B. Falvai، نويسنده , , N.D.R. Henderson، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2005
Pages :
From page :
To page :
Abstract :
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.
Keywords :
Edge ordering , Increasing paths , Altitude , Snarks , Monotone paths
Journal title :
Discrete Mathematics
Serial Year :
Link To Document :