题目：Construction scheme for cubic 4-ordered Hamiltonian graphs

内容简介：In 1997, two strong Hamiltonian properties were introduced by Ng and Schultz. A graph is k-ordered Hamiltonian if for every k ordered set S = {x1,x2,…, xk} there exists a Hamiltonian cycle which encounters S in its designated order. Moreover, a graph is k-ordered Hamiltonian connected if for every k ordered set S = {x1,x2,…, xk} there exists a Hamiltonian path joining x1 to xk that encounters S in its designated order.

Obviously, any Hamiltonian graph is 3-ordered Hamiltonian. Thus, the k-ordered Hamiltonian property is really interesting only for k³4. Similarly, any Hamiltonian connected graph is 3-ordered Hamiltonian connected. Again, the k-ordered Hamiltonian property is really interesting only for k³4.Thus, we should investigate the existence of cubic 4-ordered Hamiltonian graphs and/or cubic 4-ordered Hamiltonian connected graphs.

Up to now, some families of cubic 4-ordered Hamiltonian graphs and/or cubic 4-ordered Hamiltonian connected graphs are founded. More precisely, K4 and K3,3 are prove to be 4-ordered Hamiltonian graphs by Ng and Schultz. The Heawood graph is prove to be 4-ordered Hamiltonian by Meszaros. We have proved that the generalized Petersen graph P(n; 3) is 4-ordered Hamiltonian if and only if n is even and either n = 18 or n ³24. Moreover, the chordal ring CR(2n; 1; 5) is 4-ordered Hamiltonian if and only if 2n = 12k+2 or 2n = 12k+10 for some k³2 or 2n = 14. However, there is no construction scheme for such graphs.

Recently, we have observed a new construction scheme, we call edge join. Let G be a cubic graph with an edge (A,B) such that P1 and P2 are neighbors of A other than B and Q1 and Q2 are neighbors of B other than A. Let H be a cubic graph such that V(G) Ç V(H)= Æ with an edge (C,D) such that R1 and R2 are neighbors of C other than D and S1 and S2 are neighbors of D other than C. The edge join of G and H along (A,B) and (C,D) is the graph with V(G)ÈV(H)-{A,B,C,D} as vertex set and E(G)ÈE(H)-{(A,B), (A,P1), (A,P2), (B,Q1), (B,Q2), (C,D), (C,R1), (C,R2), (D,S1), (D,S2)}È{(P1,R1), (P2,R2), (Q1,S1), (Q2,S2)}. In this talk, we will try to find undersuitable conditions on G and H, we can prove the edge join of G and H is 4-ordered Hamiltonian and/or 4-ordered Hamiltonian connected.

报告人：台湾静宜大学徐力行教授

报告人简介：Lih-Hsing Hsu received his BS in mathematics from Chung Yuan Christian University, Taiwan, Republic of China, in 1975, and his PhD in mathematics from the State University of New York at Stony Brook in 1981 to 1985, he was an associate professor at the Department of Applied Mathematics at National Chiao Tung University in Taiwan. From 1985 to 1988, he was the chairman of the Department of Applied Mathematics at NationalChiaoTungUniversity. After 1988, he joined the Department of Computer and Information Science of National Chiao Tung University. In 2004, he retired from NationalChiaoTungUniversity, holding a title as an honorary scholar of that university. He is currently the chairman of the Department of Computer Science and Information Engineering , ProvidenceUniversity, Taichung, Taiwan. His research interests include interconnection networks, algorithms, graph theory, and VLSI layout.

时间：2018年1月9日（周二）下午2：30始

地点：南海楼224室

热烈欢迎广大师生参加!

信息科学技术学院/网络空间安全学院

2017年12月29日