수학정리(Applications, Distance, Index)

*Distance, Index

-about W(G)

-W(G) 

= sum over k>=1 (k*d(G,k))

= [sum over all i,j DistMT(G)_(i,j)] * 1/2

-about MTI(G)

-MTI(G)

=1-Zagreb(G) + DD(G)

=1-Zagreb(G) + sum over entries [AdMT(G)*DistMT(G)]

=sum over all entries [AdMT(G)]^2 + sum over all entries [AdMT(G)*DistMT(G)]

-For G:tree

-MTI(G) = 4*W(G) - (n-1)(n-2) + 2*(# of paths of length 2)

-about DD(G)

-DD(G)

=sum over entries [AdMT(G)*DisMT(G)]

-For G:tree

-DD(G) = 4*W(G) - n(n-1)

-about GG(G)

-Among G with n vertices, K_n is the graph with minimum GG(G)

-Among bipartite G with n vertices, K_([n/2], ]n/2[) is the graph with maximum GG(G)

-Among T with n vertices, P_n is the tree with minimum GG(T)

-Among T with n vertices, K_(1,n-1) is the tree with maximum GG(T)

-about NGG(G)

-If G:bipartite, then GG(G)=NGG(G)*sqrt(n-2)

-lim n->inf NGG(P_n) = pi

-about RD(G), max-RD(G), HM(G)

-max-RD(G) <= HM(G) <= RD(G), by simple calculation

-(Hansen)χ(G) <= 2*RD(G) with = iff G:complete, possibly with some additional isolated vertices

-(Deng)χ(G) <= 2*HM(G) with = G:complete, possibly with some additional isolated vertices

-(Wu, Yan, Yang)If G without isolated vertices, then col(G) <= 2*RD(G) with = iff G:K_n

-(Wu, Elphick)If G without isolated vertices, then

col(G) <= 2*max-RD(G) with = iff G is formed by K_k and K_(1,n-k) identifying one vertex in K_k with the center of K_(1,n-k) for some k

χ(G) <= 2*max-RD(G) with = iff G is formed by K_k and K_(1,n-k) identifying one vertex in K_k with the center of K_(1,n-k) for some k

χ_l(G) <= 2*max-RD(G) with = iff G is formed by K_k and K_(1,n-k) identifying one vertex in K_k with the center of K_(1,n-k) for some k

col(G) <= 2*HM(G) with = iff G is K_n

-(Tang)aχ(G) <= 2*RD(G)

-G:connected일 때 d(vi)+m(vi):fixed for all iff G:regular or G:semiregular bipartite(link)

-max{d(vi)+m(vi)} <= (2m/n-1) + (n-2) with equality iff G graph-iso S_n or G graph-iso K_(n-1) U K_1(link1)(link2)

-(Upper Bound of 1-Zagreb(G))

-G:connected일 때 1-Zagreb(G) <= m*max{d(vi)+m(vi)}

with equality iff G:regular or G:semiregular bipartite(link)

-1-Zagreb(G) <= m*{2m/n-1 + (n-2)/(n-1)*Δ +(Δ-δ)*(1 - Δ/(n-1))}

with equality iff G:K_(1,n-1) or regular or K_(Δ+1) with n-Δ-1 isolated vertices

-1-Zagreb(G) <= 2m*(2m+(Δ-δ)(n-1))/(n+(Δ-δ)) 

with equality iff G:regular or K_(Δ+1) with n-Δ-1 isolated vertices, (증명은 Maximizing the sum of...참고)

-1-Zagreb(G) <= 2m*(Δ-δ) - n*Δ*δ

with equality iff G has only two type of degree Δ, δ(증명은 Maximizing the sum of...참고)

-1-Zagreb(G) = sum over i sum over j (Adj)^2_(i,j)(link)

-About RdMT(G)

-(Lower Bound of SpecR(RdMT(G)))

-G:connected, n>=2이면 specR(RdMT(G)) >= 2m/n + 1/(n*D(G)) * [n(n-1)-2m] + 1/(n*Δ^2) * [(1-1/D(G))*sum over all i d(vi)^3 - 4m^2/D(G) + n/D(G) * 1-Zagreb(G) - 2*(1 - 1/D(G))*2-Zagreb(G)]

with = iff G:K_n or G:regular with D(G)=2(link)