
etd AT Indian Institute of Science >
Division of Electrical Sciences >
Computer Science and Automation (csa) >
Please use this identifier to cite or link to this item:
http://etd.iisc.ernet.in/2005/844

Title:  The Isoperimetric Problem On Trees And Bounded Tree Width Graphs 
Authors:  Bharadwaj, Subramanya B V 
Advisors:  Chandran, Sunil 
Keywords:  Computer Graphics  Algorithms Computer Graphics  Mathematical Models Isoperimetric Inequalities MetaFibonacci Sequences Graph Theory Trees (Graph Theory) Treewidth Graphs Weighted Graphs Infinite Binary Tree Isoperimetric Problem 
Submitted Date:  Sep2008 
Series/Report no.:  G22614 
Abstract:  In this thesis we study the isoperimetric problem on trees and graphs with bounded treewidth. Let G = (V,E) be a finite, simple and undirected graph. For let δ(S,G)= {(u,v) ε E : u ε S and v ε V – S }be the edge boundary of S. Given an integer i, 1 ≤ i ≤  V , let the edge isoperimetric value of G at I be defined as be(i,G)= mins v;s= i  δ(S,G). For S V, let φ(S,G) = {u ε V – S : ,such that be the vertex boundary of S. Given an integer i, 1 ≤ i ≤  V , let the vertex isoperimetric value of G at I be defined as bv(i,G)=
The edge isoperimetric peak of G is defined as be(G) =. Similarly
the vertex isoperimetric peak of G is defined as bv(G)= .The problem
of determining a lower bound for the vertex isoperimetric peak in complete kary trees of depth d,Tdkwas recently considered in[32]. In the first part of this thesis we provide lower bounds for the edge and vertex isoperimetric peaks in complete kary trees which improve those in[32]. Our results are then generalized to arbitrary (rooted)trees.
Let i be an integer where . For each i define the connected edge
isoperimetric value and the connected vertex isoperimetric value of
G at i as follows: is connected and is connected A metaFibonacci sequence is given by the reccurence a(n)= a(x1(n)+ a1′(n1))+ a(x2(n)+ a2′(n 2)), where xi: Z+ → Z+ , i =1,2, is a linear function of n and ai′(j)= a(j) or ai′(j)= a(j), for i=1,2. Sequences belonging to this class have been well studied but in general their properties remain intriguing. In the second part of the thesis we show an interesting connection between the problem of determining and certain metaFibonacci sequences.
In the third part of the thesis we study the problem of determining be and bv algorithmically for certain special classes of graphs.
Definition 0.1. A tree decomposition of a graph G = (V,E) is a pair where I is an index set, is a collection of subsets of V and T is a tree whose node set is I such that the following conditions are satisfied:
(For mathematical equations pl see the pdf file) 
URI:  http://etd.iisc.ernet.in/handle/2005/844 
Appears in Collections:  Computer Science and Automation (csa)

Items in etd@IISc are protected by copyright, with all rights reserved, unless otherwise indicated.
