[圖論]兩題請教
1.Prove that an r-regular bipartite graph can be
partitioned into k-regular bipartite subgraphs if k is a factor of r.
這題給人感覺很簡單理所當然，但小弟卻不知道怎麼下手，
不知道有沒有大大可以指點一下方向呢?
2.Suppose there is a homomorphism of an n-vertex graph G to H
and H is vertex transitive.Prove that a(G)/│V(G)│大於等於 a(H)/│V(H)│
Ps.
a(G)為 maximum indpendent number
A homomorphis of a graph G to a graph H is a mapping f:V(G)->V(H) s.t.
f(x)f(y) \in E(H) whenever xy \in E(H)
A graph G is vertex-transitive if for every pair u,v \in V(G) there is
an automorphism that maps u to v.
感謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.27.26.146
推
03/14 18:19, , 1F
03/14 18:19, 1F
→
03/14 18:21, , 2F
03/14 18:21, 2F
→
03/14 18:22, , 3F
03/14 18:22, 3F
→
03/14 18:22, , 4F
03/14 18:22, 4F
→
03/14 18:23, , 5F
03/14 18:23, 5F
→
03/14 18:24, , 6F
03/14 18:24, 6F
→
03/15 11:45, , 7F
03/15 11:45, 7F