BERMAN† AND K.-H

ALGEBRAICCONNECTIVITY OFTREES WITHA PENDANT

EDGE OFINFINITE WEIGHT

∗

A. BERMAN

†

AND K.-H. FÖRSTER

‡

Abstract. Let

G

^{beaweighted graph. Let}

v

^{bea vertexof}

G

^{and let}

G ^v _ω

^{denote the graph}

obtainedbyaddingavertex

u

^andanedge

{v, u}

^withweight

ω

^to

G

^{.Thenthealgebraic}connectivity

µ(G ^v _ω )

^of

G ^v _ω

^isanondecreasingfunctionof

ω

^{andisboundedbythealgebraic}connectivity

µ(G)

^of

G

^{.Thequestionofwhen}

_ω→∞ lim µ(G ^v _ω )

^isequalto

µ(G)

^{isconsideredandansweredinthecasethat}

G

^isatree.

Keywords. Weightedgraphs,Trees,Laplacianmatrix,Algebraicconnectivity,Pendantedge.

AMSsubjectclassications. 5C50,5C40,15A18.

1. Introduction. Aweightedgraphon

n

^{vertices isanundirectedsimplegraph}

G

^on

n

^{verticessuchthatwitheachedge}

e

^of

G

^{,thereisanassociatedpositivenumber}

ω(e)

^{whichiscalledtheweight of}

e

^.

TheLaplacian matrix of aweighted graph

G

^on

n

^{vertices isthe}

n × n

^matrix

L(G) = L = (l ij )

^{,whereforeach}

i, j = 1, . . . , n,

l _ij =

 

 



 

 

−ω(e)

^if

i = j

^and

e = {i, j},

0

^if

i = j

^and

i

^{isnotadjacentto}

j,

k=i l _ik

^if

i = j.

Clearly

L

^{is asingular}

M

^{-matrixandpositive}semidenite, so

λ ₁ (L) = 0

^,where

forasymmetricmatrix

A

^wearrangetheeigenvaluesinnondecreasingorder

λ ₁ (A) ≤ λ ₂ (A) ≤ . . .

Fiedler [3] showed that

λ ₂ (L)

^{is positive i}

G

^{is connected and called it the}

algebraicconnectivity of

G

^{. Thealgebraic}connectivityof

G

^{willbedenotedby}

µ(G).

Inthispaper

G

^{alwaysdenotesaconnectedweightedgraphwithoutloops.}

Let

G

^beagraphwith

n

^{vertices. Let}

v

^beavertexof

G

^andlet

G ^v _ω

^bethegraph

with

n + 1

^{verticesobtainedbyadding to}

G

^avertex

u

^andanedge

e = {v, u}

^with

weight

ω

^.

∗

Receivedbytheeditors21July2003.Acceptedforpublication24June2005. HandlingEditor:

StephenJ.Kirkland.

†

Department of Mathematics, Technion, Haifa 32000, Israel,([email protected]).

Research supportedbythe New York MetropolitanFund for Research at the Technion. Mostof

theworkwasdoneduringavisittoTUBerlin;partoftheworkwasdoneinFUBerlin,Charite-

BenjaminFranklin.

‡

DepartmentofMathematics, Technical UniversityBerlin,Sekr. MA6-4,Strassedes17. Juni 136,10623Berlin,Germany([email protected]).

Theorem 1.1. The algebraic connectivity

µ(G ^v _ω )

^isa nondecreasing function of

ω

^{andfor every}

ω

^and

n > 1

µ(G ^v _ω ) ≤ µ(G).

Proof. Let

L _ω

^{be the Laplacian matrix of}

G ^v _ω

^{and let}

0 < ω ₁ ≤ ω ₂

^{. Then}

B = L _{ω 2} − L _{ω 1}

^{isasingularrankonepositivesemidenitematrix. By[7,Th. 4.3.1]}

λ _k ( L _{ω 1} ) ≤ λ _k ( L _{ω 2} )

^for

k = 1 . . . n,

andfor

k = 2, µ(G ^v _{ω 1} ) ≤ µ(G ^v _{ω 2} ).

Toshowthat

µ(G ^v _ω )

^{isbounded, write}

L _ω

^{asthesumoftwoblockmatrices}

L _ω =



 

L(G) 0

0 0



  +



 

0 0

0 ω − ω

− ω ω



  ,

where

L(G)

^is

n×n

