수학정리(Applications, Adjacent, IcMT, dicMT)

-About AdMT(G), egv of AdMT(G), λ

-sum of all λ = 0

-sum of all (λ)^2 = 2m

-sum over all i < j λ_G(i)*λ_G(j)  = (-m)

-sum of all (λ)^3 = 6t

-ith row sum of AdMT(G) = d(vi)

-ith row sum of (AdMT(G))^2 = d(vi)m(vi)

-(i,j)-entry of (AdMT(G))^k = the distinct number of walk(vi,vj) of length k 
-(Characterization of Connected Bipartite)G:connected일 때 TFAE(link)

-G:bipartite

-a:egv of AdMT(G)이면 so does (-a)

-(-specR(AdMT(G))):egv of AdMT(G)

-AdMT(G) has exactly one positive egv iff the non-isolated vertices form a complete multipartite graph(link)

-charP(AdMT(G))의 linear equation은 G의 figure를 보고 바로 작성 가능, λ*xi=sum of all xj s.t. vi~vj

-charP(AdMT(G)) = the prod of all charP(AdMT(C)) where C:connected components of G

-G1 graph-iso G2 iff AdMT(G1) is similar to AdMT(G2) (특히 이 similar에 쓰이는 Invertible MT가 permutation임)

-the spectrum of graph is graph invariant

-하지만 charP(AdMT(G1))=charP(AdMT(G2))라 해서 G1 graph-iso G2가 아닐 수 있음,

-(Same Neighborhoods)

-sub-vertex set V' having same set of neighbors Ν with |V'|=k이면, 0는 λ되고 gm(0)=am(0)=at least k-1

(AdMT(G)는 symmetry이고 따라서 HMT이고 NMT이고 따라서 udgMT이므로 am(λ)=gm(λ)가 성립)

-vi와vj가 have same set of neighbors일 때 vi와 vj를 이어버린다면 resultant graph에서는 -1는 λ되고 multiplicities는 최소 1

-(Neighbor of several pendants)

-v1, v2:pendant이고 same neighbor를 갖는다면, nonzero λ에 대응되는 eigencomponents는 same

-G:connected, G':proper spanning subgraph of G이면 λ_G(1) > λ_G'(1)(using irreducible, nnn matrix property)

-(Recurrence Relation of charP(AdMT(G)))

for e=vivj, charP(AdMT(G)) = charP(AdMT(G-e)) - charP(AdMT(G-vi-vj)) - 2 sum over all trail T containing e charP(AdMT(G-V(T)))

-AdMT(bar(G)) = J - IMT - AdMT(G), where J is a matrix with all entries 1(SdMT랑 비슷하나 다름)

-λ를 찾는 다른 방법

-f:V(G)->R, AdMT(G)f:V(G)->R로 보고 찾는 방법이 있다.

-λ_L(G)(n)) >= -2

-λ_L(G)(1)*IMT - AdMT(G):psd

-G':induced subgraph of G일 때 (link)

