※ [本文转录自 NTU-Exam 看板]
作者: abcde1234 (沌魂) 看板: NTU-Exam
标题: [试题] 94下 张镇华 图论二 期末考
时间: Fri Jun 30 00:32:04 2006
课程名称︰图论二
课程性质︰U选修
课程教师︰张镇华
开课系所︰数学系、数学所
考试时间︰6/22 1:20~3:20
是否需发放奖励金：是
（如未明确表示，则不予发放）
试题 :
Examination 2 (Graph Theory, second semester)
Each problem weights 25 points. 2006-6-22(Gerard J. Chang)
1. Recall that a simple n-vertex G is strong regular if there are parameters
k,λ,μ such that G is k-regular, every adjacent pair of vertices have λ
common neighbors, and every pair of non-adjacent vertices have μ common
neighbors.
(a) Prove that if G is a strongly regular graph with n vertices and
_
parameters k,λ,μ then G is a strongly regular graph. Determine the
_
parameters k',λ',μ' for G in terms of n,k,λ,μ.
(b) Prove that if G is a strongly regular graph with n vertices and
parameters k,λ,μ, then k(k-λ-1)=μ(n-k-1).
(c) Prove that if G is strongly regular graph with n vertices and
1 (n-1)(μ-λ)-2k
parameters k,λ,u, then - (n-1 ± ─────────── ) are non-negative
2 √((μ-λ)^2+4(k-μ))
integers.
(d) Determine all strongly regular graphs with λ=μ=1.
(e) Give examples of strongly regular graphs with λ=μ for each μ.
2. (a) Use a random partition of vertices to prove that every graph has a
bipartite subgraph with at least half its edges.
(b) Use equipartitions of vertices to improve part(a): if G has m edges and
m┌n/2┐
n vertices, then G has a bipartite subgraph with at least ───── edges.
2┌n/2┐-1
(c) Prove the same result as in (a) without using randomness.
(d) What can you say if we replace bipartite by r-partite?
3. Recall that the product dimension pdim(G) of a graph G is the minimum t
such that we may assign the vertices of G distinct vectors of length t so
that uvεE(G) if and only if their vectors differ in every position.
_
(a) Determine pdim(K_n) and pdim(K_n).
(b) Determine pdim(K_1∪K_(n-1)).
(c) Prove that pdim(G) is well-define for any graph G.
(d) Prove that pdim(G)<=n-1 for any n-vertex graph G with n>=3.
(e) Determine pdim(P_n) and justify your answer.
4. A graph is split if its vertex set can be partitioned into a clique and a
stable set. _
(a) Prove that if G is split, then G and G are chordal.
(b) Prove that if G is split, then G has no induced subgraphs in {C_4,2K_2,
C_5}.
(c) Prove that if G has no induced subgraphs in {C_4,2K_2,C_5}, then G is
split. _
(d) Prove that if G and G are chordal, then G is split.
(e) Let d_1>=d_2>=...>=d_n be the degree sequence of a simple graph G, and
let m be the largest value of k such that d_k >=k-1. Prove that G is
m n
split if and only if Σd_i = m(m-1) +Σ d_i.
i=1 i=m+1