[수학]All about algebraic connectivity, a(G)

*Class of Graphs and their a(G) in terms of graph invariants

K_n

-a(G) = n

K_(a,b)

-a(G) = min(a,b)

P_n

-a(G) = 2 - 2cos(pi/n)

C_n

-a(G) = 2 - 2cos(2pi/n)

W_n

-a(G) = 3 - 2cos(2pi/n)

S_n

-a(G) = 1

S_n^*(K_(1,n-2)의 pendant vertex와 P_2의 한 점을 identifying)

-a(G) < 0.5(직접 characteristic polynomial 구해서)

Q_n

-a(G) = 2

X(Z_n,C)

-C={1,n-1}

-a(G) = 2 - 2cos(2pi/n)

-C={1,2}

...

J(v,k,i)

-v>=2k, i=(k-1), johnson,

-v>=2k, i=0, kneser

-J(5,2,0), petersen, a(G) = 2

 

CS(n,w)

-a(G) = n - w

PA(n,w)

-a(G) = 1

Ki(n,w)

ST(a,b)

T(n,a,b)

 

multipartite

split graph

difference graph

cograph

threshold graph(=maximal graph)

r-regular

(r,s)-semiregular

caterpillar, CTPL

binary tree

 

 

 

------------------------------------------------------------------------------------------------------------------------

*Graph Invariants

 

V와 V의 subset의 개수

n

τ(G)

γ(G)

α(G)

p(G)

q(G)

 

E와 E의 subset의 개수

m

Τ(G)

ν(G)

 

degree관련

δ(G)

d(G)

Δ(G)

1-Zagreb(G)

2-Zagreb(G)

decdseq(G)

tr(G)

 

path, length관련

r(G)

D(G)

md_G

d(G,k)

W(G)

H(G)

TW(G)

HW(G)

RCW(G)

MTI(G)

DD(G)

 

topological관련

genus(G)

 

subgraph관련

sd(G)

g(G)

G(G)

ω(G)

t(G)

 

Tree관련

Type 1 or Type 2

 

Connectivity관련

connectivity

# of components

cutvertex

bridge

κ(G)

λ(G)

 

Color관련

χ(G)

 

Homomorphism관련

Aut(G)

------------------------------------------------------------------------------------------------------------------------

*Related bounds for a(G), G:connected

 

a(P_n) <= a(G) <= n (Fiedler 1973)

 

a(G)<=κ(G)<=λ(G)<=δ(G), (Fiedler 1973)(G:K_n일땐 성립안할 수 있음, 조심)

처음 <은 path생각, 두번째 <은 triangle 2개를 1개꼭지점을 common, 세번째 <은 T1(a,b)에다가 양 끝에 path을 attach한 것

처음 = iff G=G1VG2, where G1:disconnected of order n - κ(G), G2:of order κ(G) with a(G2) >= 2 * κ(G) - n (Kirkland, Molitierno, Neumann and Shader 2002)

 

if G:not K_n, then a(G) <= [[-1 + 2 * sqrt(1 + 2 * m)]] (Belhaiza, Abreu, Hansen and Oliverita 2005)

 

a(G) >= 4/(n * D(G)) (Mohar 1992)

 

a(T) <= 2 * (1 - cos(pi/(D(T)+1))) (Grone, Merris and Sunder 1990)

 

if T:planar, then a(G) <= 4, with = iff G=K_4 or K_(2,2,2)

if n >= 6 and G:non-isomorphic to K_n, then a(G) < 0.49

a(G) <= a(P_(D(G)+1))

 

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

 

------------------------------------------------------------------------------------------------------------------------

*Main Theory of matrix, or Fiedler vector, etc

 

y_i = 0 and i~j and y_j > 0이면 te k s.t. i~k and y_k < 0

 

y_i > 0이면 te j s.t. i~j and y_j < y_i

 

v:cut vertex, G - k = G_0+G_1+...+G_r일 때

y_k > 0이면 te! G_j s.t. contains a vertex(vertices) with negative valuation이고 나머지 components의 y값은 y_k보다 큼

y_k = 0이고 te G_j s.t. containing both positive and negative이면 te! G_j이고 나머지 components는 다 0

y_k = 0이고 te no G_j s.t. containing aboth positve and negative이면 각 G_k들은 모두 only positive or only negative or only zero

