کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648728 | 1342426 | 2010 | 10 صفحه PDF | دانلود رایگان |
Suppose KvKv is the complete undirected graph with vv vertices and GG is a finite simple undirected graph without isolated vertices. A GG-packing of KvKv is a pair (X,B)(X,B), where XX is the vertex set of KvKv and BB is a collection of edge-disjoint subgraphs (blocks) isomorphic to GG in KvKv. A GG-packing (X,B)(X,B) is called resolvable if BB can be partitioned into parallel classes such that every vertex is contained in precisely one block of each class. Let (v,G,1)(v,G,1)-MRP denote a resolvable GG-packing containing the maximum possible number r(v,G)r(v,G) of parallel classes. Suppose e(G)e(G) and V(G)V(G) are the number of edges and the vertex set of the graph GG, respectively. Let k=|V(G)|k=|V(G)|. Clearly, v≡0v≡0 (mod kk) and r(v,G)≤⌊k(v−1)/2e(G)⌋r(v,G)≤⌊k(v−1)/2e(G)⌋ for a (v,G,1)(v,G,1)-MRP. Let K4−eK4−e be the graph obtained from a K4K4 by removing one edge. It is proved in this paper that there exists a (v,K4−e,1)(v,K4−e,1)-MRP with ⌊2(v−1)/5⌋⌊2(v−1)/5⌋ parallel classes if and only if v≡0v≡0 (mod 4) with the possible exceptions of v=12,116,132,172,232,280,292,296,372,412,532,592,612v=12,116,132,172,232,280,292,296,372,412,532,592,612.
Journal: Discrete Mathematics - Volume 310, Issue 4, 28 February 2010, Pages 887–896