{"entities":{"Q4350833":{"pageid":6380432,"ns":120,"title":"Item:Q4350833","lastrevid":108269321,"modified":"2026-11-05T17:12:21Z","type":"item","id":"Q4350833","labels":{"en":{"language":"en","value":"Combinatorial designs and related computational constructions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1057016"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4350833$1DBDB19F-9EEF-4DE1-BBFF-7E8B3885CFC2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"27da38fd0e2df66481874eb5cdf47882d6d2abc6","datavalue":{"value":{"text":"Combinatorial designs and related computational constructions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4350833$D841305E-7DCC-43F0-9CDE-4B5F7239A91E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0f855f5fdd2eb9e20147787726bd7fb79cac11d3","datavalue":{"value":"0879.05047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4350833$1AE3F181-BF55-469C-81F5-D47188D9C3FE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2ba20037965f50a3c3e6ed695601e3a998718cd6","datavalue":{"value":"10.1017/S0004972700017299","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4350833$1F4A0963-0994-437F-9147-2579A24E95AB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6b34985c280ac92a95e78ca54439c7119e4907e7","datavalue":{"value":{"entity-type":"item","numeric-id":2716953,"id":"Q2716953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4350833$1B520B19-4209-4860-9ECD-B48E50D74D93","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9c4bbc1ffd4ac3c02bfe23ce3ee5bf6cda40b3ee","datavalue":{"value":{"time":"+1997-10-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4350833$7F40E48F-1A55-49A8-8C84-9C02C2397053","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4350833$2F45F019-30DB-4C77-898E-5A6E478C1616","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4a5372688a0d668805df5d9ffd1da58833a0f595","datavalue":{"value":"68R05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4350833$9CA72CC5-B338-4239-B4DC-64E6A98E6F48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4350833$09DF7AA6-549A-45EE-8FAA-2010198541CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"86c47e3aedde4615dd16421ee43ac00d4048a5ec","datavalue":{"value":"05B30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4350833$B6B0C0FF-2F29-4F7B-91CC-28C4A72FB457","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8ac6b78484ba2878332477538d327b102090ea14","datavalue":{"value":"1057016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4350833$7D36D7BF-6215-4FF9-958D-12876C54977F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a209fd98c780a56473f1caeb293281e5f2044d7b","datavalue":{"value":"spectrum problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q4350833$3389DDF3-7CEB-42CE-A8D9-8DB81CEE07FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6ae53e3874ce5ebc41a99b0efcf7458cc5d508aa","datavalue":{"value":"cycle decompositions","type":"string"},"datatype":"string"},"type":"statement","id":"Q4350833$C974FB5F-6BBE-4970-B296-74DF663E1889","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"801757d989025fb5b62d33e0119ed17cde1af250","datavalue":{"value":"perfect cycle systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q4350833$9E0E9D93-FC92-4F01-A891-6809CC0106C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ca453d722b926b8973923e0613afef1c4ab52cf9","datavalue":{"value":"Petersen graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q4350833$2E26D133-A789-4C0B-95F0-37AE1A206693","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a2738728caa4dd619f30d866380c032886620b65","datavalue":{"value":"Heawood graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q4350833$5A842D9D-49FA-4F21-A10D-B9D367A52B82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3806bdde20c02db6b3deaa8005c1df4b21527145","datavalue":{"value":"bowties","type":"string"},"datatype":"string"},"type":"statement","id":"Q4350833$25E35A86-FE04-49AB-81EF-70277DF97564","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"71a973d6745b41af5fe84eae83e191b5aea2faf0","datavalue":{"value":{"entity-type":"item","numeric-id":1258466,"id":"Q1258466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4350833$DDA4339C-4DB3-461C-A5D9-E96954FE933B","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"6789d0dd30d596dd212b952aa7fe1f3906bcab8e","datavalue":{"value":{"entity-type":"item","numeric-id":32462,"id":"Q32462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4350833$B3BC5310-C925-4B65-8F2D-5ABB6BC44992","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4350833$E4BB7EAB-9C35-4F77-8D13-C0863C01E555","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dba2aa48b2c05e60608534fbf9f08233ef1cca39","datavalue":{"value":{"entity-type":"item","numeric-id":800362,"id":"Q800362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4350833$E5AD1089-1320-4984-BF07-9955A80121E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d07ede27d6e865c927e9ac575b07d614a8473342","datavalue":{"value":{"entity-type":"item","numeric-id":1343249,"id":"Q1343249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4350833$67888042-A94F-4545-A200-7C49022AEC0B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be33537fa8f7fc25ab57e517017d92ca7ae40f5a","datavalue":{"value":{"entity-type":"item","numeric-id":1356809,"id":"Q1356809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e3159bd227bee26f4720dad4a493c96cee6ab72","datavalue":{"value":{"amount":"+0.8093933463096619","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4350833$66571871-B8BD-408F-AFC7-F08A07F37206","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96adf4e5418d9ae809661b929642fed81813739e","datavalue":{"value":{"entity-type":"item","numeric-id":4862227,"id":"Q4862227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0380e29482154fa78d4f6ad5fcf047ba9c6d831f","datavalue":{"value":{"amount":"+0.8076422810554504","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4350833$4A60C253-DAAD-4182-BC11-C99842BBDE69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c45d504c9daddd118cc710a5430de52d2deebce","datavalue":{"value":{"entity-type":"item","numeric-id":4017149,"id":"Q4017149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7613cd13ff88036fc41deb50a39f583a98d3c223","datavalue":{"value":{"amount":"+0.806226372718811","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4350833$F61E29E8-EE77-41A9-8ECF-1211819500C7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d912ffbb1f582139ee25086ca89067391937cdad","datavalue":{"value":"A great deal of work has been done on finding edge-disjoint decompositions of graphs into copies of other graphs. Usually, the graph to be decomposed is the complete graph on \\(v\\) vertices, \\(K_v\\). A natural question to ask is: given a graph \\(H\\), for which values of \\(v\\) is it possible to find a decomposition of \\(K_v\\) into edge-disjoint copies of \\(H\\)? This is commonly called the spectrum problem of \\(H\\)-decompositions. This thesis considers the spectrum problem for a number of graphs including \\(i\\)-perfect \\(m\\)-cycles, closed \\(m\\)-trails, platonic graphs, the Petersen graph, and the Heawood graph. Descriptions are also given of a computer package which has been designed to find such decompositions. Chapter 1 contains the definitions and background material which is used in later chapters. Next, a number of results are presented for \\(i\\)-perfect \\(m\\)-cycle decompositions. In Chapter 2, the case \\(i=2\\) and \\(m=5 \\) is considered, and results are given for decompositions of the \\(\\lambda\\)-fold complete graph into 2-perfect pentagons; see [\\textit{P. Adams}, \\textit{E. J. Billington} and \\textit{D. E. Bryant}, `Lambda-fold Steiner pentagon systems', J. Statist. Plann. Inference (to appear)]. This extends existing results for \\(\\lambda \\in \\{1,2\\}\\) given in [\\textit{C. C. Lindner} and \\textit{D. R. Stinson}, `Steiner pentagon systems', Discrete Math. 52, 67-74 (1984; Zbl 0549.05010)] and [\\textit{C. C. Lindner} and \\textit{A. Rosa}, `Twofold pentagon systems', Carib. J. Math. 5, No. 2, 49-58 (1986; Zbl 0719.05057)] respectively. In Chapters 3 and 4, 2-perfect 8-cycles and 3-perfect 9-cycles are considered. In each case, the spectrum problem is completely solved for all \\(\\lambda\\geq 1\\), except possibly for one unsolved case when \\(i=2\\) and \\(m=8\\). In Chapter 5, the problem of finding \\(k\\)-perfect \\(3k\\)-cycle systems is considered for arbitrary \\(k\\). Such decompositions are especially interesting because the distance \\(k\\) graph of a \\(3k\\)-cycle consists of \\(k\\) edge-disjoint triangles. Thus in a \\(k\\)-perfect \\(3k\\)-cycle system of order \\(v\\), the collection of distance \\(k\\) graphs of the cycles forms a Steiner triple system of order \\(v\\). Apart from an isolated exception when \\(k=5\\), the spectrum problem is completely solved for \\(k=4\\) and \\(k=5\\). A general result is also given for arbitrary \\(k\\equiv 1, 5 \\pmod 6\\); see [\\textit{P. Adams}, \\textit{E. J. Billington} and \\textit{C. C. Lindner}, `\\(k\\)-perfect \\(3k\\)-cycle systems', J. Comb. Math. Comb. Comput. 15, 141-154 (1994; Zbl 0806.05045)]. Previously, most spectra results for \\(i\\)-perfect \\(m\\)-cycle systems have been for the special case \\(i=2\\), and for \\(m\\leq 9\\). In Chapter 6, the problem of finding \\(i\\)-perfect \\(m\\)-cycle systems is considered for larger values of \\(i\\) and \\(m\\). All values of \\(i\\) \\((2\\leq i\\leq \\lfloor(m-1)/2 \\rfloor)\\) are considered, for all \\(m\\leq 19 \\). Many new results are presented, and currently unsolved cases are listed. A section at the end of Chapter 6 gives a comprehensive summary of all previous results, together with all new results; see [\\textit{P. Adams} and \\textit{E. J. Billington}, `Completing some spectra for 2-perfect cycle systems', Australas. J. Comb. 7, 175-187 (1993; Zbl 0777.05014); \\textit{P. Adams} and \\textit{D. E. Bryant}, `\\(i\\)-perfect \\(m\\)-cycle systems, \\(m\\leq 19\\)' (submitted)]. It is interesting to consider cycle decompositions which exhibit extra properties, as well as being \\(i\\)-perfect. In Chapter 7, consideration is given to the problem of finding some perfect cycle systems which are also partitionable; see [\\textit{P. Adams}, \\textit{E. J. Billington} and \\textit{D. E. Bryant}, `Partitionable perfect cycle systems with cycle lengths 6 and 8', Discrete Math. 149, No. 1-3, 1-9 (1996; Zbl 0849.05014)]. In the remaining chapters of the thesis, spectra results are given for problems other than perfect cycle systems. For many centuries, scholars have been fascinated by the five regular solids. In Chapter 8, platonic graphs (the graphs corresponding to the regular solids) are considered. Results are given for decompositions of the complete graph into dodecahedra and icosahedra, and then cubes and octahedra are studied in more detail. The graph corresponding to an octahedron is also a Pasch configuration, which is the unique combination of four triples on six points. Numerous other graphs have been of great interest. In particular, the Petersen graph has long been loved by graph-theorists. In Chapter 9, complete solutions are given to the spectrum problem for the Petersen graph and for the Heawood graph. An \\(m\\)-cycle is a special case of a more generalised configuration called an \\(m\\)-trail, in which there may be repeated vertices. In the next two chapters, consideration is given to finding decompositions of graphs into some closed \\(m\\)-trails. In Chapter 10, the definition of \\(i\\)-perfect is extended to trails, and bowties are considered in detail (where a bowtie is a closed 6-trail with 5 vertices). The spectrum for 2-perfect bowties was recently found [\\textit{E. J. Billington} and \\textit{C. C. Lindner}, Discrete Math. 135, No. 1-3, 61-68 (1994; Zbl 0815.05018)], and these results are extended to the spectrum for \\(\\lambda\\)-fold 2-perfect bowtie decompositions, \\(\\lambda>1\\); see \\textit{P. Adams} [Util. Math. 44, 243-253 (1993; Zbl 0792.05026)]. Then in Chapter 11, all possible closed \\(m\\)-trails with 10 or fewer edges are considered, and it is shown that it is possible to find a cyclically generated closed \\(m\\)-trail system of order \\(2m+1\\) for all such \\(m\\)-trails. These results also include a summary of cyclically generated \\(i\\)-perfect closed \\(m\\)-trail systems of order \\(2m+1\\); see \\textit{P. Adams} and \\textit{D. E. Bryant} [J. Comb. Math. Comb. Comput. 17, 3-19 (1995; Zbl 0821.05033)]. Many of the results in this thesis have been obtained using computational techniques. This has involved implementation and utilisation of a generalised tool for finding graph decompositions, called autogen, written by the author. In Chapter 12 this tool is discussed in some detail, with descriptions of how it can be used. There is also discussion of some future developments and enhancements which will be made to subsequent versions of the program.","type":"string"},"datatype":"string"},"type":"statement","id":"Q4350833$F316F6DC-4E53-4ACB-A240-18B23E76B5CC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Combinatorial designs and related computational constructions","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Combinatorial_designs_and_related_computational_constructions"}}}}}