수학정리(Applications, Lap(G), sLap(G))

-About Lap(G), egv of Lap(G), μ

-sum of all egv = 2m

-Lap(G):not invertible(모든 row sum = 0이므로)

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

-Lap(G) + Lap(bar(G)) = Lap(K_n)

-n >= μ_G(1) >= μ_G(2) >= ... >= μ_G(n)=0 (using Gershgorin Circle Theorem)

-Lap(G):exactly psd, 즉, not positive-definite(nnn egv가지면서 not invertible이므로)

-(Factoring Lap(G))Lap(G) = ct(A) * A where A:(-1,0,1)-(e,v) incidence matrix, (link)

-if μ_G:nonzero, then the sum of components of egv corresponding μ_G is 0(link)

-μ:symmetric인 μ의 개수 = the number of orbits of Aut(G)

(characteristic function on orbit으로 eigenvector를 span함을 생각하면 됨)

-μ:symmectric인 μ찾는 방법(link참조)(link)

-μ:alternating iff te egv(μ) s.t. orthogonal all characteristic functions of the orbits of Aut(G)

-About perm(Lap(G))

-if G:bipartite, then perm(x*IMT - Lap(G)) = perm(x*IMT - sLap(G))

-(Relation with λ(G), edge-connectivity)

λ(G) = min over J:nontrivial proper subset of V(G) (sum over i in J, j in V(G)-J)|Lap(G)_(i,j)|

-About a(G), f:fiedler vector(link1)(link2)(link3)

-G:connected이고 vi:point of articulation일 때, G-v의 components G1,G2,...,Gr에 대해

-fi > 0 일 땐 te! Gj s.t. Gj contains a negative eigencomponent(다른 component들은 모두 fi보다 큰 eigencomponents를 가짐)

-fi = 0이고 어떤 Gj가 positive eigencomponent and negative eigencomponent모두 가진다면 Gj만 그렇고 나머지 components은 0 eigencomponents를 가짐

-fi = 0이고 te no Gj having positive eigencomponent and negative eigencomponent이면 each Gi contains either only negative or only positive or only 0 eigencomponents

-(Interlacing, deleting edges, adding edges)

-G'=G-e일 때, μ_G(1)>=μ_G'(1)>=μ_G(2)>=μ_G'(2)>=...μ_G(n)>=μ_G'(n)>=0(link)

-G'=G-e, e=vivj이고 μ_G(n) = μ_G'(n) <= μ_G(n-1) = μ_G'(n-1) <= ... <= μ_G(p) = μ_G'(p) for some p<=2일 때, for each r in {n,n-1,...,p} G and G' have the same orthonormal eigenvector corresponding to μ(r) of which the ith and jth entries are equal(link)

-N(vi)=N(vj)이고 vj,vi:not adjacent인 e=vivj추가했을 때 생각 가능, same neighbors파트 참고

-TFAE(link)

-the spectral integral variation of G occurs in one place by adding edge e=vivj

-N_G(vi)=N_V(vj)

-(0,0,...0,1,0,0,...,0,-1,0,...,0):eigenvector corresponding to |N_G(vi)|, where ith=1, jth=(-1)

-If adding edge e=vivj and the spectral integral variation of G occurs in two places(μ_G(k), μ_G(l))

then, μ_G(k) + μ_G(l)) = d(vi) +d(vj) + 1 and μ_G(k) * μ_G(l) = d(vi)*d(vj) + |N_G(vi)교N_G(vj)|(link)

-for |V(G1)|<=|V(G2)| and G1,G2:disjoint connected graphs, TFAE(link)

-the spectral integral variation of G1+G2 occurs in two places by adding an edge e=uv, where u in V(G1), v in V(G2)

-|V(G1)|=1 and |V(G2)| >= 2 and d(v)=|V(G2)| - 1

-Let G' be a graph from G by removing an edge and adding a new edge that was not there before

