TAILIEUCHUNG - Báo cáo toán học: "On the function “sandwiched” between α(G) and χ(G) V. Y"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: On the function “sandwiched” between α(G) and χ(G) V. Y. | On the function sandwiched between o G and x G V. Y. Dobrynin1 Submitted July 18 1997 Accepted September 2 1997 Abstract A new function of a graph G is presented. Say that a matrix B that is indexed by vertices of G is feasible for G if it is real symmetric and I B I A G where I is the identity matrix and A G is the adjacency matrix of G. Let B G be the set of all feasible matrices for G and let x G be the smallest number of cliques that cover the vertices of G. We show that o G min rank B B 2 B G g x G and that o G min rank B B 2 B G g implies o G x G The well known Lovasz number G of a graph G 1 is sandwiched between the size of the largest stable set in G and the smallest number of cliques that cover the vertices of G G G x G . Some alternative dehnitions of G are introduced in 2 3 . For example G max A B B is a real positive semidehnite matrix indexed by vertices of G Bvv 1 for all v 2 V G Buv 0 whenever u v in Gg where A B is the maximum eigenvalue of B V G the set of vertices of G u v denotes the adjacency of vertices u and v . Call the matrix B indexed by vertices of G feasible for G if B is real and symmetric Bvv 1 for all v 2 V G Buv 0 whenever u - v in G 0 Buv 1 whenever u v in G. Let B G be the set of all feasible matrices for G. Then 4 x G min rank B B 2 B G B CTC C 0g where the inequality denotes componentwise inequality. The aim of this paper is to study a new function of graph G THE ELECTRONIC JOURNAL OF COMBINATORICS 4 1997 R19 2 Theorem. For all graphs G a G min rank B B 2 B G implies a G x G . Proof. Let S vi v2 . va G be the stable set of G S V G S and B 2 B G is a matrix such that rank B o G . We can assume that B Ia G X T X1 Y where Ia G is the identity o G X o G -matrix. Applying block Gauss elimination B reduces to the matrix B0 Ia G 0 X Y - XT X We have Y - XT X 0 or Yuv - Xwu Xwv 0 u v 2 S 1 w2S since rank B0 rank B a G . Equation 1 gives us further information about the graph G. i If v 2 S then exists u 2 S such that u v. Indeed Yvv 1 and

• Báo cáo khoa học
• tài liệu báo cáo nghiện cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học
• các bài toán hay
• trình bày báo cáo
• báo cáo ngành văn học
• báo cáo tiếng anh
• nghiên cứu văn thơ
• giọng điệu trào phúng
• nghiên cứu khoa học
• báo cáo khoa học
• thơ lục bát
• chính sách phát triển
• gia đình việt nam
• nghiên cứu xã hội