Altitude of regular graphs with girth at least five. (English) Zbl 1062.05131
Summary: 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\geqslant 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 Blanuš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.
MSC:
| 05C78 | Graph labelling (graceful graphs, bandwidth, etc.) |
| 05C15 | Coloring of graphs and hypergraphs |
| 05C38 | Paths and cycles |
References:
| [1] | N. Alon, Problems and results in extremal combinatorics, part I, preprint.; N. Alon, Problems and results in extremal combinatorics, part I, preprint. · Zbl 1033.05060 |
| [2] | Bialostocki, A.; Roditty, Y., A monotone path in an edge-ordered graph, Internat. J. Math. Math. Sci., 10, 315-320 (1987) · Zbl 0633.05043 |
| [3] | Burger, A. P.; Cockayne, E. J.; Mynhardt, C. M., Altitude of small complete and complete bipartite graphs, Australas. J. Combin., 31, 165-175 (2005) · Zbl 1080.05046 |
| [4] | Calderbank, A. R.; Chung, F. R.K.; Sturtevant, D. G., Increasing sequences with non-zero block sums and increasing paths in edge-ordered graphs, Discrete Math., 50, 15-28 (1984) · Zbl 0542.05058 |
| [5] | Chartrand, G.; Lesniak, L., Graphs and Digraphs (1996), Chapman & Hall: Chapman & Hall London · Zbl 0890.05001 |
| [6] | Chvátal, V.; Komlós, J., Some combinatorial theorems on monotonicity, Canad. Math. Bull., 14, 151-157 (1971) · Zbl 0214.23503 |
| [7] | Cockayne, E. J.; Mynhardt, C. M., Altitude of \(K_{3, n}\), J. Combin. Math. Combin. Comput., 52, 143-157 (2005) · Zbl 1073.05062 |
| [8] | E.J. Cockayne, C.M. Mynhardt, Complete Bipartite Graphs with Altitude Four, submitted.; E.J. Cockayne, C.M. Mynhardt, Complete Bipartite Graphs with Altitude Four, submitted. · Zbl 1080.05046 |
| [9] | Fiorini, S., Hypohamiltonian snarks, (Fiedler, M., Graphs and Other Combinatorial Topics (1983), Teubner: Teubner Leipzig), 70-75 · Zbl 0535.05045 |
| [10] | Graham, R. L.; Kleitman, D. J., Increasing paths in edge ordered graphs, Period. Math. Hungar., 3, 141-148 (1973) · Zbl 0243.05116 |
| [11] | Isaacs, R., Infinite families of nontrivial trivalent graphs which are not Tait colorable, Amer. Math. Monthly, 82, 221-293 (1975) · Zbl 0311.05109 |
| [12] | Nedela, R.; S˘koviera, M., Decompositions and reductions of snarks, J. Graph Theory, 22, 253-279 (1996) · Zbl 0856.05082 |
| [13] | Read, R. C.; Wilson, R. J., An Atlas of Graphs (1998), Oxford University Press: Oxford University Press New York · Zbl 0908.05001 |
| [14] | Roditty, Y.; Shoham, B.; Yuster, R., Monotone paths in edge-ordered sparse graphs, Discrete Math., 226, 411-417 (2001) · Zbl 0961.05040 |
| [15] | Yuster, R., Large monotone paths in graphs with bounded degree, Graphs Combin., 17, 579-587 (2001) · Zbl 1010.05044 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
