Article ID Journal Published Year Pages File Type
4650772 Discrete Mathematics 2008 10 Pages PDF
Abstract

The graph consisting of the four 3-cycles (triples) (x1,x2,x8),(x2,x3,x4),(x4,x5,x6)(x1,x2,x8),(x2,x3,x4),(x4,x5,x6), and (x6,x7,x8)(x6,x7,x8), where xixi's are distinct, is called a 4-cycle-triple block and the 4-cycle (x2,x4,x6,x8)(x2,x4,x6,x8) of the 4-cycle-triple block is called the interior (inside) 4-cycle. The graph consisting of the four 3-cycles (x1,x2,x6),(x2,x3,x4),(x4,x5,x6)(x1,x2,x6),(x2,x3,x4),(x4,x5,x6), and (x6,x7,x8)(x6,x7,x8), where xixi's are distinct, is called a kite-triple block and the kite (x2,x4,x6)(x2,x4,x6)-x8x8 (formed by a 3-cycle with a pendant edge) is called the interior kite. A decomposition of 3kKn3kKn into 4-cycle-triple blocks (or into kite-triple blocks) is said to be perfect if the interior 4-cycles (or kites) form a k  -fold 4-cycle system (or kite system). A packing of 3kKn3kKn with 4-cycle-triples (or kite-triples) is a triple (X,B,L)(X,B,L), where X   is the vertex set of KnKn, B is a collection of 4-cycle-triples (or kite-triples), and L   is a collection of 3-cycles, such that B∪LB∪L partitions the edge set of 3kKn3kKn. If |L||L| is as small as possible, or equivalently |B||B| is as large as possible, then the packing (X,B,L)(X,B,L) is called maximum. If the maximum packing (X,B,L)(X,B,L) with 4-cycle-triples (or kite-triples) has the additional property that the interior 4-cycles (or kites) plus a specified subgraph of the leave L   form a maximum packing of kKnkKn with 4-cycles (or kites), it is said to be perfect.This paper gives a complete solution to the problem of constructing perfect maximum packings of 3kKn3kKn with 4-cycle-triples and kite-triples, whenever n   is the order of a 3k3k-fold triple system.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,