^{andtheleftupperzeroblockinthesecondmatrixis}

(n−1)×(n−1)

^.

By[7,Th. 4.3.4(a),thecase

k = 2

^],

µ ( G ^v _ω ) = λ ₂ ( L _ω ) ≤ λ ₃ ( L ( G ) ⊕ (0))

= λ ₂ (L(G)) = µ(G).

Remark 1.2. Thetheorem is essentiallyaconsequenceof Cor. 4.2 of[6]. It is

provedfortreesin [8].

Example 1.3. Forthecompletegraphs

K _n , n > 1,

^{withallweightsequalto 1}

ω→∞ lim µ((K n ) ^v _ω ) = n + 1

2 < n = µ(K n ).

Example 1.4. Forthecycles

C _n , n > 2 ,

^{withweightsequalto1}

ω→∞ lim µ((C n ) ^v _ω ) = µ(C n+1 ) < µ(C n ).

Example 1.5. Let

G

^{be thegraphobtainedfrom}

K ₄

^{bydeleting an edge and}

letalltheweightsof

G

^{beequalto1. Ifthedegreeof}

v

^is3,

ω→∞ lim µ(G ^v _ω ) = 2 = µ(G).

Ifthedegreeof

v

^is2

ω→∞ lim µ(G ^v _ω ) < µ(G).

Since

µ(G ^v _ω )

^isboundedby

µ(G)

^{,itisnaturaltoaskwhendoes}

ω→∞ lim µ ( G ^v _ω ) = µ ( G ) .

We answer this question in Section 3, in the case that

G

^{is a tree. The needed}

2. Results on trees. Our paper relies heavily on the work of [12] so in this

sectionwedescribetheirmainresultsandbasicbackgroundontreesneededforthese

resultsandforthenextsection. Insomecaseswechangethenotationof[12].

Theorem 2.1. [4,Th. 3.11]Let

T

^{be a weighted tree with Laplacian matrix}

L

and algebraic connectivity

µ

^{. Let}

y

^{be an} eigenvector of

L

^{associated with}

µ

^{. Then}

exactly oneofthe followingtwocasesoccur:

(a) Someentryof

y

^is

0

^.

(b) Allentries of

y

^arenonzero.

In the rst casethere exists aunique vertex

c

^suchthat

y _c = 0

^and

c

^{isadjacent to}

avertex

d

^with

y _d = 0

^{. In the secondcasethereis aunique pair of vertices}

i

^and

j

adjacent in

T

^suchthat

y _i y _j < 0

^.

Definition 2.2. Aweightedtree

T

^{is saidtobeoftypeI witha}characteristic vertex

c

^ifcase

(a)

^{ofTheorem2.1holds,andoftypeII with}characteristicvertices

i

and

j

^incase

(b)

^{. Weusealsothenotation}

I _c

^{in therstcaseand}

II _i,j

^inthesecond

case.

Thenamecharacteristicverticeswascoinedin[11]byR.Merriswhoshowedthat

if

µ

^isnotasimpleeigenvalue,thenallthecorrespondingeigenvectorsyieldthesame typeoftreeandthesamecharacteristicvertices.

Definition 2.3. Let

v

^{beavertex ofatree}

T

^{. Let}

L _v

^{bethematrixobtained}

bydeleting therowandcolumn of theLaplacianmatrixof

T

^{that correspond to}

v

^.

Thematrix

M _v,T := L ⁻¹ _v

^{iscalled thebottleneckmatrixof}

T

^at

v

^.

In[9]and[10],itisshownthattheentryof

M _v,T

^thatcorrespondstothevertices

k

^and

l

^is

m _kl = 1 ω(g)

wherethesummationisonalledges

g

^thatlieontheintersectionofthepathbetween

k

^and

v

^{and thepathbetween}

l

^and

v

^{. Thematrix}

M _v,T

^is permutationallysimilar to ablock diagonalmatrix, wherethe numberofblocksis thedegreeof

v

^{and each}

blockisapositivematrixwhichcorrespondsto auniquebranchat

v

^.

Forvertices

u, v

^ofatree

T

^let

v → u

^{denotethebranchof}

T

^at

v

^{,thatcontains}

u

^.

Wedenoteby

M _v→u,T

^theblockof

M _v,T

^thatcorrespondsto

v → u

^,andby

M _v→u,T

thematrixobtainedfrom

M _v,T

^{bydeleting therowsandthecolumns} corresponding to

