A note on on-line ranking number of graphs |
| |
Authors: | G Semani?in R Soták |
| |
Institution: | (1) Institute of Computer Science, Faculty of Science, P. J. Šafárik University, Jesenná 5, 041 54 Košice, Slovak Republic |
| |
Abstract: | A k-ranking of a graph G = (V, E) is a mapping ϕ: V → {1, 2, ..., k} such that each path with end vertices 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. |
| |
Keywords: | on-line ranking number complete n-partite graph hereditary and additive properties of graphs |
本文献已被 SpringerLink 等数据库收录! |
|