Record number :

948459

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 :

17

From page :

241

To page :

257

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 :

2005

Link To Document :