近畿大学学術情報リポジトリ

全文

(1)均衡型(σ4,07)-2かFoilシ. 潮. Balanced. ステム. 和彦*. (C4, C7)-.2t-FoilSystems Kazuhiko. USHIO*. In graph theory, the decomposition problems of graphs are very important topics. Various types of decompositions of many graphs can be seen in the literature of gaph theory. It is shown that the necessary and sufficient condition for the existence of a balanced (C4, C7)-2t-foil decomposition of the complete graph K,, is n- 1 (mod 22t). This decomposition is to be known as a balanced (C4, C7)-2t-foil system. Key words: Balanced (C4, C7)-2t-foil decomposition, Complete graph, Graph theory. 1. 2 Balanced (C4, C7)-2t-foil. Introduction. decomposition. Let Kn denote the completegraph of n vertices. Let C4 and C7 be the 4-cycle and the 7-cycle, respectively. The (C4,C7)-2t-foil is a graph of t edgedisjoint C4's and t edge-disjoint C7's with a common vertex and the common vertex is called the center of the (C4iC7)-2t-foil. In particular, the (C4sC7)2-foil is called the (C4, C7)-bowtie. When K,,, is decomposed into edge-disjoint sum of (C4, C7)-2t-foils, we say that Km has a (C4, C7)-2t-foil decomposition. Moreover, when every vertex of Km appears in the same number of (C4iC7)-2t-foils,we say that Kn has a balanced(C4,C7)-2t-foil decompositionand this number is called the replication number. In this paper, it is shown that the necessary and sufficient condition for the existence of a balanced (C4,C7)-2t-foil decomposition of Km is n - 1 (mod 22t). It is a well-known result that Km has a C3 decomposition if and only if n= 1 or 3 (mod 6). This decomposition is known as a Steiner triple system. See Colbourn and Rosa[2] and Wallis[15]. Horak and Rosa[3] proved that Kr, has a (C3,C3)-bowtie decomposition if and only if n I or 9 (mod 12). This decompositionis known as a bowtiesystem. In this sense, our balanced (C4,C7)-2t-foildecomposition of Kn is to be known as a balanced (C4,C7)2t-foil system. For the design theory, see Colbourn[1], Lindner[4], and Ushio[5]. For the graph decomposition, see Ushio[6-7J,Ushio and Fujimoto[8-14].. * til4a14114 De. partment of Informatics, School of Science and Engineering, Kinki Univesity, Osaka 577-8502, JAPAN E-mail: ushio©info.kindai.ac.jp. of Kn. Note. We consider the vertex set V of Km as V = {1, 2, ..., n}. The additions i + x are taken modulo n with. residues. 1, 2, ..., n.. Notation. We denote a (C4, C7)-2t-foil passing through v1—V2—V3—V4—vl—V5—V6—V7—V8—V9 V10—Vi, V1- v11- V12—V13—V1—V14—V15—V16—V17—V18— v19 —vl, V1—V20—V21—V22—V1—V23—V24—V25—V26—V27— V28—vl, V1 —Vg/-7 —Vg/-6r-V9t-5 —VI—V9t-4 —V9t-3—V9t-2— v9t-1 —VOL —V9t+1 —V1 by. {(v1,v2,v3,V4),(v1,v5,v6,v7,v8,v9,v10)} U {(vi, vii, V12) V13),(V1,V14,V15,V16,V17,v18,V19)} U {(v1,V20,V21,V22),(vl, V23,V24,V25,V26,V27,V28)} U {(V1,VOt-7,V91-6,V9t-5),(V1,VOt-4,v9t-3, v9t-2, Vgt-1,v9t,V9t+1)}• Theorem. Ka has a balanced (C4,C7)-2t-foil decomposition if and only if n- 1 (mod 22t). Proof. (Necessity) Suppose that Km has a balanced (C4, C7)-2t-foil decomposition. Let b be the number of (C4,C7)-2t-foilsand r be the replication number. Then b = n(n —1)/22t and r = (9t +1)(n — 1)/22t. Among r (C4,C7)-2t-foilshaving a vertex v of Km, let r1 and r2 be the numbers of (C4,C7)-2tfoils in which v is the center and v is not the center, respectively. Then r1 +r2 = r. Counting the number of vertices adjacent to V, 4tr1 + 2r2 = n —1. From these relations, r1 = (n-1)/22t and r2 = 9(n-1)/22. Therefore, n - 1 (mod 22t) is necessary. (Sufficiency) Put n = 22st + 1 and T = st. Then.

