Vol. 11 No. 4 (2012): Mapana Journal of Sciences
Research Articles

Antibandwidth of a Graph

  • Aditya Shastry,
  • Nidhi Khandelwal
Aditya Shastry
Department of Mathematics and Statistics, Banasthali University, Banasthali -304022, Rajasthan, India.
Nidhi Khandelwal
Department of Mathematics and Statistics, Banasthali University, Banasthali -304022, Rajasthan, India.
DOI: https://doi.org/10.12723/mjs.23.4

Published 2012-08-06

Keywords

  • 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

  1. Z Miller and D Pritikin, On the separation number of graphs, Networks, vol. 19, pp. 651-666, 1989.
  2. 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.
  3. 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.
  4. Y Lin and J Yuan, “The dual bandwidth problem for graphs,” Journal of Zhengzhou University, vol. 35, 2003.
  5. F Harary, Graph theory, Massachusetts: Addison-Wesley, 1969.