Details

Autor(en) / Beteiligte

• Mynhardt, C.M.
• Burger, A.P.
• Clark, T.C.
• Falvai, B.
• Henderson, N.D.R.

Titel

Altitude of regular graphs with girth at least five

Ist Teil von

• Discrete mathematics, 2005-05, Vol.294 (3), p.241-257

Ort / Verlag

Amsterdam: Elsevier B.V

Erscheinungsjahr

2005

Quelle

Free E-Journal (出版社公開部分のみ）

Beschreibungen/Notizen

• 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.