Altitude of wheels and wheel-like graphs

Tomasz Dzido; Hanna Furmańczyk

Open Mathematics (2010)

  • Volume: 8, Issue: 2, page 319-326
  • ISSN: 2391-5455

Abstract

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

How to cite

top

Tomasz Dzido, and Hanna Furmańczyk. "Altitude of wheels and wheel-like graphs." Open Mathematics 8.2 (2010): 319-326. <http://eudml.org/doc/269750>.

@article{TomaszDzido2010,
abstract = {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.},
author = {Tomasz Dzido, Hanna Furmańczyk},
journal = {Open Mathematics},
keywords = {Altitude; Edge-ordering; Increasing paths; altitude; edge-ordering; increasing paths},
language = {eng},
number = {2},
pages = {319-326},
title = {Altitude of wheels and wheel-like graphs},
url = {http://eudml.org/doc/269750},
volume = {8},
year = {2010},
}

TY - JOUR
AU - Tomasz Dzido
AU - Hanna Furmańczyk
TI - Altitude of wheels and wheel-like graphs
JO - Open Mathematics
PY - 2010
VL - 8
IS - 2
SP - 319
EP - 326
AB - 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.
LA - eng
KW - Altitude; Edge-ordering; Increasing paths; altitude; edge-ordering; increasing paths
UR - http://eudml.org/doc/269750
ER -

References

top
  1. [1] Brandstädt A., Le V.B., Spinrad J.P., Graph Classes: A Survey, Philadelphia, PA: SIAM, 1987 Zbl0919.05001
  2. [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 Zbl1080.05046
  3. [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 Zbl1062.05131
  4. [4] Chvátal V., Komlós J., Some combinatorial theorems on monotonicity,Canad. Math. Bull., 1971, 14,151–157 Zbl0214.23503
  5. [5] Cockayne E.J., Mynhardt C.M., Altitude of K 3,n , J. Combin. Math. Combin. Comp., 2005, 52, 143–157 
  6. [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 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.