×

Graph designs for all graphs with six vertices and eight edges. (English) Zbl 1105.05011

Let \(G\) be a finite simple graph. A \(G\)-design of order \(v\), denoted by \(G\)-\(GD(v)\), is a pair \((X,{\mathcal B})\), where \(X\) is the vertex set of the complete graph \(K_v\), and \(\mathcal B\) is a collection of subgraphs of \(K_v\), called blocks, such that each block is isomorphic to \(G\) and any two distinct vertices in \(K_v\) are adjacent in exactly one block. The obvious necessary conditions for the existence of a \(G\)-\(GD(v)\) are \(v\geq n\), \(v(v-1)\equiv0\;(\text{mod\;}2e)\), and \(v-1\equiv0\;(\text{mod\;}d)\), where \(n\) and \(e\) are the number of vertices and edges of \(G\), respectively, and \(d\) is the greatest common divisor of the degrees of all vertices in \(G\). The question, whether a \(G\)-\(GD(v)\) exists whose parameters \(v\), \(n\), \(e\), \(d\) satisfy the above necessary conditions, is called the “graph design problem”. Such a problem has been answered for particular graphs, and in most cases for \(n\leq5\) or \(n=6\) and \(e\leq7\). In this paper, the graph design problem is affirmatively answered for all \(22\) graphs with parameters \(n=6\) and \(e=8\), with at most two exceptions when \(v=32\).

MSC:

05B30 Other designs, configurations
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05B05 Combinatorial aspects of block designs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alspach, B., Gavlas, H. Cycle decompositions of K n and K n . Journal of Combinatorial Theory (Series B), 21:146–155 (2000)
[2] Bermond, J.C., Huang, C., Rosa, A., Sotteau, D. Decomposition of complete graphs into isomorphic subgraphs with five vertices. Ars Combinatoria, 10:211–254 (1980) · Zbl 0454.05053
[3] Bermond, J.C., Schönheim, J. G-decomposition of K n , where G has four vertices or less. Discrete Math., 19:113–120 (1977) · Zbl 0376.05016 · doi:10.1016/0012-365X(77)90027-9
[4] Blinco, A. On diagonal cycle systems. Australasian Journal of Combinatorics, 24:221–230 (2001) · Zbl 0986.05062
[5] Bosak, J. Decompositions of graphs. Kluwer Academic Publishers, Boston, 1990
[6] Chang, Y. The spectra for two classes of graph designs. Ars Combinatoria, 65:237–243 (2002) · Zbl 1073.05512
[7] Colbourn, C.J., Dinitz, J.H.(eds.) The CRC handbook of combinatorial designs. CRC Press, Boca Raton, 1996 · Zbl 0836.00010
[8] Ge, Gennian. Existence of holey LSSOM of type 2n with application to G7-packing of Kv. J. Statist. Plan. Infer., 94:211–218 (2001) · Zbl 0990.05029 · doi:10.1016/S0378-3758(00)00254-8
[9] Harary, F. Graph theory. Addison-Wesley, Reading, 1969
[10] Heinrich, K. Path-decomposition. Le Mathematics (Catania) XLVII:241–258 (1992) · Zbl 0790.05065
[11] Kang, Q.D., Du, Y.K., Tian, Z.H. Decompositions of {\(\lambda\)}Kv into some graph with six vertices and seven edges. Journal of Statistical Planning and Inference, available online 2 December 2004.
[12] Kang, Q.D., Du, Y.K., Tian, Z.H. Decomposition of complete graph into isomorphic subgraphs with six vertices and seven edges. to appear in Ars Combinatoria. (accepted on March, 2005)
[13] Kang, Q.D., Zhang, Y.F., Zuo, H.J. {\(\lambda\)}- packings and {\(\lambda\)}-coverings by k-circuits with one chord. Discrete Mathematics, 279:287–315 (2004) · Zbl 1035.05069 · doi:10.1016/S0012-365X(03)00276-0
[14] Kang, Q.D., Zuo, H.J., Zhang, Y.F. Decompositions of {\(\lambda\)}K v into k-circuits with one chord. Australasian Journal of Combinatorics, 30:229–246 (2004) · Zbl 1051.05022
[15] Kang, Q.D., Wang, Z.Q. Optimal packings and coverings of {\(\lambda\)}Kv with graph K 5 P 5. Bulletin of the Institute of Combinatorics and its Applications, 41:22–41 (2004)
[16] Kang, Q.D., Wang, Zhiqin. Maximum K 2,3-packing and minimum K 2,3-covering designs of {\(\lambda\)}K v . Journal of Mathematical Research and Exposition, 25:1–16 (2005) · Zbl 1077.05013
[17] Kotzig, A. Decomposition of complete graphs into isomorphic cubes. J. Combin. Theory (Series B), 31:292–296 (1981) · Zbl 0496.05041 · doi:10.1016/0095-8956(81)90031-9
[18] Rodger, C.A. Graph-decompositions. Le Mathematics (Catania) XLV:119–140 (1990) · Zbl 0735.05066
[19] Rosa, A. On certain valuations of the vertices of a graph, Theory of Graphs, (Internat. Symmposium, Rome, July 1966), Gordon and Breach, N.Y. and Dunod Paris, 349–355 1967
[20] Yin, J., Gong, B. Existence of G-designs with |V (G)| = 6, In:W.D. Wallis et al.(eds). Combinatorial designs and applications, Marcel Dekker, New York, 201–218 1990 · Zbl 0757.05023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.