-min of egv of AdMT(G) <= min of egv of AdMT(G')

-max of egv of AdMT(G') <= max of egv of AdMT(G)

-(Interlacing, deleting one vertex)

:G'=G-v일 때, λ_G(1)>=λ_G'(1)>=λ_G(2)>=λ_G'(2)>=...>=λ_G'(n-1)>=λ_G(n)(by cauchy-poincare)

-(Upper Bound of λ_G(1))

-λ_G(1) <= Δ_1, with = iff G:regular(link)

(증명은 maximum eigencomponent잡아서 linear equation생각과, =증명은 constant row sum생각)

-G:connected일 때 λ_G(1) <= sqrt(2m -(n-1)δ + (δ-1)Δ) with = iff G graph-iso K_(1,n-1) or G:regular(link)

-G:connected일 때 λ_G(1) <= sqrt(2m - n +1) with = iff G graph-iso K_n or K_(1,n-1)

-G:connected일 때 λ_G(1) <= {(Δ_2 - 1 + sqrt((Δ_2 - 1)^2 + 4Δ_1))/2}, with = iff G:regular or G:(n-1, Δ_2)-semiregular graph with Δ_2 < (n-1)(link)(link)(link)

-G:connected일 때 λ_G(1) <= max over i m(vi)(증명은, D^(-1)AD의 row sum생각)

-G:connected일 때 λ_G(1) <= max over i~j sqrt(m(vi)m(vj)), with = iff G:m(vi):fixed

or G:bipartite with {U,W}, all v in U, m(v):fixed and all w in W, m(w):fixed

(better than above)

(증명은 바로 밑에 것에 D^(-1)AD로 시작하면 됨)

-λ_G(1) <= max over i~j sqrt(d(vi)d(vj)), with = iff G:regular or semiregular bipartite(link1)(link2)

-λ_G(1) <= max over isqrt(d(vi)m(vi)), better than above

(증명은 (AdMT(G))^2의 row sum생각)

-λ_G(1) <= 2 iff G is...(link)

-λ_G(1) < 2 iff G is ...(link)

-(Lower Bound of λ_G(1))

-λ_G(1) >= 2m/n(증명은 Courant-Fischer에다가 x=(1,1,...,1)대입)

-(Lower bound of λ_G(n))

-G:connected일 때 λ_G(n) >= (-1) * sqrt(2m - (n-1)δ + (δ-1)Δ)(link)

-About Energy

-G1,G2가 graph-isomorphic이면 equienergetic, 역은 성립 안함

-if G:non-singular,

-|det(AdMT(G))| >= 1(왜냐하면 구할 때 생각해보면 entry가 모두 0,1이므로, det가 정수이며 nonzero)

-G:non-hypoenergetic

-(Lower Bound of energy(G))

-energy(G) >= 2 * sqrt(m), with = iff G:complete bipartite plus some isolated vertices(link)

-energy(G) >= sqrt( 2m + n(n-1)*(|det(AdMT(G))|)^(2/n) )(link)

-G:non-singular connected일 때 energy(G) >= 2m/n + (n-1) + ln(|det(AdMT(G))| - ln(2m/n),

with = iff G:K_n(link1)(link2)

(better than above)

-(Upper Bounds of energy(G))

-energy(G) <= sqrt(2*m*n) <= 2*m, with = iff G:m개의 K_2 plus some isolated vertices(link)

-About m_(G,A)

-

-About Specific Cases

-G:r-regular iff r는 λ with (1,1,...,1):egv for r

-if G1, G2:r-regular,

-spec(AdMT(G1))={r,λ_G(2),λ_G(3),...,λ_G(n)}

-charP(AdMT(L(G1),x) = (x+2)^(m-n) * charP(AdMT(G1),x-r+2)(link)

-(Sach's Theorem)spec(AdMT(L(G))={λ_G(i) + r - 2, -2 s.t. i=1,2,3,...,n}

(-2의 multiplicity는 m-n)

-spec(AdMT(bar(G1)))={n-r-1, -1-λ_G(2), -1-λ_G(3),..., -1-λ_G(n)}(link)

-bar(G1) have the same egv of G

-if n1=n2=n, then L(L(G1)), L(L(G2)):equienergetic(Sach's Theorem쓰면 됨)

-L^k(G1),L^k(G2):equienergetic for all k >= 2

-if G has no isolated vertices, then G:non-hypoenergetic

-spec(AdMT(G))={n-1, -1, ..., -1} iff G:K_n

-spec(AdMT(K_n))={n-1, -1, ..., -1}(link)

-energy(L(K_n))=2*n*(n-3)

-for n >=4, L(K_n):hyperenergetic

-spec(AdMT(K_(1,n-1)))={sqrt(n-1),0,0,...,0,-sqrt(n-1)}, 0는 n-2개(link)

-G:connected일 때 spec(AdMT(G))={sqrt(n-1),0,0,...,0,-sqrt(n-1)}, 0는 n-2개이면 G는 tree이고 

-D(G)=2라면 K_(1,n-1), D(G) != 2라면 G has induced subgraph of P_4

-spec(AdMT(K_(p,q))={sqrt(pq),0,...,0,-sqrt(pq)}, 0은 p+q-2개

-spec(AdMT(the friendship graph on n=2t+1)) = {(1+sqrt(1+8t))/2, 1,1,...,1,-1,-1,...,-1, (1-sqrt(1+8t)/2}, 1은 t-1개, -1은 t개(link)

-spec(AdMT(T(a,b))) = {sqrt(a+b-1), sqrt(b-1), 0,0,...,0, -sqrt(b-1), -sqrt(a+b-1)}, 0은 ab-2a+1개

-spec(AdMT(P_n))={2*cos((pi*j)/(n+1)), where j=1,2,...,n}

-spec(AdMT(C_n))={2*cos((2*pi*j)/n), where j=0,1,...,n-1}

-About Trees

-(Upper Bound of λ_G(1) for Tree)

-G:tree with n>2, then λ_G(1) <= sqrt( (n-1) - {(Δ+Δ'-1)-sqrt((Δ+Δ'-1)^2 - 4(Δ-1)(Δ'-1))}/2 )

where v1 s.t. d(v1)=Δ, Δ' := max over k~1 d(vk)(link)

-(Lower Bound of λ_G(1) for Tree)

-G:tree with a vertex v s.t. e(v)<=2일 때 λ_G(1) >= sqrt(d(v)+m(v)-1) (꼭 λ_G(1)이 아니라 nonzero λ이면 성립)(link)

-G:tree 이면 λ_G(1) >= max over i sqrt(d(vi)+m(vi)-1) using above and interlacing property

-(Lower Bound of λ_G(2) for Tree)

-G:tree with n>2, then λ_G(2) >= sqrt( {(Δ+Δ'-1) - sqrt((Δ+Δ'-1)^2 - 4(Δ-1)(Δ'-1))}/2 )

where v1 s.t. d(v1)=Δ, Δ' := max over k~1 d(vk)(link)

-About m_(T,A)

-m_(T,A)(λ) <= p(T) - 1(link)

-if q(T) != 1 and λ != 0, then m_(T,A)(λ) <= q(T) - 1(link)

-p(T) - q(T) <= m_(T,A)(0) <= p(T) - 1

-About IcMT(G)

-if the inner product of distinct two columns is nonzero, then the value is equal to the number of common vertices of corresponding edges

-rt(IcMT(G)) * IcMT(G) = 2IMT +AdMT(L(G))

-if the inner product of distinct two rows is nonzero, then the value is equal to the number of edges joining the corresponding vertices

-IcMT(G) * rt(IcMT(G)) = sLap(G)

-rank(IcMT(G))= n - |# of connected components|

-About dIcMT(G)

-|rt(dIcMT(G)) * dIcMT(G) - 2*IMT| = AdMT(L(G))

-dIcMT(G) * rt(dIcMT(G)) = Lap(G)(각 edge의 orientation이 어떻든간에)