Research Journal of Recent Sciences _________________________________________________ ISSN 2277-2502 Vol. 3(9), 85-89, September (2014) Res.J.Recent Sci. International Science Congress Association 85 The Bandwidth of Maximal Planar GraphsImtiaz Ahmad Department of Mathematics, University of Malakand, Khyber Pakhtunkhwa, PAKISTANAvailable online at: www.isca.in , www.isca.me Received 26th September 2013, revised 29th November 2013, accepted 21st January 2014Abstract 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 thatis maximal planar graph. Keywords: Labelling of graphs, bandwidth of graphs, planar graphs, bipartite graphs, and maximal planar graphs. IntroductionGraph labelling is one of the well worked areas of graph theory. Simple graphs have a variety of labellings like graceful labellings, cordial, elegant, magic labellings and many more. The bandwidth labelling is one of the interesting labellings of simple graphs. However, the problem to determine the bandwidth of a general graph is NP-complete. Since then, this kind of labelling has perhaps attracted the most attention in the literature. Bandwidth labelling of graphs has a wide range of engineering applications like data security, mobile telecommunication systems, cryptography, various coding theory problems, communication networks and many more. Suppose that is a finite simple graph with vertex set = and edge set = . For undefined terminology of graph theory we refer the reader to the book of Jonathan L. Gross and Jay Yellen. A labelling is a bijection where and ,2,1{. Letbijection a . We define the bandwidth of a labelling of as maxBWuv. The bandwidth ofis given by { } maxminBWuv. We say that is a bandwidth labelling of if ).BWBW = Bandwidth of some basic graphs can be found in references4,5 and bandwidth of direct product of graphs has been discussed in references6-8. Characterizing Bandwidth via Powers of the Path Graph We start with the following denition: Denition 1. Let and H be graphs. An injection ® a is called an embedding if a preserves adjacency; that is a satises uv Î ® Î a a (2.1) in which case we say a embeds in H and write Note that there is no requirement that a preserves non-adjacency; i.e. it may happen that ) Î with uv Ï but Î a a . Note also that the composition of embeddings is an embedding. Let }.,3,2,1{ The thpower of a graph with on n vertices, denoted by, is the graph having vertex-set and edge-set { } uv, where is the length of a path from to in of minimum value. Let in (b) and Then is the graph with },3,2,1{and if )ij:is the m-uniform graph on },3,2,1{andijif ; : is the -uniform graph over the integers; andij, with ijif . Research Journal of Recent Sciences ______________________________________________________________ ISSN 2277-2502Vol. 3(9), 85-89, September (2014) Res. J. Recent Sci. International Science Congress Association 86 For example for a path graph, is the path on n vertices, while the complete graph on n vertices, for all .1 - ³ Proposition 2. Let be a bandwidth labelling of a graph. Then every 1 in the corresponding adjacency matrix, lies in the band containing the BW diagonals above and the BWdiagonals below the leading diagonal. It can be observed from the above denition that for the natural labelling = , the adjacency matrix ofwith vertex sequence ),has all s'1on its first m diagonals that are closer to the leading diagonal, for - £ £ and zero everywhere else. Using this observation and proposition 2 we have the following: Proposition 3. For the path graphPmBWfor - £ £ Proposition 4. Let be a graph on n vertices. Then BW £ if and only if is a sub graph of . From these propositions immediately follows: Corollary 5. Let be a graph on n vertices. Then BW = if and only if m is the smallest integer such that is a sub graph of . The next result relates a graph on n vertices of at most bandwidth m to the power of path graphs as defined in Definition 1. Lemma 6. The following are equivalent for a graph on n vertices: i.BW £ ; ii. ; iii. ; iv. ; Proof. Let be a graph on n vertices. Then (i)(ii). Assume that BW £ , so $ a bijection ® (we may write this as ® such that uvmax. Since we have . Moreover, let uv Î . Then . Hence . (ii)(iii). Suppose. Let be the natural mapping dened by = )( h . Hence h is an injection and if Î with ij then, )()(ijHence and so ah, as required. (iii)  (iv).Let and similar to (iii) by introducing the natural embedding by = )( h . We then have ah. (iv)(i). Let, and let us write =  a say, observe that £ + £ £ ³ - for . Dene by = , where = )( a . Since a is injection, then so isNow take any uv Î , whence . Let = = )(,)( a a say. Then . It follows thatBW £ , which completes the proof. Planarity and Bandwidth of Graphs Here we will characterize the planarity of graphs via their bandwidth by applying Lemma 6 to a graph such thatBWsomefor £ . The following corollaries immediately follow from Lemma 6. Corollary 7.BW = , if and only if is the least positive integer such that ,1Figure 1 Corollary 8: = BW, if and only if the components of are paths. Research Journal of Recent Sciences ______________________________________________________________ ISSN 2277-2502Vol. 3(9), 85-89, September (2014) Res. J. Recent Sci. International Science Congress Association 87 ,2Figure 2 Again is an (innite) planar graph as can be seen in figure-2 and £ BW if and only if is a subgraph of, so in particular is also planar. ,3For ,3is a planar graph. The next gure shows this in two stages. The rst graph in figure 3 shows its subgraph. The triangle 012contains the subgraphas illustrated in the second figure-4. If we take the subgraph of on the vertex set we get a plane version of.Each vertex of has degree 6 except for );5(3),4(2),3(1),5(2),4(1),3( - - where the bracketed numbers are the respective degrees. The degree sum of is evidently 122436)53(2)6(6 - = + - = + + + - Hence (the count here assumes that ,6 ³ but the expression is also valid for all ,3 ³ as is seen by inspecting cases). As is well known, for any planar graph on n vertices, , and so each is a maximal (with respect to edges) planar graph. This is equivalent to each face being a triangle. Each subgraph of on any 5 (consecutive) vertices, has a maximum of 9 edges and is planar as each subgraph - is planar for the deletion of any edge e of . Similarly a subgraph for on any 6 consecutive vertices has a maximum of 8 edges of the bipartite subgraph3,3of . Hence does not contain any subdivision of 3,3or and hence is a planar. In conclusion. Figure 3 Proposition 9.is planar if and only if £ Proof. Suppose that ³ . Then contains as a subgraph (as any 5 consecutive labelled vertices will be pairwise adjacent to each other) which is non planar and so nor is hence for ³ , is non-planar. Conversely is planar by the above discussion and since if £ , the result follows. Corollary 10. For any graph £ BWimplies is planar. Proof. If £ BWthenLamma, which is planar. This is stated in the contrapositiveform byJ. Chvatalova4 as: Theorem 11. If is non-planar, then £ BWAlthough Theorem 11 is contained in reference, but it gives no explanation or proper answerto the question as to why is planar. It does draw a simple picture. An Alternative Proof for the Planarity of The subdivision of some edge e with endpoints yields a graph containing one new vertex , c and with an edge set replacing e by two new edges, and. A subdivision of a graph is a graph resulting from the subdivision of edges in . We also recall the Kuratowski’s theorem that states that a nite graph is planar if and only if it does not contain a subgraph that is a subdivision of or 3,3. Research Journal of Recent Sciences ______________________________________________________________ ISSN 2277-2502Vol. 3(9), 85-89, September (2014) Res. J. Recent Sci. International Science Congress Association 88 Figure 4 Proposition 12.is planar. Proof. We use the Kuratowski’s Theorem to prove that the graph is planar. For the subdivision of it is enough to show that there is no set of 5 vertices of that are pairwise connected by a set of vertex disjoint paths. Let = be any set of 5 vertices ofand without loss assume that Any path from a to any other vertex of must pass through one of the vertices ,1 + + and + . It follows that if we take any set of 4 paths from a to the other members of, two of them pass through the same vertex )31( £ £ + and so there is no disjoint set of paths from a to all the other members of, as required. If on the other hand the 3,3subdivision were present in then there would exist 6 vertices and and a set P of 9 vertex disjoint paths from each of the members of the rst set to each of the members of the second set. Without loss we may assume that a is the least of the six integers involved (but we cannot assume that for instance). Any path from a to must pass through at least one of the vertices ,2,1 + + + , and at least one of each set of three consecutive vertices from this point onwards, until is reached. Hence, if we consider the (vertex disjoint) paths in P from a to each of and we see that they collectively include all of the vertices from a up to and including Î + where lies in the set }.,1,2 + - + - + = It follows that neither nor c lie in the interval from a up to and including + , so that . The paths in P from and from c to each contain (distinct) vertices in the interval }.3,2,1 + + + + + + = Now lies in I and the two other vertices in I are on the paths in P from a to e and to respectively. Hence e lies in I for otherwise, since , two vertices of lie on paths in P from a to e and to whence there exists a vertex v in that lies on a path in P from or from c to and also on a path from a to e or from a to contradicting the assumption that all the paths of P are vertex disjoint. Hence we do indeed have that both and e lie in I . But then there exist two vertices in on paths in P from and from c to e . There must then be some vertex u in that is both on a path in P from or from c to e and on a path from or c to , which again contradicts vertex disjointness of the set of paths. Hence 3,3is not a subdivision of either and therefore is planar by Kuratowski’s Theorem. Conclusion The bandwidth labelling is one of the most interesting labellings of finite simple graphs that has enormous applications in various fields including coding theory, telecommunication and VLSI designs and many more. This article describes the maximal planar graphs and shows that if the bandwidth of a graph is at most 3 then it is necessarily a planar graph.We have proved that graphs having bandwidth at most 3 can be embedded in and hence is the maximal planar graph. However, this is not sufficient that is, planar graphs could have bandwidth more than 3, e.g. the bandwidth of the planar graph is given as { } BWmin,is more than 3 unless { } min. On the other hand the bipartite graph, K3,3is evidently non planar having bandwidth 4. 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- Research Journal of Recent Sciences ______________________________________________________________ ISSN 2277-2502Vol. 3(9), 85-89, September (2014) Res. J. Recent Sci. International Science Congress Association 89 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 prole 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)