Show simple item record

dc.contributor.advisorChandran, Sunil
dc.contributor.authorBharadwaj, Subramanya B V
dc.date.accessioned2010-08-26T08:08:31Z
dc.date.accessioned2018-07-31T04:39:56Z
dc.date.available2010-08-26T08:08:31Z
dc.date.available2018-07-31T04:39:56Z
dc.date.issued2010-08-26
dc.date.submitted2008-09
dc.identifier.urihttp://etd.iisc.ac.in/handle/2005/844
dc.description.abstractIn 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 k-ary 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 k-ary 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 meta-Fibonacci sequence is given by the reccurence a(n)= a(x1(n)+ a1′(n-1))+ 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 meta-Fibonacci 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)en_US
dc.language.isoen_USen_US
dc.relation.ispartofseriesG22614en_US
dc.subjectComputer Graphics - Algorithmsen_US
dc.subjectComputer Graphics - Mathematical Modelsen_US
dc.subjectIsoperimetric Inequalitiesen_US
dc.subjectMeta-Fibonacci Sequencesen_US
dc.subjectGraph Theoryen_US
dc.subjectTrees (Graph Theory)en_US
dc.subjectTreewidth Graphsen_US
dc.subjectWeighted Graphsen_US
dc.subjectInfinite Binary Treeen_US
dc.subjectIsoperimetric Problemen_US
dc.subject.classificationComputer Scienceen_US
dc.titleThe Isoperimetric Problem On Trees And Bounded Tree Width Graphsen_US
dc.typeThesisen_US
dc.degree.nameMSc Enggen_US
dc.degree.levelMastersen_US
dc.degree.disciplineFaculty of Engineeringen_US


Files in this item

This item appears in the following Collection(s)

Show simple item record