Some formulas and bounds for the bandwidth of graphs

Date of Publication

1999

Document Type

Dissertation

Degree Name

Doctor of Philosophy in Mathematics

Subject Categories

Mathematics

College

College of Science

Department/Unit

Mathematics and Statistics

Thesis Adviser

Severino V. Gervacio

Defense Panel Chair

Leonor A. Ruivivar

Defense Panel Member

Severino D. Diesto
Blessilda P. Raposa
Yolando B. Beronque
Arlene A. Pascasio

Abstract/Summary

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.

Abstract Format

html

Language

English

Format

Print

Accession Number

TG02847

Shelf Location

Archives, The Learning Commons, 12F Henry Sy Sr. Hall

Physical Description

79 leaves ; Computer print-out

Keywords

Mathematics--Formulae; Graph theory; Mathematics--Problems, exercises, etc.

This document is currently not available here.

Share

COinS