then spec(Lap(G))과 spec(Lap(G'))비교(link)

-(Interlacing, deleting vertices, adding vertices)

-G':subgraph from deleting 1 vertieces from G,

then μ_G'(i) >= μ_G(i+1) - 1 for i=1,2,...,n-2(link)

-G':subgraph from deleting k vertices from G, then a(G') >= a(G) - k(link)

(link, 혹은 위에 걸로 증명됨)

-V(G)=UUV(decomposition), then a(G) <= min(a(G[U])+|V|, a(G[V])+|U|)

-G':subgraph from deleting cutvertex v from G, then μ_G(2) <= 1 + |largest components의 vertices개수|(link)

-G:connected, U={v1,v2,..,vs}, s>=2, U:subset of V(G), G[U]:induced subgraph of G, (μ,x):eigenvalue, eigenvector

-if G[U]=K_s and N_G(v1) - U = N_G(v2) - U = ... = N_G(vs) - U and μ != d(vi) + 1 for any i=1,2,...,s

then x1 = x2 = ... = xs(link)

-if G[U]=sK_1 and N_G(v1) = ... = N_G(vs)

then x1 = x2 = ... = xs(link)

-if G[U]=sK_1 and for any 0<=t<=C(s,2) edges, G_t:=a graph obtained from G by adding any t edges among U,

then μ_G(1) = μ_(G_t)(1)(link)

-Let s>=2 new paths with equal length k, Pi:(v,v_ik,v_i(k-1),...,v_i1), i=1,2,...,s, are attached to G at v respectively, to form a new graph (G_(s,k)), let G_(s,k,t1,t2,...,tk) be the graph obtained from G_(s,k) by adding 0<=tj<=C(s,2) edges among {v1j, v2j, ..., vsj}. If Δ(G_(s,k)) >= s+3,

then μ_(G_(s,k,t1,t2,...,tk))(1) = μ_(G_(s,k))(1)(link1)(link2)

-G:connected, G_k:=the graph obtained from G by attaching a new path P:(v0,v1,v2,...,vk) at v0, where v1, v2,...,vk are distinct new vertices. Let X be a unit eigenvector of G_k crpd to μ_(G_k)(1). If μ_(G_k)(1)>=4,

then(link)

-for any 0<=i<=(k-1), |x_(i+1)| <= |x_i| and x_i * x_(i+1) <= 0 with = iff x_0 = 0

-x_0 = 0 iff x_k = 0

-G:connected, u,v:disticnt vertices of G, G_t:=the graph obtained from G by attaching t new paths (v,v_(i,1),v_(i,2),...,v_(i,qi)) (i=1,2,...,t) at v. Let X be a unit eigenvector of G_t crpd to μ_(G_t)(1) >= 4.

Let G_u be G_t - vv_(1,1) - vv_(2,1) - ... - vv_(t,1) + uv_(1,1) + uv_(2,1) + ... + uv_(t,1).(link)

-if |x_u| >= |x_v|, then μ_(G_u)(1) >= μ_(G_t)(1)

-if |x_u| > |x_v|, then μ_(G_u)(1) > μ_(G_t)(1)

 

 

 

 

 

-(Upper Bound of a(G))

-(n, δ, m)a(G) <= (n/(n-1)) * δ <= 2m/(n-1)(link)

-(κ, λ, δ)G:not graph-iso K_n이면 a(G) <= κ(G) <= λ(G) <= δ(G)

-(independent vertex)if G contains an independent set of k vertices, then a(G) <= n-k(증명은 bar(G)생각하면됨)

-if G:not graph-iso K_n, then a(G) <= n-2

-(m)if G:not graph-iso K_n, then a(G) <= ]]-1 + sqrt(1+2m)[[ for all m >= 2

(증명은 Variable Neighborhood search for...참고)

-(n, α) a(G) <= n - α(G)(증명은 complement와 subgraph생각)

-(genus(G)) if genus(G)=0, then a(G)<=4, with = iff G:K_4 or G:K_(2,2,2)

-

-(Lower Bound of a(G))

-(n, δ)2δ - n + 2 <= a(G)(link)

-(n, λ),a(P_n)*λ(G) <= a(G)

-(n, κ, Δ)2*cos(pi/n - cos(2pi/n))*κ(G) - 2*cos(pi/n * (1-cos(pi/n)))*Δ <= a(G)

-(n, D(G)) 4/(D(G)*n) <= a(G)

-(Upper Bound of a(bar(G))

-(n, α)a(bar(G)) <= n*(1 - 1/α(bar(G)), with = iff α|n and G has α개 components equal to K_(n/α)

-(Given m, te G s.t. a(G)=maximum)

-Given m>=2, te n, G s.t. G:connected and not graph-iso K_n with maximum a(G) and bar(G) is the disjoint union of K_1, K_2, K_3, P_3(여기서 maximum a(G)란, fixed m이고 n을 변화시킬 때를 가리킴, 단 G:not K_n이면서)

(a(G)는 n-2이거나 n-3이다.)

-(Given n, te G s.t. a(G)=maximum)

-Given n>=4, te (n-1)개의 m s.t. G:not graph-iso K_n with maximum a(G), order n

(여기서 maximum a(G)란, fixed m이고 n을 변화시킬 때를 가리킴, 단 G:note K_n이면서)

(그리고 처음의 [[(n-1)/2]]개는 a(G)=n-2, 나머진 a(G)=n-3

(증명은 위의 Variable..참고)

-(Upper Bound of μ_G(1))

-μ_G(1) <= max i~j |N_G(vi) U N_G(vj)| <= n(link)(link가 잘못된게 xj잡을 때, i와 adjacent한 것 중 잡아야)

-If G:connected, = holds iff ... link참고

-μ_G(1) <= q_G(1) <= max over i {d(vi)+m(vi)}(link)

-if G:connected, = holds iff G:regular bipartite or G:semiregular bipartite(link)

-μ_G(1) = n iff G:join of two graphs( ->방향 증명은, bar(G)생각)

-If G':subgraph of G, then μ_G'(i) <= μ_G(i) for any i

(edge를 지웠으면 weyl's inequality생각, vertex지우면 interlacing생각)

-G:connected bipartite일 때 μ_G'(1) = μ_G(1)  iff G'=G(link)

-About m_(G,L)

-if G:connected, n > 2, q(G)*2 = n,

then m_(G,L)([0,1))=q(G), m_(G,L)([1,2))=0, m_(G,L)(2)=1, m_(G,L)((2,n])=q(G)-1(link)

-If G:connected, n > 2, n > q(G)*2,

then m_(G,L)((2,n]) >= q(G)(link)

-(Connected Sum and m_(G,L))

-H:connected sum of G, K_(1,k-1)이면 m_(G,L)(k)=m_(H,L)(k)(link1)(link2)

(Reduction관점으로 보기 좋음, 특히 P_3나 P_2를 없애는 관점으로)

-H:connected sum of G, P_3, s.t. G의 1개 점과 P_3의 pendant와 이은 경우이면 m_(G,L)(1)=m_(H,L)(1)(link)

-H:connected sum of G, P_3, s.t. G의 1개 점과 P_3의 중간점을 이은 경우이면

m_(G,L)(1) <= m_(H,L)(1) <= m_(G,L)(1) + 2(link)

-(the number of Not Faria vectors)a:=m_(G,L)(1) - p(G) - q(G), S:induced subgraph of G by inner vertices(inner vertices란, V(G)에서 pendant랑 quasipendant 모두 빼고 남은 것)

-Lap(S) = Lap(G)의 inner vertices part - IMT

-a = nullity of Lap(S) = am(1) of Lap(G)의 inner vertices part

-a <= τ(G)

-a <= k where k:the number of components of S, if each of the k components of S satisfies *(link)

(*:complete graph or for any nonadjacent vi,vj, d(vi)+d(vj) >= n)

 

-(Upper Bounds for m_(G,L))

-m_(G,L)(n) <= [[δ/(n-Δ)]](link)

-if δ=0, then n must not egv of Lap(G)

-if δ=1, then am(n)=1 or 0

-σ(G) <= n - p(G)

-m_(G,L)([0,1)) <= γ(G)

-(Lower Bounds for m_(G,L))

-m_(G,L)([0,1)) >= q(G)(link)

-m_(G,L)((1,inf)) >= q(G)(link)

-m_(G,L)(1) >= p(G) - q(G)(pendants pair에 (1,-1)주고 나머진 0주는 방식으로 eigencomponent만들면됨) -m_(G,L)([δ,n]) >= α(G)

-m_(G,L)([0,Δ]) >= α(G)

-m_(G,L)([1,n]) >= n - γ(G)

-m_(G,L)((2,n]) >= [[l/2]], where l:the length of the longest path in G.(link)

-G:connected일 때, for V'={v1,v2,...,vk} of V(G), G'=G[V']=(V',E'), If E':consists of r pairwise disjoint edges이면

μ_G(1)+μ_G(2)+...+μ_G(k) >= d(v1) + d(v2) + ...+ d(vk) + k - r(link1)(link2)(link3)

-(Lower Bound of μ_G(1))

-k=1대입하면 μ_G(1) >= Δ + 1 (G:connected일 때, = iff Δ = (n-1)(link))

-μ_G(1) >= (n-1)/n * Δ(link)

-(Lower Bound of μ_G(1) + μ_G(2)), n >= 3일 때

-μ_G(1) + μ_G(2) >= Δ_1 + Δ_2 + 1

-if d(v1)=Δ_1, d(v2)=Δ_2, v1,v2:not adjacent, then μ_G(1) + μ_G(2) >= Δ_1 + Δ_2 + 2

-(Brouwer Conjectures)

-m + 1/2*(k^2 + k) >= μ_G(1)+μ_G(2)+...+μ_G(k)

-Holds for cograph(증명은 inductive 과정이 부등식을 만족함을 보이면 된다.)

-Holds for regular증명은 아래 참고

-(Lower Bound of μ_G(2))

-if G:connected and n>=3, then μ_G(2) >= Δ_2,

with = if G:K_(r,s) or G:tree with n:even and degree (n/2, n/2, 1,1,...,1)(link)

-(Necessary condition for μ_G(1)=(n-1))

-G:connected일 때, μ_G(1)=(n-1)이면 for any i, d(vi) <= n-3

-G:connected일 때, μ_G(1)=(n-1)이면 max i~j |N_G(vi) U N_G(vj)| = n

-G:connected일 때, μ_G(1)=(n-1)이면 D(G)=2 or 3

-μ_G(1)=(n-1) and a(G)=1이면 D(G)=D(bar(G))=3

 

-(Matrix Tree Theorem)t(G)=1/n * μ_G(1)*μ_G(2)*...*μ_G(n-1) = the cofactor of any element of Lap(G)

-G:disconnected iff t(G)=0 iff a(G)=0

-the number of connected components = the multiplicities of zero egv of Lap(G)

-n*t(G) = charP(Lap(G),x)의 x의 계수 = μ_G(1)*μ_G(2)*...*μ_G(n-1)(charP(MT)의 계수 성질 참고)

-(Using equitable partition){V1,V2,...,Vk}:equitable partition of G with d_(i,j), and B = (b_(i,j)) where b_(i,j)=(-d_(i,j)) for i != j, b_(i,i) = {sum over s d_(i,s)} - d_(i,i) for i=j, 일 때 egv of B는 egv of Lap(G)도 된다.(link)

(더 size낮은 matrix의 egv로써 더 size큰 Lap(G)의 egv를 구한다는 것이 의의)

-Lap(bar(G)) = DegMT(bar(G)) - AdMT(bar(G)) = {(n-1)*IMT - DegMT(G)} - {1 - IMT - AdMT(G)}

-spec(Lap(G))={n >= μ_G(1) >= ... >= μ_G((n)=0}일 때,

spec(Lap(bar(G))={n-μ_G(n-1) >= n-μ_G(n-2) >= ... >= n-μ_G(1) >= 0}, 즉 complement의 spec(Lap)도 알 수 있다.(link)

-About G1xG2, G1=(V1,E1,n1,m1,...), G2=(V2,E2,n2,m2,...)

-spec(Lap(G1xG2))={all possible sums of μ_G1(i) + μ_G2(k) for 1<=i<=n1, 1<=k<=n2}(link)

-a(G1xG2)=min{a(G1),a(G2)}

-About DS(G1,G2)

-Lap(DS(G1,G2)) = Lap(G1) + Lap(G2)

-a(G1)+a(G2) <= a(DS(G1,G2))

-About VD(G), V(G)=UUV

-a(G) <= min(a(G[U])+|V|, a(G[V])+|U|)

-(Same Neighborhoods)

-sub-vertex set V' having same set of neighbors Ν with |V'|=k and |Ν|=j 이면 j:egv of Lap(G) with am(j)=at least k-1

-sub-vertex set V'에서 몇몇 edges E'를 없애서 having same set of neighbors N with |V'|=k and |N|=j이고 spec(Lap((V',E'))={a1>=a2>=...>=aκ=0}일 때, j+ai:egv of Lap(G) for i=1,2,3,...,(k-1)이고 remaining egv는 same

(증명은 eigenvalue, eigenvector관련 equation잘잡아서)

-vi,vj:not adjacent, e=vivj를 추가했을 때, 역도 성립, 즉 egv가 +2만 됐다면 same neighbors(link)

-(Neighbor of several pendants)

-v1, v2:pendant이고 same neighbor를 갖는다면, μ( != 1)에 대응되는 eigencomponents는 same

-If (μ_G,x):(egv,egv) for Lap(G)이고 x_i:the largest eigencomponent of egv이고 x_j:the smallest eigencomponent of egv일 때 then min over k~i {x_k} >= (1 - μ_G)x_i and max over k~ i {x_k} <= (1- μ_G)x_i(link)

-(0 < μ_G < 1)If 0 < μ_G <1

-the eigencomponents corresponding to the neighbors of vi are the same sign of x_i, also the eigencomponents corresponding to the neighbors of vj are the same sign of x_j

-if vi, vj are not adjacent, then N_G(vi)교N_G(vj):empty

(위에서 결정한 vi, vj에 대해서임)

-if G:connected, then D(G)>=3

-If (μ_G(1),x):(egv,egv) for Lap(G)이고 x_i:the largest(modulus가) eigencomponent of egv이고 x_j:the second largest eigencomponent(modulus가) of egv일 때(link)

-d(vi) >= μ_G(1)/2

-if μ_G(1)=Δ_1 +Δ_2,

-d(vi)=Δ_1

-if Δ_1 != Δ_2, then vi~vj and |xj| >= (Δ_2 / Δ_1)|xi|

-G:connected이고 Δ_1 != Δ_2이면 μ_G(1) = Δ_1 + Δ_2 iff G:graph iso K_(1,n-1)(link)

-(Adding an pendant edge)If we add an pendant edge e to G, then a(G+e) <= a(G)

-(Joining K_1)(link)

:If G'=GVK_1, then

μ_G'(1) = n+1 >= μ_G'(2) = μ_G(1) + 1 >= μ_G'(3) = μ_G(2) + 1 >= ... >= μ_G'(n) = μ_G(n-1) + 1 >= μ_G'(n+1) = 0

(증명은 bar(G') = bar(G) + K_1 이용)

-(Joining General G)

:{μ_G1(1) >= μ_G1(2) >= ... >= μ_G1(n1) = 0}, {μ_G2(1) >= ... >= μ_G2(n2) = 0}일 때 G1VG2의 spectrum of laplacian은 {n1+n2, n1+μ_G2(j), n2+μ_G1(i), 0 | i=1,...,n1-1, j=1,...,n2-1}(link)

-a(G1VG2) = min (n1+a(G2), n2+a(G1))

-(subdividing some edges)

Let P:(v1,v2,...,vk):internal path(정의는 link참조)

Let G' be a graph obtained from G by subdividing some edge of P(1개 edge만 subdividing)

then μ_G'(1) < μ_G(1)(link1)(link2)

-(Subdividing a general edge)

Let G' be a graph obtained from G by subdividing one edge of G

then a(G') <= a(G)(link1)(link2)

-(Identifying two verices)

Let G1, G2, v1 in G1, v2 in G2, G:=formed by identifying v1 and v2 into v1

then a(G)<=min(a(G1),a(G2))(link)

-About Lnergy(G)

-Lnergy(G)

= 2* (sum from i=1 to i=σ μ_G(i)) - (4*m*σ)/n(link)

= max over 1<=i<=(n-1) {2 * (sum from j=1 to j=i μ_G(j)) - 4*m*j/n}(link)

-(Lower Bound of Lnergy(G))

-if G:connected, then Lnergy(G) >= 2 * (1 + Δ - d(G)), with = iff G:K_(1,n-1)(link1)(link2)

-(Upper Bound of Lnergy(G))

-if m >= n/2, then Lnergy(G) <= 4m - 2Δ - 4m/n + 2, with = iff G:K_(1,n-1) or K_(1,Δ) + bar(K_(n-Δ-1)(link)

-Lnergy(G) <= 4m*(1 - 1/n), with = iff G:K_2 + bar(K_(n-2))

-(Lower Bound of Lnergy(G) + Lnergy(bar(G)))

-Lnergy(G) + Lnergy(bar(G)) >= 2*(n-1), with = iff G:K_n or G:bar(K_n)

-Lnergy(G) + Lnergy(bar(G)) >= 2*(n-1 + Δ - δ)(link1)(link2)

, with iff G:K_n or G:bar(K_n) or G:K_(1,2) or G:(K_2 + K_1) V K_1

-(Upper Bound of Lnergy(G) + Lnergy(bar(G)))

-Lnergy(G) + Lnergy(bar(G)) <= n*sqrt(n^2 - 1)

-Lnergy(G) + Lnergy(bar(G)) <= 8m - 4Δ +2n -12m/n, with = iff G:K_(1,n-1)(link1)(link2)(link3)

-(Extremal Lnergy among Connected Threshold Graphs with n:fixed >= 5)

-PA_(n,]](2n+1)/3[[):has the maximal Lnergy among connected threshold Graphs with n:fixed > 5

-About Specific Cases

-G:r-regular이면 spec(Lap(G)) = {r - λ_G(1), r - λ_G(2), ..., r - λ_G(n)}

-spec(Lap(K_n))={n,n,n,...,n,0}

-spec(Lap(K_(1,n-1))={n,1,1,...,1,0}

-spec(Lap(P_n))={2 - 2cos((pi*k)/n), k=0,2,...,n-1}

-spec(Lap(C_n))={2 - 2cos((2*pi*k)/n), k=n-1,n-2,...,0, not ordered임}

-spec(Lap(K_(r,s))={r+s, r, r, ..., r,s,s,...,s,0}, r이 s-1, s가 r-1개

-spec(Lap(PA(n,w))={n,w,w,...,w,1,1,...,1,0}, w가 w-2개, 1이 n-w개
-μ_(r,s)-semiregular bipartite(1) = r+s(link개)

-about Tree(G:tree)

-if μ:integral egv of Lap(G), μ >= 2, then(link)

-μ | n

-am(μ) = 1, 즉 m_(G,L)(μ)=1 for G:Tree, μ>=2 if μ:eigenvalue of G

-no coordinate of egv corresponding to μ is zero

-(Lower bound of μ_G(1))

-if te v s.t. e(v)<=2,

then μ_G(1) >= 1/2 * {(d(v)+m(v)+1) + sqrt((d(v)+m(v)+1)^2 - 4(d(v)m(v)+1))

, with = iff for any vi, vj s.t. vi~v and vj~v, d(vi)=d(vi)(link1)(link2)

-μ_G(1) >= max over i 1/2 * {(d(vi)+m(vi)+1) + sqrt((d(vi)+m(vi)+1)^2 - 4(d(vi)m(vi)+1))

-μ_(P_n)(1) <= μ_(G)(1) <= μ_(K_(1,n-1))(1) = n with left = iff G:graph-iso P_n, with right = iff G:graph-iso K_(1,n-1)(link1)(link2)

-if x:Fiedler vector, then exactly one of the following two cases occurs:

(A)

-No entry of x is 0

-te! vi~vj s.t. xi > 0 and xj < 0

-any p(vi,~) which doesn't contain vj, entries are inc

-any p(vj,~) whcih doesn't contain vi, entries are dec

(B)

-te zero entries of x

-U={vi s.t. xi=0}, then G[U]:connected

-te! vi s.t. xi=0 and vi~vj with xj:nonzero(vj가 unique하진 않을 수 있음)

-any path p(vi,~), entries are either inc, dec, identically 0

(We say T is type-(I) if T satisfies (B), We say T is type-(II) if T satisfies (A))

-Lap(G) - vi is invertible for any vi(using matrix-tree theorem)

-the (i,j)-entry (Lap(G) - vk)^(-1) = the number of edges of G which are on both the path from vi to v and the path from vj to v

-(Lower Bound of μ_G(2) for tree)

-if n>2(link1)(link2)(link3)(link4)

-if Δ_1 ~ Δ_2, then μ_G(2) >= Δ_2, with = if(not iff) G:T1(Δ_1 - 1,Δ_2 - 1)

-if Δ_1, Δ_2 are not adjacent, then μ_G(2) >= {(Δ_2 + 1) + sqrt((Δ_2+1)^2 - 4)}/2, with = if(not iff) G:T2(Δ_1 - 1, Δ_2 - 1)

-if n>2 and Δ_1 = Δ_2 = μ_2(G), then G:T1(d-1,d-1)(link)

-(Lower Bound of μ_G(1)+μ_G(1) for tree) n >= 3

-if d(v1)=Δ_1, d(v2)=Δ_2 and vi~vj, then

μ_G(1) + μ_G(2) >=

-1/2 * {Δ_1 + 2*Δ_2 + m(v1)+1) + sqrt((Δ_1 + m(v1) + 1)^2 - 4*(Δ_1 * m(v1) + 1))}

-Δ_1 + 1/2 * {Δ_2 + 2 + sqrt((Δ_2 +2)^2 - 8))}(link1)(link2)

-if d(v1)=Δ_1, d(v2)=Δ_2 and vi,vj:not adjacent, then

μ_G(1) + μ_G(2) >=

-1/2 * {Δ_1 + Δ_2 + m(v1) + 2 +sqrt((Δ_2 + 1)^2 - 4) + sqrt((Δ_1 + m(v1) +1)^2 - 4*(Δ_1 * m(v1) + 1))}

-Δ1 + 2 + 1/2 * {sqrt((Δ_2 - 1)^2 + 4 * |N(v1)교N(v2)|) + sqrt((Δ_2 + 1)^2 - 4 * |N(v1)교N(v2)|)}(link1)(link2)

-(Upper Bound of a(G) with n >= 6)

-if G:not K_(1,n-1), then a(G) < 0.49(증명은 tree with 6 vertices중에서 가장 큰 a(G)=0.48...near star, 그리고 adding pendant edges 생각)

-(Upper Bound of a(G) with D(G))

-a(G) <= a(P_(D(G)+1)), 즉 diameter가 같은 path의 a(G)가 최대이다. tree의 경우

-(Lower Bound of a(bar(G)))

-(n, α) a(bar(G)) > n - 2*α(T)

-(Upper Bound of μ_G(k) for tree)

-μ_G(k) <= [[n/k]] for k=1,2,3,...,n

-About T1(a,b), G=T1(a,b)

-0 < a(G) < 1, and other μ >= 1

-for 1 <= a <= (n-2)/2, fixed n, a(G):strictly decreasing of a

(즉, n이 고정되어 있을 때, 양쪽으로 vertex가 골고루 있을 수록 a(G)가 낮다.)

(증명은 Ordering trees by algebraic connectivity, Grone, Merris참고)

-About TZ(k), G=TZ(k)

-m_(G,L)(k) = 1, eigencomponents가 pendant는 1, quasipendant는 -1, center는 1 - (k)^2

-About m_(T,L)

-n>=2이고 for any μ, m_(T,L)(μ) <= p(T) - 1(link)

-m_(T,L)((0,2)) >= [[D(G)/2]](link)

-m_(T,L)((2,inf) >= [[D(G)/2]](link)

-About sLap(G), egv of sLap(G), q

-x^(m-n) * charP(sLap(G),x) = charP(AdMT(L(G)),x-2)(link)

-(Factoring sLap(G))sLap(G) = IcMT(G) * ct(IcMT(G))

-sLap(G):psd

-q_G(i)>=0, for all i

-(Interlacing, deleting one edge)G'=G-e일 때, q_G(1)>=q_G'(1)>=q_G(2)>=q_G'(2)>=...q_G(n)>=q_G'(n)>=0

(증명은 line graph와의 관계+interlacing, deleting vertex, in AdMT사용)

-(Same Neighborhoods)

-sub-vertex set V' having same set of neighbors Ν with |V'|=k and |Ν|=j 이면 

j:egv of sLap(G) with am(j)=at least k-1

-About perm(sLap(G))

-sd(G) = the multiplicity of perm(x*IMT - sLap(G))

-G has pendant stars with more than one pendant vertex iff 1 is a root of perm(x*IMT - sLap(G))

-About q_G(1)

-(Upper Bound of q_G(1)

-μ_G(1) <= q_G(1) <= max i {d(vi)+m(vi)}(증명은 -μ_G <= max i {d(vi)+m(vi)}와 유사)

-if G:connected, then right = hold iff G:regular or semiregular bipartite iff d(vi)+m(vi):fixed(link)

(증명을 보면, G:bipartite이면 spec(sLap(G))=spec(Lap(G))임을 알 수 있다. (usim이라), 그리고 역도 성립)

-if G:connected, then left = hold iff G:bipartite

(따라서 left = and right = holds iff G:regular bipartite or semiregular bipartite)

-if G:connected, then q_G(1) <= Δ_1 + Δ_2, with = iff G:regular or G:graph-iso K_(1,n-1)

-(Lower Bound of q_G(1))

-q_G(1) >= Δ + 1

-if G:connected, then = hold iff G:graph-iso K_(1,n-1)

-About q_G(2)

-(Lower bound of q_G(2))

-if Δ_1 ~ Δ_2, then q_G(2) >= {Δ_1 + Δ_2 - sqrt((Δ_1 - Δ_2)^2 + 4)}/2

-if Δ_1, Δ_2 are not adjacent, then q_G(2) >= Δ_2

-q_G(2) >= Δ_2 - 1, if = holds, then Δ_1=Δ_2 and corresponding vertices are adjacent

(왜냐하면 Δ_2 >= {Δ_1 + Δ_2 - sqrt((Δ_1 - Δ_2)^2 + 4)}/2 >= Δ_2 - 1)

-if G:connected, then q_G(2) >= d(G) - 1 with = iff G:graph-iso K_n

-if G:connected, then q_G(2) >= δ - 1 with = iff G:graph-iso K_n

-if G:connected and n>=4, G:not graph iso K_n, then q_G(2) >= a(G)

with = iff

-G:K_(1,n-1)

-G:K_(1,3,3)

-G:K_(n-δ, n-δ, ..., n-δ), complete p-partite graph, n-δ>=2

-G:K_(1,1,...,1,2,2,...,2), complete (k+t)-partite graph, 1이 k개, 2가 t개

-(Upper bound of q_G(2))

-If G:connected and n>=3, then q_G(2) <= n + δ - 3, with = iff G:graph-iso Ki_(n,n-1)

-If G:connected, then q_G(1) - q_G(2) <= n, with = iff G:graph-iso K_n

-If Δ_2 = n-1, then q_G(2) = n-2

-(Lower Bound, Related with the index)

-n>2, G:not K_3 and not K_4이면 1- sqrt(n-1) <= q_G(2) - λ_G(1), with = G:K_(1,n-1) or K_5

-About q_G(n)

-If G:connected, q_G(n) < δ(G)(증명은 Rayleigh에 (0,0,...,1)넣어서)

-G:connected and non-bipartite with q_G(i):integer for all i이면 G has no pendant vertices.

-G:connected일 때, q_G(n) = 0 iff G:bipartite(증명은 incidence로 표현해서)

-G:connected and te vi~vj s.t. N_G(vi) - {vj} != N_G(vj) - {vi}이면, q_G(n) < (d(vi) + d(vj) - 2)/2

-About Specific Cases

-G:r-regular일 때

-G:connected이면 q_G(n) <= r-1 with = holds iff G:K_n

-sLap(K_n)={2n-2, n-2, n-2, ..., n-2}

-spec(sLap(P_n))=spec(Lap(P_n))

-spec(sLap(C_n))={2 + 2cos((2*pi*k)/n), k=n-1,n-2,...,0, not ordered임}

-sLap(CS(n,w))...link참고

-sLap(K_(n-δ,n-δ,...,n-δ), n-δ가 p개) 

= {2δ, δ,..., δ, (n-δ)(p-2), (n-δ)(p-2), ..., (n-δ)(p-2), δ:p(n-δ-1)개, (n-δ)(p-2):p-1개}(link)

-About Tree(G:tree)

-if n>=4, then q_G(1) - q_G(2) <= n-1, with = iff K_(1,n-1)

-Graph distance