International E-publication: Publish Projects, Dissertation, Theses, Books, Souvenir, Conference Proceeding with ISBN.  International E-Bulletin: Information/News regarding: Academics and Research

The Bandwidth of Maximal Planar Graphs

Author Affiliations

  • 1 Department of Mathematics, University of Malakand, Khyber Pakhtunkhwa, PAKISTAN

Res. J. Recent Sci., Volume 3, Issue (9), Pages 85-89, September,2 (2014)

Abstract

Bandwidth labelling is one of the interesting labellings of graphs. The bandwidth of a simple graph is the minimum of all possible maximum differences of adjacent labelled vertices. We consider bandwidth calculation for the maximal planar graphs. We characterize bandwidth of graphs via power of paths and show embedding of some planar graphs in power of path graphs. We also show alternatively that all graphs having bandwidth at most 3 are planar and prove that Pn3 is maximal planar graph.

References

  1. Papadimitriou C.H., The NP-completeness of the bandwidth minimization problem, Computing, 16, 263-270 (1976)
  2. Bloom G.S. and Golomb S.W., Numbered complete graphs,unusual rules, and assorted applications, Theory and Applications of Graphs, Lecture Notes in Math., 642, 53-65(1978)
  3. Jonathan L. Gross. Jay Yellen Handbook of Graph Theory, CRC Press, New York, USA (2004)
  4. Chvatalova J., On the bandwidthproblem for graphs, PhD Thesis, Department of Combinatorial and Optimization, University of Waterloo, Canada, (1980)
  5. Lai Y. L., K. Williams, A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs, J. Graph Theory, 31, 75–94 (1999)
  6. Ahmad I. and Peter M. Higgins, Bandwidth of direct products of graphs. Int. Math. Forum, 7 (22), 1321-1331 (2012)
  7. Ahmad I., Bandwidth labelling of graphs and their associated semigroups, PhD Thesis, Department of Mathematical Sciences, University of Essex, UK,(2011)
  8. Diestel R., Graph Theory (Third Edition), Springer-Verlag Heidelberg, New York, (2005)