A Faber-Krahn-type inequality for regular trees

AFaber-Krahn-typeinequalityforregulartreesJosefLeydoldUniversityofEconomicsandBusinessAdministrationDepartmentofAppliedStatisticsandDataProcessingA-1090Vienna,Augasse2{6Austriaphone:43/1/31336/4695e-mail:[e-mail]-Krahn-typeinequalityforregulartreeswithboundary.Leydold:AFaber-Krahn-typeinequalityforregulartrees1.IntroductionTheeigenvectorsoftheLaplacianongraphshavereceivedlittleattentioncom-paredtothespectrumofthisoperator(seee.g.[6,9,10])ortheeigenfunctionsofthe\classicalLaplaciandierentialoperatoronRiemannianmanifolds(e.g.[1,2]).Recentlytheseeigenvectorsseemtobecomemoreimportant.Grover[7]hasdiscoveredthatthecostfunctionofanumberofwell-studiedcombinatorialoptimisationproblems,e.g.thetravellingsalesmanproblem,areeigenvectorsoftheLaplacianofcertaingraphs.Thusglobalpropertiesofsucheigenvectorsareofinterest.InthelastyearssomeresultsfortheLaplacianonmanifoldshavebeenshowntoholdalsoforthegraphLaplacian,e.g.Courant’snodaldomaintheorem([3,5])orCheeger’sinequality([4]).In[5]Friedmandescribedtheideaofa\graphwithboundary(seebelow).WiththisconcepthewasabletoformulateDirichletandNeumanneigenvalueproblems.Healsoconjecturedanother\classicalresultformanifolds,theFaber-Krahntheorem,forregularboundedtreeswithboundary.TheFaber-KrahntheoremstatesthatamongallboundeddomainsDRnwithxedvolume,aballhaslowestrstDirichleteigenvalue.Inthispaperwewanttoshowsucharesultfortrees.WegiverestrictiveconditionsfortreeswithboundarywheretherstDirichleteigenvalueisminimizedforagiven\volume.AmazinglyFriedman’sconjectureisfalse,i.e.ingeneralthesetreesarenot\balls.Butwewillshowthatthesearesimilarto\balls.2.StatementoftheResultLetG=(V;E)beanundirected(weighted)graph,withweights1ce0foreache2E.TheLaplacianofGisthematrix=(G)=D(G)A(G)whereA(G)istheadjacencymatrixofGandD(G)isthediagonalmatrixwhoseentriesarethesumsoftheweightsoftheedgesattheverticesofG,i.e.Dv;v=Pe=(v;u)2E1ce.TheassociatedRayleighquotientonreal-valuedfunctionsfonVisthefractionRG(f)=hf;fihf;fi=P(u;v)2E1ce(f(u)f(v))2Pv2V(f(v))21Leydold:AFaber-Krahn-typeinequalityforregulartreesNoticethatinoppositetotheLaplaciandierentialoperatoronmanifolds,(G)isdenedasapositiveoperator.ThegeometricrealizationofGisthemetricspaceGconsistingofVandarcsoflengthcegluedbetweenuandvforeveryedgee=(u;v)2E.WedenetwomeasuresonG(andG).Let1(G)=jVjbethenumberofverticesofGand2(G)=Pe2Ece,i.e.theLebesguemeasureofG.NowletSdenotethesetofallcontinuousfunctionsonGwhicharedierentiableonGnV.Weintroducea(Laplacian)operatorGonGbytheRayleighquotientRG(f)=RGjrfj2d2RGf2d1;f2STheoperatorGisthecontinuousversionoftheLaplacianonG.Proposition1:(see[5])TheRayleighquotientRG(f)isminimizedat,andonlyat,edgewiselinearfunc-tionsf2S,i.e.thosefunctionswhoserestrictionstoeachedgearelinear.TheeigenvaluesandeigenfunctionsofGexistandarethoseof(i.e.therestric-tionsoftheGeigenfunctionstoVaretheLaplacianeigenvectors).OnGwecanavoidtheproblemsthatarisefromthediscretenessofoursituation.Nowthe(proper)nodaldomainsofaneigenfunctionfofGarethecomponentsofthecomplementoff1(0),i.e.ofthenodalsetoff.Thusanalogouslytotheclassicalsituation(see[2])fvanishesonthe\boundaryofeachnodaldomain.ItmakessensetointroducetheDirichleteigenvalueproblemforgraphswithboundary.AgraphwithboundaryisagraphG(V0[@V;E0[@E)whereeachvertexin@V(boundaryvertex)hasdegree1(i.e.itistheendpointofoneedgenotnecessarilyoflength1)andeachvertexinV0(interiorvertex)hasdegreegreaterthanorequalto2.Eachedgee2E0(interioredge)joinstwointeriorvertices,eachedgee2@E(boundaryedge)connectsaninteriorvertexwithaboundaryvertex.Onsuchagraphwecandenethe\DirichletoperatorbyrestrictingfintheRayleighquotientRG(f)tothosefunctionsf2Swhichvanishatallbound-aryvertices.ThentheDirichleteigenvalueproblemistondtheeigenvaluesandeigenfunctionsofthisoperator.EquivalentlywecandenethisLaplacianoperatoronagraphwithboundarybyalinearoperatorthatactsontheinteriorverticesofGonly,i.e.onV0:0=D0A02Leydold:AFaber-Krahn-typeinequalityforregulartreeswhereA0istheadjacencymatrixrestrictedtoV0andwhereD0isthediagonalmatrixwhoseentrycorrespondingtov2V0is(noteE=E0[@E)(D0)v;v=Xe=(v;u)2E1ceOurgoalistondtheeigenvaluesandeigenvectorsofthisLaplacian.IfwenowinsertnewverticesoneachpointinGwheretheeigenfunctionfvanishes,thentheclosureofeachnodaldomainoffisthegeometricrealizationofagraph.Therestrictionofftothisgraph(i.e.thenodaldomain)isaneigenfunctiontotherstDirichleteigenvalueofthisgraph.Sincethereisnoriskofconfusion,wedenotetheLaplacianonagraphwithboundaryGsimplyby=(G).WedenotethelowestDirichleteigenvalueofGby(G).Wethenhavethefollowingpropertiesof.Proposition2:(see[5])LetGbeagraphwithboundary.(1)(G)isapositiveoperator,i.e.(G)0.(2)Aneigenfunctionftotheeigenvalue(G)of(G)iseitherpositiveorneg-ativeonallinteriorverticesofG.(3)(G)iscontinuousasafunctionofGinthemetric(G;G0)=2(GG0)+2(G0G).(4)(G)ismonotoneinG,i.e.ifGG0then(G)(G0).(5)(G)isasimpleeigenvalue,ifGisconnected.Wereferthereaderto[5]fortheproofsandformoredetails.Inthispaperwerestrictourinteresttoregulartreeswithbounda