Some formulas and bounds for the bandwidth of graphs

• Main Author: Lim, Yvette F.
• Format: text
• Language: English
• Published: Animo Repository 1999
• Subjects: Mathematics > Formulae; Graph theory; Mathematics > Problems, exercises, etc.; Mathematics
• Online Access: https://animorepository.dlsu.edu.ph/etd_doctoral/804
• Institution: De La Salle University

The bandwidth problem for a graph is that of labeling its vertices with distinct integers so that the maximum difference across an edge is minimized. In this study, this problem is solved for the graph called flowerette Fn defined by Fortes [9] for all values of n. This is a graph which consists of the vertices of the cycle Cn together with copies of these vertices joined to each adjoining neighbor of the vertices of Cn. Furthermore, this problem is also solved for the Cartesian product of a doublestar Dm1,m2 with a path Pn, caterpillar T with a path Pn where n is greater than or equal to 2diamT - 1, caterpillar T with a cycle Cn, where n is greater than or equal to 4diamT and a connected graph G which is not complete with Pk/n where n is greater than or equal to k2(G)diamG. Optimal labellings to achieve each of these bandwidths are provided. In addition to these, some new bounds for the bandwidth of graphs are also given.