수학정리(Applications, Basic Graph Theory)

*Basic Graph Theory

-G:simple graph, n:order of G, m:size of G, t:the number of triangle of G

-invariant map의 예:order, size, δ(G), d(G), Δ(G), g(G), G(G), components 개수, D(G), r(G), central, 

-sum of all degree = 2m

-the number of vertices of odd degree is always even

-d(G) = 2m/n

-r(G)<=D(G)<=2r(G)(link)

-Every G with at least one edge has a subgraph G' s.t. 2*δ(G') > m(G') >= m(G) 

-Every G contains a path of length δ(G)

-Every G contains a cycle of at least length δ(G)+1(if δ(G) >= 2)

-Every G containing a cycle satisfies g(G) <= 2*D(G) + 1

-if r(G) <= k and Δ(G) <= d, then n <= d * (d-1)^k * 1/(d-2) 

-n >= n_0(δ(G), g(G))

-if δ(G) >= 3, then g(G) < 2 * log_(2)(n)

-if m(G) >= m >= 2 and g(G) >= g, then n >= n_0(m,g)(Alon, Hoory, and Linial 2002)

-(Mader)if m(G) >= 4k, then G has a (k+1)-connected subgraph G' s.t. m(G') > m(G) - 2k(link1)(link2)

-D(G)>=3 이면 D(bar(G)) <= 3(link)

-a_k:dec seq of positive integers with n terms일 때

-a_k:graphical이면

-a_1 <= n-1

-sum over k a_k는 even

-for b_j s.t. a_k majorize b_j, b_j:graphical

-(Characterization of graphical seq, Havel-Hakimi Theorem)

-a_k:graphical

iff a_k의 a_1을 없애고 a_2부터 총 a_1개의 terms에 -1해서 얻은 seq도 graphical

(위 thm을 반복해서 적용, 그러다 negative값이 나오면 not graphical 혹은 graphical한거나오면 됨)

iff sum from i=1 to i=tr(Tb(G)) (a_i + 1) <= sum from i=1 to i=tr(Tb(G)) conj(a_k)_i

(for each i=1,2,...tr(Tb(G)), decdseq(G)_i + 1 = conj(decdseq(G))_i iff G:threshold)

-given fixed n, the graph with the smallest D(G) is K_n, the quantity = 1

-given fixed n, the graph with the smallest md_G is K_n, the quantity = 1

-given fixed n, the graph with the largest D(G) is P_n, the quantity = n-1

-given fixed n, the graph with the largest md_G is P_n, the quantity = (n+1)/3

-G has two vertex having the same degree(link)

-G:self-complementary이면 4|n or 4|(n-1)(link)

-G:bipartite iff G has no odd cycles

-About α(G)(V, independence), τ(G)(V, covering), v(G)(E, matching), γ(G)(V, domination)

-α(G)+τ(G) = n

-ν(G) <= τ(G)

-G:odd cycle이면 ν(G) +1 = τ(G)

-G:even cycle이면 ν(G) = τ(G)

-ν(G) = α(L(G))

-G:isolated-free

-γ(G) <= ν(G)

-G has a minimum dominating set U in which every member u in U has epn(u,U)

-G has a star forest F=(S_n1,...,S_nγ) s.t. every v in V(G) belongs to exactly one star, and the centers of the stars form a minimum dominating set.

-About DfG

-Bipartite

-

-About Split Graph

-About cograph, G:cograph

-any cograph may be constrcted using complement and disjoint union

-cograph is closed under complement, finitely many disjoint union

-bar(G):cograph

-G1:cograph, G2:cograph이면 G1+G2도 cograph

