کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650772 | 1632441 | 2008 | 10 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Maximum packing for perfect four-triple configurations Maximum packing for perfect four-triple configurations](/preview/png/4650772.png)
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.
Journal: Discrete Mathematics - Volume 308, Issues 5–6, 28 March 2008, Pages 753–762