漳州师范学院硕士学位论文图论中若干问题的研究姓名：谢小花申请学位级别：硕士专业：基础数学指导教师：陈宝兴20080601ii?2?Cayley?Bi-Cayley?Cayley?Zn?2?Bi Cayley?BC(n;s1,s2)?DLG(n;s1,s2)?L? ?L?L-?3?Zn?2?Bi-Cayley?BC(n;s1,s2)?L-?L(2n;l,h,p,q)?DLG(n;s1,s2)?L-?L(n;l,h,p,q)?:?Cayley?Bi-Cayley?L-?iiiAbstractThe main objective of studying on the determinant of the adjacency matrix ofa graph is to study the multiplicity of zero eigenvalue, which is widely applied inthe stability problem of the chemical molecular structure graph. The determinantsof the adjacency matrices of a graph with one cycle and a graph with bicycle aregiven in the second chapter of this thesis.For given n,s1,s2, the relationship between the four parameters of the L-shape tile L(n;l,h,p,q) of Double Loop Graph DLG(n;s1,s2) and the L-shape tileL(2n;l,h,p,q) of Bi-Cayley Graph BC(n;s1,s2) is given in the third chapter ofthis thesis.Key Words:graph with one cycle; graph with bicycle; adjacency matrix; per-fect matching; determinant;Cayley graph; Bi-Cayley graph; Double loop network;L-shape tile漳 州 师 范 学 院 学位论文原创性声明 本人郑重声明： 所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名： 日期： 年 月 日 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权漳州师范学院可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1、保密，在_年解密后适用本授权书。 2、不保密。 （请在以上相应方框内打“” ） 作者签名： 日期： 年 月 日 导师签名： 日期： 年 月 日 ?11?1.1?G?(V (G)?E(G)?G),?V (G)?E(G)?V (G)?G?G?G?(G) = |V (G)|?G?G?(G) = |E(G)|?G? ? ? ?10?G?(v0,vk)?W = v0e1v1e2v2.ekvk,?v0,v1,.,vk?G?e1,e2,.,ek?G?1 i k,ei? ?vi1?vi.?v0,vk?W?k?W?W?W?10?G?G?G?n?n+1?G?G?G?G?G?G?v1,v2,.,v,?G?A(G) =aij,?aij=( 1,?(vi,vj) E(G)0,?(vi,vj) / E(G).?A?n?detA = 0,?A?A?Cayley?Bi Cayley?DLG(n;s1,s2)?V = Zn= 0,1,2,.,n1,?E = i i + s1,i i + s2|i Zn.2?G?S (?)?G?Cayley?Cay(G,S)?G?S?V = G,E = (g,gs)|g G,s S.?G?S (?)?G?Bi Cayley?BC(G,S)?V = G 0,1,?E = (g,0),(sg,1),g G, s S .?G?Zn= 0,1,2,.,n 1, S = s1, s2?s1,s2 Zn?BiCayley?BC(Zn,S)?BC(n;s1,s2)?V = ZnZ2= Zn0,1?E = (i,0),(i+s1,1),(i,0),(i+s2,1)|i Zn.1.2?2?3?Zn?2?Bi-Cayley?BC(n;s1,s2)?L-?L(2n;l,h,p,q)?DLG(n;s1,s2)?L-?L(n;l,h,p,q)?32?2.1?G?A(G)?(0,1)-?4?8?9?8?9?7.?2.15:?n?G?A(G),?detA(G) = (1)nXH(1)k(H)2c(H)()?H?G?n?H?k(H)?H?c(H)?H?()?2.2?2.210:?2.3:?G?C?G?G1= G V (C).?G?G1?G1?C?C?G?G1?4?G1?T1,?G?T1?u?C?v?(?2.1).?G?E(T1) uv,?V (T1) v?T?G V (T)?2.2,?G?rrrrrrrrrppppppppppppppppppppppppppppppuvT1C?2.1?2.1:?G?n?C?G?k?k 1,?n?n?G(l1,l2,l3).?2.2?Pl1+1?Pl3+1?C1,?l1+ l3,?Pl2+1?Pl3+1?C2,?l2+ l3,?Pl1+1?Pl2+1?C3,?l1+ l2.? 2.3:?C1,C2?l1,l2(?l1,l2 2)?C1?C2?n?n?G(l1,l2).?2.3?11 rrC1? ? ? ?pppppppppprrr ? ? ? ? rr pppppppppprrC2?2.3?G(l1,l2)(?)? 2.4:?G = G(l1,l2,l3) (?G(l1,l2) )?n?C1, C2,C3(?C1, C2)?G?Gi= GV (Ci),?Ci?Gi?(i = 1,2,3).ri?Ci?2.5:?G = G(l1,l2)?n?G?G1?G2?G?n?G1?G2?G?l1,l2?G