-any connected cograph is a join of two graphs(왜냐하면 G1VG2 = bar(bar(G1) + bar(G2))

-Any Cograph is L-integral

-About Threshold Graph

-G:split and cograph, then G:threshold graph

-(Criteria of threshold)if G:threshold, then decdseq(G)_(i+1) = conj(decdseq(G))_i for all i > tr(Tb(G))

-(Characterization of Threshold Graph)G:Threshold

iff G:obtained from K_1 by a seq of operations (i) add an isolated vertex, or (ii) take the complement

iff G:obtained from K_1 by a seq of operations (i) add an isolated vertex, or (ii) add an dominating vertex

iff decdseq(G) is not majorized by any other decdseq

iff for each i=1,2,...tr(Tb(G)), decdseq(G)_i + 1 = conj(decdseq(G))_i

-About genus

-(Euler's Formula)G:connected with genus(G)=0이면 n - m + r = 2, where r:the number of region from G

(증명은 induction on m, G:tree일때와 아닐 때로 구분)

-if G with genus(G)=0

-m <= 3n - 6(즉 no crossing edges로 그래프 그릴려면 m이 그렇게 클 수가 없음)

-δ <= 5

-if G:maximal planar

-every region is bounded by three edges

-every vertex v is the center of a wheel subgraph induced by v and all vertices adjacent to v.

-δ >= 3

-(Kuratowski's Theorem, Criteria of Planar)

:G가 planar iff G does not contain K_5, K_(3,3), or any subdivision of K_5, or K_(3,3) as a subgraph.

 

 

 

 

-About subgraph

-Every graph G with at least one edge has a subgraph G' with δ(G') > d(G')/2 >= d(G)/2(link)

-G:eulerian iff G:connected and d(vi):even for all i

-for r:even, G:r-regular이면 G has a 2-factor

-t(G)=t(G-e) + t(G with e) for any edge e

-About generated graph

-bar(K_p)Vbar(K_q)=K_(p,q)

-Every topological minor of G is minor of G(역 성립 안함)

-bar(G1+G2) = bar(G1) V bar(G2)(드모르간 같음)

-bar(G1VG2) = bar(G1) + bar(G2)(드모르간 같음)

-G':sub

-(Characterization of Line Graph)

G:line graph

iff E(G) can be partitioned into a set of cliques with the property that any vertex lies in at most two cliques.

(G에서 pendant말고 다른 vertex생각해보면 그때마다 cliques in L(G)생김)

iff each induced subgraph of G on at most six vertices is a line graph

-(Whitney's Line Graph Theorem)G1:Connected and G2:connected일때

G1 graph-iso G2 iff L(G1) graph-iso L(G2) except for G1=K_(1,3), G2=K_3

-δ(G1)>=4 and δ(G2)>=4이면(connected일 필요 없음) G1 graph-iso G2 iff L(G1) graph-iso L(G2)

-G:connected이면 L(G):connected(역은 성립안함)

-G:connected이고 L(G):regular이면 G:regular or semiregular bipartite

-G:connected이고 G graph-iso L(G)이면 G:cycle

 

 

 

-L(G)의 예

-L(K_(1,n))=K_n

-L(P_(n+1))=P_n

-L(C_n)=C_n

-L(G)의 구조

-|V(L(G))| = m

-|E(L(G))| = 1/2 * [sum over i~j (d(vi)+d(vj)-2)] = (1/2 * {sum of all d(vi)^2}) - m

-G=L(G) and G:connected인 것은 C_n뿐(link)

-About quasi-line graph

-G:L(G') for some G'이면 G:quasi-line graph

-G:quasi-line graph이면 G:claw-free

-About Connectivity

-About tree

-G:tree이면

-m=(n-1)

-G has at least Δ(G) leafs, n>=2

-bipartite, 따라서 bipartite성질을 모두 따른다.

-for vi~vj, d(vi)+d(vj) <= n

-center가 1개 or 2개 존재함(증명은 leaf를 없앨 때마다 e(vi)가 -1 그래서 계속 없애다보면 center되는 애나 애들만이 남음)

-edge1개 지우면 component는 정확히 2개, 각각은 다시 tree됨

-d(vi)=s인 vi를 지우면 components는 정확히 s개, 각각은 다시 tree됨

-항상 {v1,v2,...,vn} enumerate가능 s.t. G[{v1,v2,...,vi}]:connected for every i=1,2,3,..,n and vi has a unique nbd in {v1,v2,...,vi-1}

-For any a in N, te v in V(T) s.t. te! component C of T - v with |C| <= max(n-1-a,a) and all other components C_i of T - v with |C_i| <= a(link)

 

 

-G:tree(connected acyclic)(link1)(link2)(link3)(link4)(link5)

iff G:1-edge-connected , i.e. minimally connected

iff G+e have a cycle

iff G:connected with n-1 edge

iff for any vi, vj in G, te! path from vi to vj

-About Binary Tree

-te 1/2 * (n+1) vertices s.t. degree=1

-m>=1/2*(n-1)(n-2) + 1이면 G:connected(link)

-δ(G)>1/2*n - 1이면 G:connected(link)

-G:disconnected이면 bar(G):connected

-G:connected이면

-n >= D(G) * δ(G) * 1/3

-항상 {v1,v2,...,vn} enumerate가능 s.t. G[{v1,v2,...,vi}]:connected for every i=1,2,3,..,n

-G contains a normal tree with any specified vertex as its root(root에서 시작해서 아직 안가본 any vertex로 edge따라 이동, 만약에 그런 점이 없을 경우가 오면, 현재 그 점에 가장 처음에 왔던 edge를 따라 이동, 그리고 그런 점이 없을 경우가 root가 된다면 stop, 이렇게 얻은 tree가 normal이 된다.)

-G contains a normal spanning tree with any specified vertex as its root.

-G has at least n-m connected components(link)

-G:connected이면 m >= n-1

-κ(G) <= λ(G) <= δ(G)(link)

-About cutvertex

-(Characterization of cutvertex)G:connected일 때 TFAE

-v:cutvertex

-te u,w in V(G) s.t. u != v and w != v and u lies on every path from u to w .

-v:a point of articulation of G

-About κ(G)

-κ(P_n) = 1

-κ(C_n) = 2

-κ(tree)=1

-About λ(G)

-λ(P_n)=1

-λ(K_n)=n-2

-λ(C_n)=2

-λ(tree)=1

-About hypergraph

-About Directed

-If dG:acyclic, then [n]로 level assign, with no two vertices have the same level, and if vivj is in E(dG) then ni<nj, 가능!

-If dG:acyclic with a longest path of length k, then k+1 is the smallest number of levels in any level assignment of dG

(즉, dG가 acyclic이면 |longest path|+1개의 숫자써서 level assign가능)

-dG* has no loops

-dG* has no closed directed walks(link)

-TFAE

-dG has no cycles

-every strong components of dG consists of one point

-dG is isomorphic to dG*

-dG and dG* have the same number of points

-Every walk is a path

-It is possible to order the points of dG so that AdMT(dG) is UMT(link)

-It is possible to assign levels ni to the points vi in such a way that if vivj is in E(dG) than ni<nj

-dG^t has no loops, asymmetric(arc (a,b)가 있으면 (b,a)는 없음), transitive

-About competition graph C(dG)

-(Opsut 1982)It is an NP-complete problem to compute c#(G)

-c#(G) >= cec(G) - n + 2

-If G without K_3, then c#(G) >= m - n + 2

-If G without K_3 and conncected, then c#(G) = m - n + 2

-Every chordal graph G has c#(G) <= 1 with = iff G has no isolated vertices

-Every interval graph has c#(G) <= 1

-(Opsut 1982)c#(G) <= cec(G)

-(Opsut 1982)c#(G) >= min over vi cvc(N_G(vi)), N_G(vi)를 induced subgraph of G로 보고 계산

-If G is L(G') for some graph G', then cvc(N_G(vi))<=2

-If G is L(G') for some graph G', then c#(G) <= 2 with = iff every v in V(G), cvc(N_G(v)) = 2

-About Matching

-M:maximum matching iff G has no M-augmenting path(link)

-(First Tutte's Theorem)G has a perfect matching iff for any subset U of V(G), odd(G-U)<=|U|

-for every component C with odd order and v in V(C), C - v has a perfect matching

-(Tutte-Berge Formula)ν(G) = 1/2 * min over U:subset of V(G) {(|U| + |V(G)| - odd(G-U))}

-(Konig's Matching Theorem)G:bipartite이면 ν(G) = τ(G)(link)

-(Hall's Marriage Theorem)G:bipartite with partition (A,B) of V(G)일 때, 

te M covering A iff for any subset U of A, |N_G(U)|>=|U|(link)

(Marriage Theorem이라 불리는 이유는 다음과 같은 상황을 생각하자. A:남자들의 모임, B:여자들의 모임, 각 남자 mi는 결혼하면 행복할 여자들 Bi가 존재한다. (즉, Bi:nonempty subset of B) 그리고 여자들은 자기를 좋아해주는 남자와 결혼하면 행복하다고 하자. 이때 모든 남자들이 행복한 결혼생활을 할 수 있게 matching시켜줄 수 있는 필요충분조건을 제시함)

-(Gale-Shapley Theorem)Every bipartite graph has a stable matching

-for r>=1, G:r-regular bipartite이면 G has a perfect matching

-G:3-regular and has no bridge이면 G has a perfect matching

-About Coloring

-col(G) = deg(G) + 1

-χ(G) <= χ_l(G) <= col(G) <= Δ(G) + 1.

-χ(G) <= aχ(G)

(aχ(G) and col(G) are incomparable)

-About k-color-critical

-G:k-color-critical이면

-δ(G) >= k-1

-About Homomorphism, Automorphism, Group etc

-Aut(G)=Aut(bar(G))

-χ(G)=the minimum number a s.t. te f:homomorphism from V(G) to V(K_a)

-End(G)는 monoid가 된다.

-Aut(C_n) giso D_2n(아마도?)

-S_[v] <= Aut(J(v,k,i)), as a subgroup

(사실 = 일 때가 많다, 증명은 어렵지만)

-n!/|Aut(G)| = |isomorphism class of G| (즉, vertices개수가 n인 graph중에서 G와 isomorphic인 애들의 개수)

-About Matrices

-MT:irreducible iff dG(MT):strongly connected(link)(other link)

-About Space of a graph

-Let E be a subset of E(G). Then TFAE

-E is in CS(G)

-E is a disjoint union of cycles in G(empty일 수도)

-all vertex degree of (V,E) is even