M _v→u,T

^.

Definition 2.4. A diagonal block of

M _v,T

^{whose spectral radius is equal to}

ρ(M v,T )

^{, where}

ρ(A)

^{denotes thespectralradiusof thematrix}

A

^{, iscalled aPerron}

blockandthecorrespondingbranchof

T

^at

v

^{iscalled aPerronbranch.}

Theorem2.5. [9,Cor. 2.1]Let

T

^{beaweightedtree. Then}

T

^{isoftypeIwitha}

characteristic vertex

c

^{,if andonlyif at}

c

^,

T

^{has morethanone Perron branch.}

Inthis case,

µ(T )

^{,the algebraic} connectivity of

T

^{isequal to}

_ρ(M ¹

c,T )

^.

Let

e

^{be an edge of a graph}

G

^{. Replace the weightat}

e

^by

ω

^{and denote the}

resultinggraphby

G ^e _ω

^{. Observethat since}

e = {v, u}

^{isapendantedgeof}

G ^v _ω

^,then

(G ^v _ω ) ^e _ω = G ^v _ω

^{. Let}

G ^e _∞

^{denotethefamilyofweightedgraphs}

{G ^e _ω , ω > 0}

^,andlet

G ^v _∞

denotethefamilyofweightedgraphs

{G ^v _ω , ω > 0}

^.

Theorem 2.6. [12,Corollary1.1] Let

T

^{bea weighted treeandlet}

e

^{be anedge}

of

T

^{. Then thereexistsapositive number}

ω ₀

^{suchthatallthe trees}

T _ω ^e , ω ₀ < ω < ∞

^,

areof the sametypeandhave the samecharacteristicvertices.

Thefollowingdenitionsareusedin [12].

Definition 2.7. Thefamilyoftrees

T _∞ ^e

^{isatypeItreeatinnitywithcharac-}

teristicvertex

c

^{if thereexistsan}

ω ₀ > 0

^{suchthat forall}

ω ∈ [ω ₀ , ∞)

^,

T _ω ^e

^isoftype

I _c

^{. Similarly,}

T _∞ ^e

^{is a typeII tree at innity with} characteristic vertices

i

^and

j

^if

thereexists an

ω ₀ > 0

^{suchthat forall}

ω ∈ [ω 0 , ∞)

^,

T _ω ^e

^{is oftype}

II _i,j

^.

Wenowcanstatethemainresultof[12].

Theorem 2.8. [12,Th.1.8]Let

e = {v, u}

^{be anedge thatis notapendantedge}

of a tree

T

^{. Let}

T ₁

^and

T ₂

^{be the resulting components arising from the deletion of}

e

^{. Suppose}

v ∈ T ₁

^,

u ∈ T ₂

^and

µ ( T ₁ ) ≤ µ ( T ₂ )

^{. Then}

lim

ω→∞ µ ( T _ω ^e ) = µ ( T ₁ )

ⁱ

T ₁

^isa

treeoftypeIwith acharacteristicvertex, say,

c

^{,and oneof thefollowing conditions}

holds:

(a)

T _∞ ^e

^{isoftype Iwitha}characteristicvertex

c

^.

(b)

c

^{isincident to}

e

^and

ρ(M u,T 2 ) ≤ _µ(T ¹ _{1 )}

^.

Weconcludethe backgroundresultswiththe analogueofTheorem 2.5 fortype

IItreesandtwopropositionsthatwillbeusedinprovingthemainresult.

Theorem 2.9. [9,Th.1]Aweightedtree

T

^{isof typeIIiateveryvertex}

T

^has

auniquePerronbranch. Ifthe characteristicvertices,

i

^and

j

^,of

T

^{arejoinedby an}

edge ofweight

θ

^{,thenthereexistsanumber}

0 < γ < 1

^,suchthat

ρ(M i→j,T − γ

θ J ) = ρ(M j→i,T − 1 − γ θ J ), and µ ( T ) = 1

ρ(M i→j,T − ^γ _θ J) = 1

ρ(M _j→i,T − ^1−γ _θ J) ,

whereJdenotes an allonesmatrix.

Proposition2.10. [8,Cor. 1.1]Thecharacteristicverticesof

T _ω ^v

^{lieonthe path}

between thecharacteristicverticesof Tand

u

^.

Proposition 2.11. [12, Claim 3.2] Let Tbea tree. Let

{ i _k , j _k }

