Antibandwidth of a Graph
DOI:
https://doi.org/10.12723/mjs.23.4Keywords:
Vertex independent number, chromatic number, vertex connectivity, antibandwidth.Abstract
The antibandwidth problem consists of placing the vertices of a graph on a line in consecutive integer points in such a way that the minimum difference of adjacent vertices is maximized. This problem is NP- hard. In this paper, we find some bounds for antibandwidth using some invariants of graphs. We prove that considerating the interior boundary and the exterior boundary when estimating the antibandwidth of connected graphs gives the same results.
References
Z Miller and D Pritikin, On the separation number of graphs, Networks, vol. 19, pp. 651-666, 1989.
F T Leighton, B M Maggs and S B Rao, Packet routing and job-shop scheduling in O (congestion + Dilation) steps, Combinatorica, vol. 14, pp. 167-180, 1994.
J Y-T Leung, O Vornberger and J D Witthoff, On some variants of the bandwidth minimization problem, SIAM Journal on Computing, vol. 13, pp. 650-667, 1984.
Y Lin and J Yuan, “The dual bandwidth problem for graphs,” Journal of Zhengzhou University, vol. 35, 2003.
F Harary, Graph theory, Massachusetts: Addison-Wesley, 1969.
