A note on on-line ranking number of graphs

Gabriel Semanišin; Roman Soták

Czechoslovak Mathematical Journal (2006)

  • Volume: 56, Issue: 2, page 591-599
  • ISSN: 0011-4642

Abstract

top
A k -ranking of a graph G = ( V , E ) is a mapping ϕ V { 1 , 2 , , k } such that each path with endvertices of the same colour c contains an internal vertex with colour greater than c . The ranking number of a graph G is the smallest positive integer k admitting a k -ranking of G . In the on-line version of the problem, the vertices v 1 , v 2 , , v n of G arrive one by one in an arbitrary order, and only the edges of the induced graph G [ { v 1 , v 2 , , v i } ] are known when the colour for the vertex v i has to be chosen. The on-line ranking number of a graph G is the smallest positive integer k such that there exists an algorithm that produces a k -ranking of G for an arbitrary input sequence of its vertices. We show that there are graphs with arbitrarily large difference and arbitrarily large ratio between the ranking number and the on-line ranking number. We also determine the on-line ranking number of complete n -partite graphs. The question of additivity and heredity is discussed as well.

How to cite

top

Semanišin, Gabriel, and Soták, Roman. "A note on on-line ranking number of graphs." Czechoslovak Mathematical Journal 56.2 (2006): 591-599. <http://eudml.org/doc/31051>.

@article{Semanišin2006,
abstract = {A $k$-ranking of a graph $G=(V,E)$ is a mapping $\varphi \:V \rightarrow \lbrace 1,2,\dots ,k\rbrace $ such that each path with endvertices of the same colour $c$ contains an internal vertex with colour greater than $c$. The ranking number of a graph $G$ is the smallest positive integer $k$ admitting a $k$-ranking of $G$. In the on-line version of the problem, the vertices $v_1,v_2,\dots ,v_n$ of $G$ arrive one by one in an arbitrary order, and only the edges of the induced graph $G[\lbrace v_1,v_2,\dots ,v_i\rbrace ]$ are known when the colour for the vertex $v_i$ has to be chosen. The on-line ranking number of a graph $G$ is the smallest positive integer $k$ such that there exists an algorithm that produces a $k$-ranking of $G$ for an arbitrary input sequence of its vertices. We show that there are graphs with arbitrarily large difference and arbitrarily large ratio between the ranking number and the on-line ranking number. We also determine the on-line ranking number of complete $n$-partite graphs. The question of additivity and heredity is discussed as well.},
author = {Semanišin, Gabriel, Soták, Roman},
journal = {Czechoslovak Mathematical Journal},
keywords = {on-line ranking number; complete $n$-partite graph; hereditary and additive properties of graphs; on-line ranking number; complete -partite graph; hereditary and additive properties of graphs},
language = {eng},
number = {2},
pages = {591-599},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {A note on on-line ranking number of graphs},
url = {http://eudml.org/doc/31051},
volume = {56},
year = {2006},
}

TY - JOUR
AU - Semanišin, Gabriel
AU - Soták, Roman
TI - A note on on-line ranking number of graphs
JO - Czechoslovak Mathematical Journal
PY - 2006
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 56
IS - 2
SP - 591
EP - 599
AB - A $k$-ranking of a graph $G=(V,E)$ is a mapping $\varphi \:V \rightarrow \lbrace 1,2,\dots ,k\rbrace $ such that each path with endvertices of the same colour $c$ contains an internal vertex with colour greater than $c$. The ranking number of a graph $G$ is the smallest positive integer $k$ admitting a $k$-ranking of $G$. In the on-line version of the problem, the vertices $v_1,v_2,\dots ,v_n$ of $G$ arrive one by one in an arbitrary order, and only the edges of the induced graph $G[\lbrace v_1,v_2,\dots ,v_i\rbrace ]$ are known when the colour for the vertex $v_i$ has to be chosen. The on-line ranking number of a graph $G$ is the smallest positive integer $k$ such that there exists an algorithm that produces a $k$-ranking of $G$ for an arbitrary input sequence of its vertices. We show that there are graphs with arbitrarily large difference and arbitrarily large ratio between the ranking number and the on-line ranking number. We also determine the on-line ranking number of complete $n$-partite graphs. The question of additivity and heredity is discussed as well.
LA - eng
KW - on-line ranking number; complete $n$-partite graph; hereditary and additive properties of graphs; on-line ranking number; complete -partite graph; hereditary and additive properties of graphs
UR - http://eudml.org/doc/31051
ER -

References

top
  1. Extremal Graph Theory, Academic Press, London, 1978. (1978) MR0506522
  2. 10.7151/dmgt.1037, Discuss. Math. Graph Theory 17 (1997), 5–50. (1997) MR1633268DOI10.7151/dmgt.1037
  3. 10.1002/jgt.3190110113, J.  Graph Theory 11 (1987), 86–99. (1987) MR0876208DOI10.1002/jgt.3190110113
  4. 10.7151/dmgt.1094, Discuss. Math. Graph Theory 19 (1999), 175–197. (1999) MR1768300DOI10.7151/dmgt.1094
  5. A lower bound for on-line ranking number of a path, Discrete Math (to appear). (to appear) MR2311106
  6. 10.1016/S0012-365X(99)00215-0, Discrete Math. 212 (2000), 141–147. (2000) MR1748681DOI10.1016/S0012-365X(99)00215-0
  7. 10.1007/BF01202473, Graphs Comb. 10 (1994), 75–93. (1994) MR1273014DOI10.1007/BF01202473

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.