(y_k < 0인 경우도 결국 설명됨, eigenvector니까)(Fiedler 1975)

 

G:connected with at least one cut vertex일 때 다음 2가지 중 1가지는 반드시 성립(Fiedler 1975)

(a)

te! B0 in which contains both positively and negatively.

Each other block has either vertices with positive only, negative only, or zero only

Every pure path P starting at B0 and containing just one vertex k in B0 has the property that the valuations at the cut vertices contained in P form either an increasing, decreasing, or zero sequence along this path.(pure path란 각 block의 articulation을 0,1번만 지나는 path)

a(G) is simple

(b)

No block of G contains both positive and negative.

te! j which has zero and is adjacent to a nonzero and j is a cut vertex.

Each block contains either positive only, negative only, or zero only.(zero랑 positive가 같이 있는 경우도 없는!)

Every pure path P starting at j has the property that the valuations at the cut vertices contained in P form either an increasing, decreasing, or zero sequence along this path.

the induced subgraph from zero is connected

 

위의 내용을 Tree에 적용하면(Fiedler 1975)

(a)

all valuations are nonzero

te! ij s.t. yi >0 and yj < 0

any path from i not containing j 는 increasing concave down(위로 볼록)

any path from j not containing i 는 decreasing concave up(아래로 볼록)

a(G):simple

(b)

te! i s.t. yi = 0 and i is adjacent to nonzero

any path from i 는 increasing concave down(위로볼록), decreasing concave up(아래로 볼록), or identically zero.

 

T:tree일 때

L_k:invertible,

inv(L_k)_(i,j) = sum over all edge in P_(i,j) 1/w(edge)

, where P_(i,j):the set of edges of T which are simultaneously on the path from i to k and on the path from j to k, w:weight

inv(L_k) permutationally similar to a block diagonal matrix in which each block is positive and correponds to a branch at k.(즉 Lap(T)에서 branch에 해당하는 submatrix의 inverse가 됨)(Kirkland, Neumann, Shader, 1996)

 

T:tree일 때

T:type I with characteristic vertex k iff te two or more Perron branch of T at k.

Moreover, a(T) = 1/specR(inv(L_k)), where L_k:Lap(G)에서 kth row와 kth column제거한 것. (Kirkland, Neumann and Shader 1996)

 

T:tree, i~j일 때

T:type II with characteristic vertices i,j iff te 0 < eps < 1 s.t. specR(M1 - eps * J) = specR(M2 - (1 - eps) * J)

Moreover, a(T) = 1/specR(M1 - eps * J) = 1/specR(M2 - (1 - eps) * J) and the branch at i containing j is the unique Perron branch at i and the branch at j containing i is the unique Perron branch at j

where M1:bottleneck matrix for the branch at j containing i, M2:bottleneck matrix for the branch at i containing j. (Kirkland and Neumann 1997)

 

T:tree일 때

T:type I iff te! i s.t. te two or more Perron branches at i

T:type II iff for any i, te! Perron branch at i(Kirkland, Neumann and Shader 1996)

 

T:tree type I with characteristic vertex i이고 am(a)=k이면 i has exactly k+1 Perron branches(Grone and Merris 1987)

 

T:tree, i:non-characteristic vertex이면 te! Perron branch at i and the branch contains all of the characteristic vertices of T(Kirkland, Neumann and Shader 1996)

 

For positive integers k1,k2,...,km, form an tree T by taking a vertex x and making it adjacent to the root vertices of both T(k1,k2,...,km) and T(km,...,k1). Then T is a type I tree with characteristic vertex x.

where T(k1,k2,...,km):한 vertex x에서 k1개 pendant붙이고 각 pendant에 k2개 pendant붙이고...km까지(Kirkland 1999)

 

T:tree, B:branch at i which does not contain all of the characteristic vertex(vertices) of T. Form T' from T by replacing the B by some other branch B' at i.

M:the bottleneck matrix of B, M':the bottleneck matrix of B'

if M << M', then

