Next: Double-wheel graphs Up: Introduction Previous: Results

KmxPn graphs

KmxPn graphs are the cross product of an m clique and a path of length n. They consist of n copies of the clique Km with the corresponding vertices in each clique also forming the vertices along a path Pn.

K4xP3 with a graceful labelling

K4xPn graphs

Graph A graceful labelling Number of labellings
K4 {0,1,4,6} 1
K4xP2 {0,1,5,16;6,15,13,3} 15
K4xP3 {0,1,4,26;24,18,13,6;10,2,23,25} 704
K4xP4 {0,1,3,36;24,32,7,2;13,6,22,34;27,33,4,14} -
K4xP5 {0,1,3,46;19,42,7,2;6,14,38,44;45,34,24,8;12,5,39,30} -

K4 has been included for completeness. K4 x P2 was also already known to be graceful [Lustig and Puget, 2001], but the number of graceful labellings was not. We did not find all graceful labellings for K4xP4 and K4xP5.


K4xP5 with a graceful labelling

KmxP2 graphs

K3xP2 and K4xP2 were already known to be graceful; they have 4 and 15 graceful labellings, respectively (apart from symmetric equivalents). We have shown that K5xP2 is graceful, but has only one graceful labelling, and K6xP2 is not graceful.


The unique graceful labelling of K5xP2


Next: Double-wheel graphs Up: Introduction Previous: Results

Barbara Smith
January 2003