(2) n=22T+1. When T = 1, construct a balanced (C4,C7)-2-foildecomposition of K23 as follows: B; = {(i,i+5,i+13,i+6),(i,i+1,i+3,1+7,i+ 10,i+20,i+9)} (1 = 1, 2,...,23). First, consider a sequence S : 91,92,93, •••,9T• When T = 2, put S : 91,92 with 91 = 21,g2 = 19. When T = 3, put S : 91,92,93 with 9i = 28,92 = 30,93 = 29. When T = 4, put S : 91,92,93,94 with 9i = 39,92 = 41,93=38,g4=37. When T = 5, put S : 91,92i 93,94,95 with 91 = 51,92=47,93=49,94=48,95=46. When Ta2 (mod 4),T>6, put T=4p+2and S : 91,92,93,•••,94p+2with Si : 91,93,95,•••,92p-1 S2 : 92s94s96s•••792p7 53 92p+1 , S4 • 92p+2,92p+3s92p+4,•••,94p+2 such as Si : 10T 2,10T-4,1QT-6,...,10T-2p S2 : 10T+1,10T1,10T-3,...,IOT--2p+3 S3 : 10T-2p+1 84 : 10T-2p-1, IOT- 2p-2, 10T- 2p- 3, ..., 9T + 1. When T - 3 (mod 4), T > 7, put T = 4p + 7 and S : 91,92,93, ..., 94.p+7with Si. : 91,92p+3,94p+5s94p+6,94p+7s S2 : 92,93,94,•••s92p+2 5 S392p+4 s92p+6s92p+8s•••s94p+4 s 54 : 92p+5,92p+7,92p+9,•••594p+3such as Si : 10T + 1,10T-2p-3,9T+5,9T+3,9T+1 S2 : 10T-1,10T-2,10T-3,...,10T-2p-1 S3 : 10T-2p-5,10T-2p-7,10T-2p-9,...,9T+2 S4 : 10T-2p-2,10T-2p-4,10T-2p-6,...,9T+7. When T=0 (mod 4), T > 8, put T = 4p + 4 and S : 91,92,93,•••,94p+4with S1 : 91,93,957•••792p-1 s 52 • 92s94,96,•••s92p-I-2 s 53 • 92p+1 , 54 • 92p+3s92p+4s92p+5s •.•394p+4such as Si : 10T 2,10T-4,10T-6,...,10T-2p S2 : 10T + 1, 10T1, 10T - 3, ..., 10T - 2p + 1 53 : 10T-2p1 54 : 10T-2p-2,10T-2p-3,10T-2p-4, ..., 9T+1. When T - 1 (mod 4), T > _ 9, put T = 4p + 9 and S : 91s92,93, •••,g4p+9 with Si 91,92p+5s94p-F-7, 94p+8s94p+9s 52 : 92s93s94, •••,92p+3 s S3g2p+4 s92p+6sg2p+8s•••sg4p+6 s S4 • 92p+7,92p+9,92p+11s•••s94p+5such as S1 : 10T + 1,10T-2p-3,9T+5,9T+3,9T+1 S2 : 10T - 1,10T-2,10T-3,...,10T-2p-2 S3 : 10T-2p-5,10T-2p-7,10T-2p-9,...,9T+2 S4 : 10T-2p-4, IOT- 2p - 6, 10T- 2p- 8, ... ,9T + 7. Next, construct n (C4iC7)-2T-foilsas follows: Bi = {(i,i+T+1,i+15T+2,i+2T+1),(i,i+1,i+ 3T +2,i+ 10T +2,i+15T + 3, i + 20T +3,i+g')} U {(i,i+T +2,i+15T +4,i+2T +2),(i,i+2,i+ 3T+4,i+10T+3,i+15T+5,i+20T+4,i+g2)} U {(i,i+T+3,i+15T+6,i+2T+3), (i,i+3,i+3T+ 6,i+10T+4,i+15T+7,i+20T+5,i+g3)} U ... U {(i,i+2T,i+17T,i+3T),(i,i+T,i+5T,i+11T+ 1,i+ 17T +1,i+ 21T +2,i+gT)} (i = 1,2,...,n). Last, decompose each (C4, C7)-2T-foil into s (C4,C7)-2t-foils. Then they comprise a balanced (C4,C7)-2t-foildecomposition of K. ^. Corollary. Kn has a balanced (C4, C7)-bowtie decomposition if and only if n 1 (mod 22). Example 1. A balanced position of K23.. (C4, C7)-2-foil decom-. B, = {(i,i+5,i+13,i+6),(i,i+1,i+3,i+7,i+ 10,/ + 20,i + 9) } (i = 1, 2, ..., 23). Example 2. A balanced (C4, C7)-4-foil decomposition of K45. Bi = {(i,i+3,i+32,i+5),(i,i+1,i+8,i+22,i+ 33,i+43,i+21)} U {(i,i+4,1 + 34,i + 6), (i,i + 2,i + 10,1 + 23,i + 35,i + 44,i + 19)} (i = 1, 2, ..., 45). Example 3. A balanced (C4, C7)-6-foil decomposition of K67. Bi = {(i,1+4,1+47,1+7),(1,1+1,1+11,1+32,1+ 48,i+63,i+28)} U {(i,i+5,i+49,i+8),(i,i+2,i+13,i+33,i+ 50,i + 64,i + 30)} U {(i,i+6,i+51,i+9),(i,i+3,i+ 15,i+34,i+ 52,2 + 65, 2+ 29)1 (i = 1, 2, ..., 67) . Example 4. A balanced (C4, C7)-8-foil decomposition of Ks9. B1 = {(i,i+5,i+62,1+9),(1,1+1,1+14,1+ 42,i+ 63,i+83,i+39)} U {(i,i+6,i+64,i+10),(i,i+2,i+16,i+43,1+ 65,i+84,i+41)} U {(i,i+7,i+66,i+11),(i,i+3,i+18,1+44,i+ 67,i+85,i+38)} U {(i,i+8,i+68,i+12),(i,i+4,i+20,1+ 45,1+ 69,i + 86,i + 37)1 (i=1,2,...,89). Example 5. A balanced (C4, C7)-10-foil decomposition of K111. Bi = {(1,,i+6,1+ 77,1+11),(1,1+1,1+17,1+52,1+ 78,i + 103,i + 51)} U {(i,i+7,i+79,i+12),(i,i+2,i+19,i+53,i+ 80,i+104,i+47)} U {(i,i+8,i+81,i+13),(i,i+3,i+21,i+54,i+ 82,/ + 105,i + 49)1 U {(i,i+9,i+83,i+14),(i,i+4,i+23,i+55,i+ 84,i+106,i+48)} U {(i,i+10,i+85,i+15),(i,i+5,i+25,i+56,i+ 86,i + 107,i + 46)1 (i = I, 2, ...,111). Example 6. A balanced (C4, C7)-12-foil decomposition of K133. Bi = {(i,i+7,i+92,i+13),(i,i+1,i+20,i+62,i+ 93,i+123,i+58)} U {(i,i+8,i+94,i+14),(i,i+2,i+22,i+63,i+ 95,i+124,1+61)} U {(i,i+9,i+96,i+ 15),(i,i+3,i+24,1 +64,i+ 97,i+125,i+59)} U {(i,i+10,i+98,i+16),(i,i+4,i+26,i+65,i+ 99,i+126,1+57)}.

(3) U {(i,i+11,i+100,i+17),(i,i+5,i+28,i+66,i+ 101,1+127,i+56)} U {(i,i+12,i+102,i+18),(i,i+6,i+30,i+67,i+ 103,1+ 128,i + 55)1 (i = 1, 2, ..., 133).. 152,i + 190,i+84)} U {(i,i+18,i+153,i+27), (i,i+9,i+45,1+100,i+ 154,i + 191,i + 82)} (i=1,2,...,199).. Example 7. A balanced (C4, C7)-14-foil decomposition of K155. Bi = {(i,i+8,i+107,i+15),(i,i+1,i+23,i+72,i+ 108,i+143,1+71)} U {(i,i+9,i+109,i+16),(i,i+2,i+25,i+73,i+ 110,i+144,i+69)} U {(i,i+10,i+111,i+17),(i,i+3,i+27,i+74,i+ 112,1+145,i+67)} U {(i,i+11,i+113,i+18),(i,i+4,i+29,i+75,i+ 114,1+146,i+65)} U {(i,i+12,i+115,i+19),(i,i+5,i+31,i+76,i+ 116,1+147,i+68)} U {(i,i+13,i+117,i+20),(i,i+6,i+33,i+77,i+ 118,1+148,i+66)} U {(i,i+14,i+119,i+21),(i,i+7,i+35,i+78,i+ 120,i + 149,i + 64)1 (i = 1, 2, ...,155) . Example 8. A balanced (C4, C7)-16-foil decomposition of K177. Bi = {(i,i+9,i+122,i+17),(i,i+1,i+26,i+82,i+ 123,1+163,i+78)} U {(i,i+10,i+124,i+18),(i,i+2,i+28,i+83,i+ 125,1+164,i+81)} U {(i,i+11,i+126,i+19),(i,i+3,i+30,i+84,i+ 127,1+165,i+77)} U {(i,i+12,i+128,i+20), (i,i+4,i+32,i+85,i+ 129,1+166,i+79)} U {(i,i+13,i+130,i+21),(i,i+5,i+34,i+86,i+ 131,1+167,i+76)} U {(i,i+14,i+132,i+22),(i,i+6,i+36,i+87,i+ 133,1+168,i+75)} U {(i,i+15,i+134,i+23), (i,i+7,i+38,i+88,i+ 135,i + 169,i + 74)} U {(i,i+16,i+136,i+24), (i,i+8,i+40,i+89,i+ 137,i + 170,i + 73)1 (i = 1, 2, ...,177). Example 9. A balanced composition of K199.. (C4, C7)-18-foil. de-. B = {(i,i + 10,i + 137,i + 19), (i,i + 1,i + 29,i + 92,i+138,i+183,i+91)} U {(i,i+11,i+139,i+20),(i,i+2,i+31,i+93,i+ 140,1+184,i+89)} U {(i,i+12,i+141,i+21),(i,i+3,i+33,i+94,i+ 142,i+185,i+88)} U {(i,i+13,i+143,i+22),(i,i+4,i+35,i+95,i+ 144,1+186,1+85)} U {(i,i+14,i+145,i+23),(i,i+5,i+37,i+96,i+ 146,1+187,i+87)} U {(i,i+15,i+147,i+24),(i,i+6,i+39,i+97,i+ 148,1+ 188,i+ 188,i+83)} U {(i,i+16,i+149,i+25),(i,i+7,i+41,i+98,i+ 150,i + 189,i -- 86)} U {(i,i+17,i+151,i+26),(i,i+8,i+43,i+99,i+. References. 1) C. J. Colbourn, CRC Handbook of Combinatorial Designs, CRC Press (1996). 2) C. J. Colbourn and A. Rosa, Triple Systems, Clarendom Press, Oxford (1999). 3) P. Horak and A. Rosa, DecomposingSteiner triple systems into small configurations, Ars Combinatoria 26 (1988) 91-105. 4) C. C. Lindner, Design Theory, CRC Press (1997). 5) K. Ushio, G-designs and related designs, Discrete Math. 116 (1993) 299-311. 6) K. Ushio, Bowtie-decomposition and trefoildecomposition of the complete tripartite graph and the symmetric complete tripartite digraph, J. School Sci. Eng. Kinki Univ.36 (2000) 161-164. 7) K. Ushio, Balanced bowtie and trefoil decomposition of symmetric complete tripartite digraphs, Information and Communication Studies of The Faculty of Information and Communication Bunkyo University25 (2000) 19-24. 8) K. Ushio and H. Fujimoto, Balanced bowtie and trefoil decomposition of complete tripartite multigraphs, IEICE Trans. Fundamentals E84-A(3) (2001) 839-844. 9) K. Ushio and H. Fujimoto, Balanced foil decomposition of complete graphs, IEICE Trans. Fundamentals E84-A(12) (2001) 3132-3137. 10) K. Ushio and H. Fujimoto, Balanced bowtie decomposition of complete multigraphs, IEICE Trans. Fundamentals E86-A(9) (2003) 2360-2365. 11) K. Ushio and H. Fujimoto, Balanced bowtie decomposition of symmetric complete multi-digraphs, IEICE Trans. Fundamentals E87-A(10) (2004) 2769-2773. 12) K. Ushio and H. Fujimoto, Balanced quatrefoil decomposition of complete multigraphs, IEICE Trans. Information and Systems E88-D(1) (2005) 19-22. 13) K. Ushio and H. Fujimoto, Balanced C4bowtie decomposition of complete multigraphs, IEICE Trans. Fundamentals E88-A(5) (2005) 1148-1154. 14) K. Ushio and H. Fujimoto, Balanced C4trefoil decomposition of complete multigraphs, 1EICE Trans. Fundamentals E89-A(5) (2006) 11731180. 15) W. D. Wallis, Combinatorial Designs, Marcel Dekker, New York and Basel (1988)..

(4)