An edge-ordering of a graph G=(V, E) is a one-to-one mapping f:E(G)→{1, 2, ..., |E(G)|}. A path of length k in G is called a (k, f)-ascent if f increases along the successive edges forming the path. The altitude α(G) of G is the greatest integer k such that for all edge-orderings f, G has a (k, f)-ascent. In our paper we give exact values of α(G) for all helms and wheels. Furthermore, we use our result to obtain altitude for graphs that are subgraphs of helms.
@article{bwmeta1.element.doi-10_2478_s11533-010-0017-4,
author = {Tomasz Dzido and Hanna Furma\'nczyk},
title = {Altitude of wheels and wheel-like graphs},
journal = {Open Mathematics},
volume = {8},
year = {2010},
pages = {319-326},
zbl = {1205.05202},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_2478_s11533-010-0017-4}
}
Tomasz Dzido; Hanna Furmańczyk. Altitude of wheels and wheel-like graphs. Open Mathematics, Tome 8 (2010) pp. 319-326. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_2478_s11533-010-0017-4/
[1] Brandstädt A., Le V.B., Spinrad J.P., Graph Classes: A Survey, Philadelphia, PA: SIAM, 1987 | Zbl 0919.05001
[2] Burger A.P., Cockayne E.J., Mynhardt C.M., Altitude of small complete and complete bipartite graphs, Australas. J. Combin., 2005, 31, 167–177 | Zbl 1080.05046
[3] Burger A.P., Mynhardt C.M., Clark T.C., Falvai B., Henderson N.D.R., Altitude of regular graphs with girth at least five,Disc. Math.,2005,294,241–257 http://dx.doi.org/10.1016/j.disc.2005.02.007 | Zbl 1062.05131
[4] Chvátal V., Komlós J., Some combinatorial theorems on monotonicity,Canad. Math. Bull., 1971, 14,151–157 | Zbl 0214.23503
[5] Cockayne E.J., Mynhardt C.M., Altitude of K 3,n , J. Combin. Math. Combin. Comp., 2005, 52, 143–157
[6] Katrenič J., Semanišin G., Complexity of ascent finding problem, Proceedings of SOFSEM 2008, High Tatras, Slovakia, January 20–24, 2008, II, 70–77