Altitude of wheels and wheel-like graphs

• Autorzy: Tomasz Dzido , Hanna Furmańczyk
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Altitude; Edge-ordering; Increasing paths

Kategorie tematyczne

• 05C78: Graph labelling (graceful graphs, bandwidth, etc.)

• Wydawca: De Gruyter Open
• Czasopismo: Open Mathematics
• Rocznik: 2010
• Tom: 8
• Numer: 2
• Strony: 319-326

Daty

wydano

2010-04-01

online

2010-04-14

Twórcy

autor

Tomasz Dzido

• University of Gdańsk

autor

Hanna Furmańczyk

• University of Gdańsk

Bibliografia

• [1] Brandstädt A., Le V.B., Spinrad J.P., Graph Classes: A Survey, Philadelphia, PA: SIAM, 1987
• [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
• [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
• [4] Chvátal V., Komlós J., Some combinatorial theorems on monotonicity,Canad. Math. Bull., 1971, 14,151–157
• [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

Identyfikatory

DOI

10.2478/s11533-010-0017-4