Abstract / Excerpt:

Abstract: This thesis is an exposition of the first part of the paper entitled " Bandwidth and Density for Block Graphs" which appeared in Discrete Mathematics, volume 189, pages 163 to 176 in 1998. The bandwidth problem concerns with labeling a graph in such a way that each vertex of the graph is labeled with distinct integer and minimizes the stretching of the edges of the graph. The authors of the article present a polynomial algorithm to produce an optimal bandwidth labeling for block caterpillars, graphs where deleting the vertices of degree one produces a path cliques. Furthermore, they also give examples of graphs wherein the bandwidths exceed the local density bound of the graphs. This thesis gives a detailed explanation of their work on block caterpillars and supply the necessary steps of all the proofs presented in the article . A simplified step by step procedure to label a block caterpillar graph is also provided, which is based on the proof of the main theorem. Explicit examples in labeling a block caterpillar are also presented

Info

Source Institution	Ateneo de Davao University
Unit	Natural Science
Authors	Fenecios, Jonald P.
Page Count	1
Place of Publication	Davao City
Original Publication Date	March 1, 2004
Tags	Dissertations, Graphic methods.

Preview