(The) Anti-bandwidth of triangular grid graph

다국어 초록 (Multilingual Abstract)

The anti-bandwidth problem is to label the vertices of a graph of n vertices by 1, 2, 3, , n bijectively, such that the minimum difference of labels of adjacent vertices is maximized. In 1980, Hale, W.K. introduced the obnoxious facility location problem, radio colouring as a frequency assignment. The anti- bandwidth problem is known as an NP-complete problem for general graphs. For this reason, the anti-bandwidths of many
individual graphs have not been known yet. In this thesis, we give an anti-bandwidth labeling scheme
for a special class called triangular grid graph and study the lower bound of anti-bandwidth problem for the same class of graphs. We also give exact results for some of its subclasses.

목차 (Table of Contents)

• 1 Introduction 4
• 1.1 Definitions and motivations 4
• 1.2 The triangular grid graph 9
• 2 The anti-bandwidth of Tn. 10
• 2.1 ab(T1), and ab(T2). 10
• 2.2 The anti-bandwidth of T3. 12
• 2.3 The anti-bandwidth of T4. 13
• 2.4 Lower bound of ab(Tn) when n ≥ 5. 14
• 3 Conclusions 38