a(T') <= a(T)

the characteristic vertices of T' are either on the path joining the characteristic vertices of T to i, or they are located on B'(Kirkland, Neumann 1997)

(A << B means te P,Q s.t. P:Permutation MT, Q:permutation MT, if the order of A < the order of B, PArt(P) is entrywise dominated(<=) by a psubMT of QBrt(Q), if the order of A = the order of B, PArt(P) is entrywise dominated by QBrt(Q) with at least one strictly inequality)

 

the corollaries

위의 내용을 adding a pendant vertex로 보면

a(T') <= a(T)

the characteristic vertices of T' lie on the path between the characteristic vertices of T and the new pendant vertex.(Kirkland, Neumann 1997)

 

위의 내용을 change B to path로 보면

Form T' from T by replacing B(the order of B is k) by P_k with i adjacent to the end of P_k, then

a(T') <= a(T)

 

위의 내용을 change B to star로 보면

Form T' from T by replacing B(the order of B is k) by K_(1,k-1) with i adjacent to the center of the star, then

a(T) <= a(T')

 

위의 내용을 subtree인 경우를 보면

Any subtree T' of T, a(T') <= a(T)

 

T:type I with characteristic vertex i, d(i)=d, B1,B2:Perron branches, B3,B4,...,Bd:other branches, |B3UB4U...Bd|=k

Let H:any graph on k vertices

Form G from T by discarding B3,B4,...,Bd and adjoining i to some or all vertices of H.

Then a(G) <= a(T) (Grone and Merris 1990)

 

 

 

 

------------------------------------------------------------------------------------------------------------------------

*Graph Perbutation and related theorems

G -> G'=L(G)

G -> G'=bar(G)

a(G') = n - μ_G(1)

G -> G'=T(G)

(G,v) -> G'=G-v

a(G') >= a(G) - 1

(G,v) -> G'= (G-v and then +e), smoothing of v

(G,v,k,l), k >= l >= 1, -> G' = v에서 길이가 k, l인 path를 attaching, G'' = v에서 길이가 k+1, l-1인 path를 attaching

a(G') >= a(G'') (Guo 2010)

(G,v) -> G' = adding some edges among pendent vertices at v

if a(G) != 1, then a(G) = a(G') (Shao, Guo and Shan 2008)

(G,U,V) -> VD(G) = (G[U], G[V])

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

(G,v,u1,u2,...,uk), each ui not adjacent to v -> G' = G+H, where V(H)=(v,u1,...,vk), v~ui for any i

if G' not K_n, then a(G') - a(G) <= k - eps where eps is the smallest positive root of

"d(v) * eps * (k - eps) - (1 - eps)^2 * (k - 1 - eps)^2" (Kirkland, Oliveira and Justel 2011)

(G,e) -> G'=subdivision of e

a(G') <= a(G)

(G,e) -> G'=contraction of e

(G,e) -> G'=G-e

a(G') <= a(G)

(G,e) -> G'=G+e,

a(G') >= a(G)

(G,v,e) -> G'=G+pe

if G, G':both trees, then a(G') <= a(G)

G1, G2 -> G1+G2

a(G1+G2) = 0

G1, G2 -> G1VG2

a(G1vG2) = min(a(G1)+n2, a(G2)+n1)

G1, G2 -> G1xG2

a(G1xG2) = min(a(G1), a(G2))

G1, G2 -> EDP(G1,G2)

G1, G2 -> DS(G1,G2)

a(DG(G1,G2)) >= a(G1) + a(G2)

(G1,u), (G2,v) -> G = identifying u and v

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

(G1,u), (G2,v) -> G' = (G1+G2) + (uv), G'' = G' and then identifying u and v(say u) and then +(uw),

a(G') <= a(G'') (Guo 2010)

(G,u,v) with some nbds of v(Specifically, {v1,v2,...,vs}:subset of N(v) - N(u) and any vi is different from u), G' = G - vv1-vv2-...-vvs + uv1 + uv2 + ... + uvs

if y(u)=y(v), then a(G') <= a(G)(Lama 2016)

-----------------------------------------------------------------------------------------------------------------------

*Extremal Problems

 

(Among tree, n, D(G))a(T(a,b,c)) is the minimum where a = ]](n-c)/2[[, b = [[(n-c)/2]], c = D(G) - 1(Fallat and kirkland 1998)

 

 

 

 

 

 

 

 

 

------------------------------------------------------------------------------------------------------------------------

*Problems

(Among Tree)one edge subdivision always make a(G) decreasing.

------------------------------------------------------------------------------------------------------------------------

읽었는 논문

 

읽을 논문