^{beedges in T}

withweights

α _k

^,for

k = 1 , 2

^{,suchthatthepathfrom}

i ₁

^to

j ₂

^contains

j ₁

^and

i ₂

^,and

let

0 < γ ₁ , γ ₂ < 1

^{. Then}

ρ(M j 1 →i 1 ,T − γ ₁

α ₁ J ) < ρ(M j 1 →i 1 ,T ) < ρ(M j 2 →i 2 ,T − γ ₂ α ₂ J ).

3. Assigninganarbitrarilylargeweighttoapendantedgeofatree. In

thissectionweconsiderthecasewhere

T

^isatreeand

u

^{isapendantvertexof}

T ∪ e

where

e = { v, u }

^and

v ∈ T

^.

In some sense the question in this case may be considered asa special case of

thediscussion in [12]. Todo this,

{u}

^{isto beconsidered asa "treewith algebraic}

connectivity

∞

^{"and the spectralradius of an empty matrix hasto be dened (for}

Ourdiscussionisbasedontheanalysisofthelimitsofthebottleneckmatricesof

T _ω ^v

^when

ω

^increasesto

∞

^;namely

M _v,T v

ω = M _v,T ⊕ 1

ω

,

M _u,T v

ω = (M _v,T ⊕ (0)) + 1 ω J

andif

s = v

^isavertexof

T

^,

M _{s,T ω} ^v =

M _s,T M ^(v) M ^(v)t m _vv + _ω ¹

,

where

M ^(v)

^{isthecolumnof}

M _s,T

correspondingto

v

^and

m _vv

^{isthediagonalentry}

of

M _s,T

^, corresponding to

v

^{. In} particular, for all the branches of

T

^at

s

^{that do}

not contain

v

^{, the diagonal blocks of}

M _s,T v

ω

^{and of}

M _s,T

^{are the same. Denoting}

ω→∞ lim M _s,T v

ω

^by

M _s,T v

∞

^weseethatfor

s / ∈ e M _s,T v

∞ =



 M _s,T M ^(v) M ^(v)t m _vv





^(3.1)

and

M _v,T v

∞ = M _u,T v

∞ = M _v,T ⊕ (0) .

^(3.2)

Thereadershouldnotbeconfusedbythefactthat

T ^v _∞

^{denotesafamilyoftrees}

while

M _{s,T ∞} ^v

^{denotesasinglematrix(upto} permutationsimilarity).

Example3.1.

◦ 1/2 a

@ @

@ @

@ @

@

◦ _c ¹ ◦ _v ^ω ◦ _u

◦ ^1/2

b

~ ~

~ ~

~ ~

~

M _v,T v

∞ = M _u,T v

∞ =



 



3 1 1 0 1 3 1 0 1 1 1 0 0 0 0 0



 

 ,

M _{c,T ∞} ^v =



 



2 0 0 0 0 2 0 0 0 0 1 1 0 0 1 1



 

 ,

M _{a,T ∞} ^v = M _{b,T ∞} ^v =



 



4 2 2 2 2 2 2 2 2 2 3 3 2 2 3 3



 

 .

Remark 3.2. Thematrices

M _{s,T ∞} ^v

^{are ofcourse singular, but theydo contain}

informationon

lim ω→∞ µ(T _ω ^v )

^.

As in thecaseofnonsingularbottleneck matriceswe callthe diagonalblocks of

M _{s,T ∞} ^v

^{whosespectralradiusismaximal,Perronblocks. The}correspondingbranches of

T _ω ^v

^{donotdependon}

ω

^{;theywillbecalledthePerronbranchesofthefamily}

T _∞ ^v

^.

Lemma 3.3. If

M _s,T v

∞

^{hasmorethanonePerronblock, then}

ω→∞ lim µ(T _ω ^v ) = 1 ρ(M s,T _∞ ^v ) .

Proof. Considertheprincipal submatrix

L _s,T v

ω

^{obtainedfromtheLaplacianma-}

trixof

T _ω ^v

^{bydeleting therowandcolumn} correspondingto

s

^{. Then}

M _s,T v

∞ = lim

ω→∞ (L s,T _ω ^v ) ⁻¹ .

By[7,Th. 4.3.15]for

r = n − 1, k = 1

^and

k = 2

^,

λ ₁ (L s,T _ω ^v ) ≤ µ(T _ω ^v ) ≤ λ ₂ (L s,T _ω ^v ),

so

ω→∞ lim λ ₁ (L s,T _ω ^v ) ≤ lim

ω→∞ µ(T _ω ^v ) ≤ lim

ω→∞ λ ₂ (L s,T _ω ^v ),

Since

M _{s,T ∞} ^v

^{hasatleasttwoPerronblocksweobtain}

ω→∞ lim λ ₂ (L s,T _ω ^v ) = lim

ω→∞ λ ₁ (L s,T _ω ^v ) = ρ(M s,T _∞ ^v ).

Remark 3.4. Ifthere existsan

ω ₀

^{such thattwoofthePerronblocksof}

M _{s,T ∞} ^v

arePerronblocksof

M _{s,T ω} ^v

^for

ω ≥ ω ₀

^then

λ ₂ (L s,T _ω ^v ) = λ ₁ (L s,T _ω ^v )

^for

ω ≥ ω ₀ .

Lemma 3.5. Let

s

^{be a vertex of}

T

^{. Suppose}

M _{s,T ∞} ^v

^{has at least two Perron}

blocks andlet

t

^{beanother vertexof}

T

^{. Then}

ρ(M t,T _∞ ^v ) > ρ(M s,T _∞ ^v )

Proof. Byassumption, thefamily

T _∞ ^v

^{has atleast twoPerron branchesat}

s

^{, so}

oneofthem,say

s → x

^{,doesnotcontain}

t

^{. Let}

t → s

^{bethebranchat}

t

^thatcontains

s

^{. Thenitcontainsthebranch}

s → x

^,andweobtain

ρ(M t,T _∞ ^v ) ≥ ρ(M t→s,T _∞ ^v ) > ρ(M s→x,T _∞ ^v ) = ρ(M s,T _∞ ^v ),

wherethestrictinequalityfollowsfrom [1, Cor. 2.1.5]andthefact that

M _s→x,T v

∞

^is

asubmatrixof

M _t→s,T v

∞

^{,whichispositive.}

Corollary3.6. Thereisatmost onevertex, say

c

^,suchthat

M _c,T v

∞

^{has more}

thanonePerronblock.

Definition 3.7. Inthecasethatthere isavertex

c

^suchthat

M _c,T ∞ v

^hasmore

thanonePerronblock,wewillsaythatthefamilyoftrees

T _∞ ^v

^{isatrii(treeininnity)}

oftypeIc. Ifnosuch

c

^{existswesaythat}

T _∞ ^v

^{isatriioftypeII.}

Remark 3.8.

(a)If thetrees

T _ω ^v

^{are oftypeI}

_c

^{for allsucientlylarge}

ω

^{, then thefamily}

T _∞ ^v

isatriioftypeI

c

^{(andalsoatypeI treeat innitywith}characteristicvertex

c

^{). In}

otherwords,if

T _∞ ^v

^{isatriioftypeII,thenforall}

ω

^largeenough,

T _ω ^v

^{aretreesoftype}

II.

(b)Supposethetrees

T _ω ^v

^areoftypeII

_p,q

^{forallsucientlylarge}

ω

^,thenbythe

representationof

L _ω

^{intheproofofTheorem 1.1andbyTheorem2.1,}

{ p, q }

^cannot

bethependantedge

{v, u}

^.

(c) It is possible that

T _ω ^v

^{are of type II for all suciently large}

ω

^(so

T _∞ ^v

^{is a}

typeII treeat innity) but

T _ω ^v

^{is atriiof typeI;see Lemma3.10and Subcase 4of}

Example3.13in thefollowingdiscussion.

Remark3.9. TheproofofLemma 3.5showsthatif

T

^{isatreeoftypeIwitha}

characteristicvertex

c

^{, thenforanyothervertex}

s

^of

T ρ ( M _s,T ) > ρ ( M _c,T ) .

(ThishasalreadybeenestablishedinProposition2of[9].)

ConsiderTheorem2.9 where

T _ω ^v

^isoftypeII

_i,j

^{andtheweightoftheedge}

{i, j}

is

θ

^{. Thenforevery}

ω

^{(sucientlylarge)there existanumber}

γ _ω

^{,between0and1,}

suchthat

µ(T _ω ^v ) = 1

ρ(M _{i→j,T ω} ^v − ^γ _θ ^ω J ) = 1 ρ ( M _j→i,T v

ω − ^1−γ _θ ^ω J ) .

Whathappenstothethenumber

γ _ω

^when

ω

^goesto

∞

^{? Weclaimthat}

lim

ω→∞ γ _ω

exists. Indeed,oneofthebranchescorrespondingto

M _i→j,T v

ω

^and

M _j→i,T v

ω

^doesnot

contain

u

^{. Suppose it is the second, so}

M _j→i,T v

ω = M _j→i,T

^{. The numbers}

µ ( T _ω ^v )

increasetoalimit,seeTheorem1.1,sothenumbers

ρ(M j→i,T _ω ^v − ^1−γ _θ ^ω J)

^decreaseto

alimit,whichmeansthatthenumbers1-

γ _ω

^{increasetoalimit. Thislimitisatmost}

1since

0 < γ _ω < 1

^.

Lemma 3.10. If the trees

T _ω ^v

^{are of typeII, with} characteristic vertices

i, j

^for

ω ₀ < ω < ∞

^,andif

γ = lim

ω→∞ γ _ω = 0

^,where

ρ(M _{i→j,T ω} ^v − ^γ _θ ^ω J ) = ρ(M _{j→i,T ω} ^v − ^1−γ _θ ^ω J )

and

θ

^{isthe weightof theedge}

{i, j}

^,then

T _∞ ^v

^{isatrii oftypeI}

_i

^{. Similarly,if}

γ = 1

then

T _∞ ^v

^{isatrii oftype I}

_j

^.

Proof.

M _j→i,T v

∞ = (M _{ij,T ∞} ^v ⊕ (0)) + ¹ _θ J

^{so if}

γ = 0

^{, then}

ρ(M _{i→j,T ∞} ^v ) = ρ(M _{j→i,T ∞} ^v − ¹ _θ J ) = ρ(M _{ij,T ∞} ^v )

^so

T _∞ ^e

^{isatriioftypeI}

_i

^.

Corollary 3.11. If the trees

T _ω ^v

^{are of type II and if}

T _∞ ^v

^{isa trii of type II,}

then

0 < γ = lim

ω→∞ γ _ω < 1

^.

Remark 3.12. Thetree

T

^{can beatree oftypeI with a}characteristicvertex, say

c

^{,or atreeoftypeII.Intherstcasethereare3}possibilities:

1 T _∞ ^v

^{is atriioftypeI}

_c

^,

2 T _∞ ^v

^{is atriioftypeI}

_s

^{, where}

s = c

^,

3 T _∞ ^v

^{is atriioftypeII.}

Inthesecond casethere aretwopossibilities:

4 T _∞ ^v

^{is atriioftypeI}

_s

^forsome

s

^,

5 T _∞ ^v

^{is atriioftypeII.}

Thefollowingexampledemonstratesthatallvesubcasesarepossible.

Example 3.13.

Subcase1

◦

x @ @

@ @

@ @

@

◦ _c ¹ ◦ _v ^ω ◦ _u

◦ ^x

~ ~

~ ~

~ ~

~ 0 < x ≤ ¹ ₂ .

Here

M _{c,T ω} ^v =



 



1/x 0 0 0

0 1/x 0 0

0 0 1 1

0 0 1 1 + _ω ¹



 

 ,

sofor

x < ¹ ₂ , T _∞ ^v

^{isatreeoftypeI witha}characteristicvertex

c

^andfor

x = _2, ¹

^itis

onlyatriioftype

I _c

^.

Anotherexampleiswhen

c = v

◦ x

@ @

@ @

@ @

@

◦ _c ^ω ◦ _u

◦ ^x

~ ~

~ ~

~ ~

~

.

Subcase2

◦

x

@ @

@ @

@ @

@

◦ _c ¹⁰ ◦ _s ¹ ◦ _v ^ω ◦ _u

◦ ^x

~ ~

~ ~

~ ~

~

where

ρ







 1 /x + 0 . 1 0 . 1 0 . 1 0.1 1/x + 0.1 0.1

0.1 0.1 0.1







 = 2 .

Subcase3

◦ x

@ @

@ @

@ @

@

◦ _c ¹ ◦ _v ^ω ◦ _u

◦ ^x

~ ~

~ ~

~ ~

~ 1

2 < x ≤ 1,

or

◦ ¹ ◦ _c ¹ ◦ _v ^ω ◦.

Subcase4

◦ ¹ ◦ ^x ◦ _s ¹ ◦ _v ^ω ◦, ρ

1 + 1/x 1/x 1/x 1/x

= 2.

Subcase5

Herewesuggest3examples:

◦

x @ @

@ @

@ @

@

◦ ¹ ◦ ^ω ◦

◦ ^x

~ ~

~ ~

~ ~

~

x > 1,

◦ ^x ◦ ¹ ◦ ^ω ◦

x / ∈ {1/2, 1},

◦ 1

@ @

@ @

@ @

@

◦ _v ^ω ◦ _u

◦ ^x

~ ~

~ ~

~ ~

~

x = 1 .

Wearenowreadytostateandprovethemainresult.

Theorem 3.14. Let

T

^{beatree. Then}

ω→∞ lim µ(T _ω ^v ) = µ(T )

^(3.3)

if andonlyif

(a)

T

^{isatreeof typeIwith} characteristic vertexsay

c

^,

and

(b)

ρ(M _{c→u,T ∞} ^v ₎ ≤ ρ(M c,T ) = _µ(T ¹ ₎

^.

Proof. We provethetheorem byconsidering the vesubcases of Remark 3.12,

andshowingthat(3), (a)and(b)holdinSubcase1andonlyinthiscase,i.e. ifand

onlyif

T

^and

T _∞ ^v

^areoftypeI

_c

^{forsomevertex}

c

^.

Subcase 1: Obviously (a) holds. From (1) and (2) follows that

ρ(M c,T _ω ^v ) ≥ ρ(M c,T )

^{. Butif}

T

^and

T _ω ^v

^areoftype

I _c

^{,thenequalityholds. Thus}

ρ(M _{c→u,T ∞} ^v ₎ ≤ ρ(M c,T ),

proving(b),and

µ(T ) = 1

ρ ( M _c,T ) = 1 ρ ( M _c,T v

ω ) = lim

ω→∞ µ(T _ω ^v ),

proving(3). ThiscompletestheproofinSubcase1.

If

T

^{is atreeof type}

I _c

^{and(b) holds, then itfollowseasily that}

T _ω ^v

^{is atrii of}

typeI

c

^{. Therefore(b) doesnot hold in Subcases 2and 3,while (a) obviouslydoes}

nothold in Subcases4 and5. Nowwewill provethat (3) doesnothold in thelast

foursubcases.

Subcase2: Wehaveto showthat(3)doesnothold. Indeed

µ(T ) = 1

ρ(M c,T ) > 1 ρ(M s,T )

= 1

ρ(M s,T _ω ^v )

^,byLemma3.5

= lim

ω→∞ µ(T _ω ^v )

^{, byLemma 3.3.}

Subcase3: ByRemark 3.8(a)thetrees

T _ω ^v

^{areforsucientlylarge}

ω

^oftype

II

^,

sayoftype

II _p,q

^{,seeTheorem2.6,andtheedge}

{p, q}

^of

T

^hasweight

θ

^,byRemark

3.8(b)itdoesnotdependon

ω

^{. Withoutlossof}generality,

p

^{liesonthepathbetween}

q

^and

c

^.

ByProposition2.10thevertices

p

^and

q

^{lie onthepathbetween}

c

^and

u

^{. Let}

i

beaneighborof

c

^suchthat

c, p

^and

q

^{lieonthepathbetween}

i

^and

u

^and

c → i

^isa

Perronbranchof

T

^{. Thenweobtain}

ω→∞ lim µ(T _ω ^v ) = lim

ω→∞

1

ρ(M q→p,T _ω ^v − ^γ _θ ^ω J )

^{,byTheorem2.9,}

= lim

ω→∞

1

ρ(M _q→p,T − ^γ _θ ^ω J )

^,since

q → p

^isin

T

^,

= 1

ρ(M _q→p,T − ^γ _θ J)

^,where

0 < γ < 1

^{,byCorollary3.11,}

< 1

ρ(M _c→i,T )

^,byProposition2.11,

= 1

ρ ( M _c,T )

^{, since}

c → i

^{isaPerronbranchof}

T,

= µ(T )

^,since

T

^isoftype

I _c ,

so(3)doesnothold.

Subcase4: Here againwehaveto showthat (3)doesnothold. Suppose

T

^{is of}

type

II _ij

^{, where}

j

^{lies on thepathfrom}

i

^to

u

^{. Let}

θ

^and

γ

^{beasin Theorem 2.9.}

Since

T _ω ^v

^{is atriioftype}

I _s

^{, theby}Proposition 2.10,

s

^{lies onthepathfrom}

i

^to

u

^.

Therefore

ω→∞ lim µ(T _ω ^v ) = lim

ω→∞

1

ρ(M s→i,T _ω ^v ) = lim

ω→∞

1 ρ(M s→i,T )

≤ 1

ρ(M _j→i,T ) < 1

ρ(M _j→i,T − ^γ _θ J) = µ(T ).

Subcase5: HereTisof,say,typeII

ij

^andfor

ω

^largeenough,

T _ω ^v

^{areof,say,type}

II

pq

^{, whereby} Proposition 2.10,we maytake, withoutlossofgenerality,

p

^and

q

^to

liebetween

i

^and

q

^{. Let}

θ

^and

γ

^{beas in Theorem2.9 forthe edge}

{i, j}

ⁱⁿ

T

^and

let

θ ˆ

^and

γ _ω

^bethecorrespondingpairfortheedge

{p, q}

ⁱⁿ

T _ω ^v

^{. Observethat}

θ ˆ

^does

notdependon

ω

^{byRemark3.8(b). Let}

γ ˆ = lim ω→∞ γ _ω

^{. ByCorollary3.13wehave}

0 < γ < 1

^{. Now}

ω→∞ lim µ(T _ω ^v ) = lim

ω→∞

1 ρ(M _{q→p,T ω} ^v − ^γ _ˆ ^ω

θ J ) = lim

ω→∞

1 ρ(M _q→p,T − ^γ _ˆ ^ω

θ J )

= 1

ρ ( M _q→p,T − ^{γ ˆ} _{θ ˆ} J ) < 1

ρ ( M _j→i,T − ^γ _θ J ) = µ(T ),

wheretheinequalityfollowsfromProposition2.11.

Acknowledgments. We are indebted to Mr. Felix Goldberg [5] for suggesting

Example1.5 which showsthat

G

^{doesnothaveto beatree for}

lim

ω→∞ µ(G ^v _ω ) = µ(G)

tohold. Thequestionofwhen does

lim

ω→∞ µ(G ^v _ω ) = µ(G)

^{, when}

G

^{isageneralgraph,}

seems to be much more dicult than the one in the case that

G

^{is a tree. We}

are grateful to thereferee for his orherimportant remarks and forsuggestingthat

Propositions 1.3and1.4, as wellasLemma 2.2of[2], maybeusefulin dealingwith

thegeneralcase.

REFERENCES

[1] A.Bermanand R.J.Plemmons.NonnegativeMatricesinthe MathematicalSciences,SIAM,

Philadelphia,1994.

[2] S.FallatandS.Kirkland.Extremizing algebraicconnectivitysubjecttographtheoretic con-

straints. ElectronicJournalofLinearAlgebra,3:4874,1998.

[3] M.Fiedler.Algebraicconnectivityofgraphs.CzechoslovakMathematicalJournal,23: 298305,

1973.

[4] M.Fiedler.Apropertyofeigenvectorsofnonnegativesymmetricmatricesanditsapplications

tographtheory.CzechoslovakMathematicalJournal,25: 619633,1975.

[5] F.Goldberg.Privatecommunication.

[6] R.Grone,R.Merris,and V.Sunder.TheLaplacianspectrumofagraph. SIAMJournal on

MatrixAnalysisandApplications,11: 218-238,1990.

[7] R.J.HornandC.R.Johnson.MatrixAnalysis.CambridgeUniversityPress,Cambridge,1985.

[8] S.Kirklandand M. Neumann.Algebraic connectivity ofweighted trees underperturbation.

LinearandMultilinearAlgebra,42: 187203,1997.

[9] S.Kirkland,M.Neumann,andB.Shader.CharacteristicverticesofweightedtreesviaPerron

values.LinearandMultilinearAlgebra,40: 311325,1996.

[10] S.Kirkland, M.Neumann,and B.Shader. Distancesinweightedtrees andgroupinverse of

LaplacianMatrices. SIAM Journal on MatrixAnalysis and Applications, 18: 827841,

1997.

[11] R.Merris.Characteristicverticesoftrees.LinearandMultilinearAlgebra,22: 115131,1987.

[12] J.J.MolitiernoandM.Neumann.Thealgebraicconnectivityoftwotreesconnectedbyanedge

ofinniteweight. ElectronicJournalofLinearAlgebra,8: 113,2001.