# Combinatorial Mathematics VIII: Proceedings of the Eighth by R. G. Stanton, R. C. Mullin (auth.), Kevin L. McAvaney

By R. G. Stanton, R. C. Mullin (auth.), Kevin L. McAvaney (eds.)

Read Online or Download Combinatorial Mathematics VIII: Proceedings of the Eighth Australian Conference on Combinatorial Mathematics Held at Deakin University, Geelong, Australia, August 25–29, 1980 PDF

Best mathematics books

Extra info for Combinatorial Mathematics VIII: Proceedings of the Eighth Australian Conference on Combinatorial Mathematics Held at Deakin University, Geelong, Australia, August 25–29, 1980

Sample text

If j >0, we let K 2 = ((s,t) e K It >j }. tonian path p in K 2 from x to y. By Lemma 2, there exists a hamil- We may then extend p to get a hamiltonian path in K from x to y. In case 3, if i = m-2 and j = n-2, then y = (m-l, n-l), and so we can apply Lemma 2 to get a hamiltonian path in K from x to y. Hence we may assume either 28 i

Hamiltonian path in K from x to y. This completes Lemma 2. By induc- path Pl in K 3 from (0,1) to (I,i) and a Let p = (0,0)plP2(l,0). Then p is a the Proof of Lemma I. If mn is odd, then there exists a hamiltonian path from any corner- vertex x to any vertex in K with the same colour as x. Proof. Again, by symmetry, we may take x = (0,0) which is coloured blue. y = (i,j) be any blue vertex in K. We have the following two cases Let : Case I. i >0. ,(O,n-l)) there exists a hamiltonian (O,n-l)Pl. and K 2 = K -K I.

We shall prove by in- duction on n that there exists a hamiltonian path from x to any red vertex y in K. If n =2, then y = ( l , 0 ) or (0,1). (i,I)(I,0) or (0,0)(I,0)(1,I)(0,I) We may then choose the path p to be (0,0)(0,I) respectively. Hence Lemma 1 holds. the result holds for n 2) and consider the case when n =k. (0,1). (1,O). , let K 1 ={(i,h)[i=0,1 ; 0 < h < j ) and K 2 = K - K I. Applying induction hypothesis to the section graphs K 1 and K2, there exist a hamiltonian path Pl from (0,0) to (l,j-l) in K 1 ; and a hamiltonian path P2 from (l,j) to (O,j) in K 2.