{"entities":{"Q1972324":{"pageid":1983066,"ns":120,"title":"Item:Q1972324","lastrevid":71198019,"modified":"2026-04-13T20:20:02Z","type":"item","id":"Q1972324","labels":{"en":{"language":"en","value":"Symmetric graph designs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1436041"}},"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":"Q1972324$B0F5F48A-81FA-4D63-86DA-C02E4687D34E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"57a5ea4e83722403e642c54747e3619cdd7bf858","datavalue":{"value":{"text":"Symmetric graph designs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1972324$BABE0452-F00B-4543-8B40-AF9469E95A08","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e4f0e9aab001368361188e6189d2d71e79db414b","datavalue":{"value":"0952.05005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972324$D1223FA2-BC69-4039-90A0-269F9763059A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62093226388c211ee4d5286124caf1fbc8b86437","datavalue":{"value":{"entity-type":"item","numeric-id":185060,"id":"Q185060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1972324$93873F69-66A2-4C36-98EF-416BB5F89C4E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7465641cd1982038f0f140fd1043a93fe5e7d97d","datavalue":{"value":{"time":"+2000-12-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1972324$E378F860-4D57-43E2-BD0A-BBB5C507A21A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e90d2eea3bc2b24ccc4a2dd2ce39ca4038db20ec","datavalue":{"value":"The authors introduce the notion of a symmetric graph design (SGD) which is a generalization of a symmetric balanced incomplete block design. In particular, a symmetric \\((n,G,\\lambda;F)\\)-design is a collection \\(\\{G_1, G_2, \\dots{}, G_n\\}\\) of spanning subgraphs of the complete graph \\(K_n\\) such that: (i) \\(G_i \\simeq G\\) for \\(i = 1, \\dots{}, n\\); (ii) every edge of \\(K_n\\) is contained in exactly \\(\\lambda\\) subgraphs \\(G_i\\), and (iii) \\(G_i \\cap G_j \\simeq F\\) for all \\(i, j, i \\neq j\\), and \\(|E(F)|= \\lambda' = {{\\lambda}\\choose{2}}\\). The paper consists of a series of results on existence of various families of SGDs. Just some of the results will be summarized here. Trivially every symmetric \\((v,k,\\lambda)\\)-BIBD is a \\((v,K_k,\\lambda)\\)-SGD. A further trivial example is an \\((n,K_{n-1},n-2; K_{n-2})\\)-SGD which exists for all \\(n\\). For \\(\\lambda = 1\\) an \\((n,G,1)\\)-SGD is an edge-disjoint decomposition of \\(K_n\\) into copies of \\(G\\) where \\(G\\) is a spanning subgraph with \\((n-1)/2\\) edges. When \\(\\lambda = 2\\) an \\((n,G,2)\\)-SGD is an orthogonal double cover (ODC) of \\(K_n\\) by \\(G\\), and such objects have been well studied. For \\(\\lambda = 3\\) the authors ask for which pairs \\(G\\), \\(F\\) does there exist an \\((n,G,3;F)\\)-SGD? Although it appears hopeless to determine the spectrum in the general case, the authors do give some results for the more restricted question where \\(F \\simeq K_3\\). They show that if there exists an \\((n,k,1)\\)-BIBD then there exists an \\((n,G_{r,k-1},k-2; K_{k-2})\\)-SGD where \\(r = (n-1)/(k-1)\\), and \\(G_{r,t}\\) is the graph with \\(rt+1\\) vertices and \\(r+1\\) components, \\(r\\) of which are \\(K_t\\) and one is \\(K_1\\). As a corollary an \\((n,G_{(n-1)/4,4},3;K_3)\\)-SGD exists for all \\(n \\equiv 1,5 \\pmod{20}\\). But the question of whether an \\((n,G_{(n-1)/4,4},3;K_3)\\)-SGD exists for the remaining values of \\(n \\equiv 1 \\pmod{4}\\) remains open. By analogy with the well-known result on ODCs the authors conjecture that for all \\(k \\geq 4\\) there exists a constant \\(n_0\\) such that an \\((n,G_{(n-1)/(k-1),k-1},k-2; K_{k-2})\\)-SGD exists for all \\(n \\equiv 1 \\pmod{k-1}\\), \\(n \\geq n_0\\). If \\(F_{r,k}\\) is the connected graph with \\(r(k-1)+1\\) vertices consisting of \\(r\\) copies of \\(K_k\\) glued together at a single common vertex, the authors show that an \\((n,F_{r,k},k;K_k)\\)-SGD (where \\(r = (n-1)/(k-1)\\)) exists if and only if there exists an \\((n,k,1)\\)-BIBD. Following a PBD-closure result for rooted SGDs, the authors then establish the triplication result that if there exists an \\((n,G,3;K_3)\\)-SGD then there exists a \\((3n,G^*,3;K_3)\\)-SGD where \\(G^*\\) is the graph on \\(3n\\) vertices obtained from the \\(n\\)-vertex graph \\(G\\) by appending at each vertex a triangle with two new vertices, one of which is common to all appended triangles. This leads to the following generalization. Let \\(G\\) be an \\(n\\)-vertex graph, and suppose there exists a \\((n,G,t';K_t)\\)-SGD. If there exists a transversal design \\(\\text{TD}(2t,n)\\) then there exists a \\((tn,G^{(t)},t;K_t)\\)-SGD. Finally the authors show that if \\(n\\) is a prime power and \\(F\\) is a graph with \\({n+1}\\choose{2}\\) edges which has a \\(\\rho\\)-labelling, then there exists an \\((n^2+n+1,G,n+1;F)\\)-SGD for some graph \\(G\\) with \\((n+1){{n+1}\\choose{2}}\\) edges.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1972324$C288CD49-A23A-4C29-91E6-77E85E19707D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"27fdbe8a4d1d20711d709896b961d73094143735","datavalue":{"value":{"entity-type":"item","numeric-id":819931,"id":"Q819931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1972324$2BF75FAA-A81B-43C4-95E2-92AA617480FE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"0777d7ff21c1f44314f8092c977cf5f02a5fe09c","datavalue":{"value":"05B05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972324$433C4F09-C277-4276-97F3-E75AE0272190","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ef4f65024bb9e2b8cc8f8df27f6a525ddad01576","datavalue":{"value":"51E05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972324$C4E13E95-02F4-4CDE-8A29-C43743D85B8F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"313daca7b441657aa994c2873c836b5012d2fd7d","datavalue":{"value":"1436041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972324$3FB09C46-ABC4-449A-A850-E7D1521D0D7C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"59a3fae840c562c36341684f2487658084c378d9","datavalue":{"value":"symmetric balanced incomplete block design","type":"string"},"datatype":"string"},"type":"statement","id":"Q1972324$9D6089C8-E704-4681-9736-ADDBC5EF723B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c30f5c9e2dbe896eafa82873f48d7f278e562e65","datavalue":{"value":"symmetric graph design","type":"string"},"datatype":"string"},"type":"statement","id":"Q1972324$18FBE5DE-38BB-407E-8363-908A64902291","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d2a61d783555007bf8a0bd00f0f69e44ebe5a34","datavalue":{"value":"orthogonal double cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q1972324$0D4A2804-F8FB-4D20-9780-D0983342C2DD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ac477f1df395589c0cab4a2bbf89ace8bc4e54fe","datavalue":{"value":{"entity-type":"item","numeric-id":697627,"id":"Q697627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1972324$28413A85-2826-4083-96BD-1CE2CF3D6C29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"41175922393ae37be45d3a182cef3f94400d5f81","datavalue":{"value":{"entity-type":"item","numeric-id":676712,"id":"Q676712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1972324$A84FBDB9-27F7-483B-A445-4DCCB82513F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"594d499a3377412eac4844b15a7c2b9e11872e70","datavalue":{"value":{"entity-type":"item","numeric-id":468450,"id":"Q468450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1972324$4FF5D3EE-0F0A-4D3D-844A-7B2DB6E69A03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0209d0a64c6f3f2fb6f27259727276a0ac76123d","datavalue":{"value":{"entity-type":"item","numeric-id":1412251,"id":"Q1412251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1972324$247376FA-8689-4D3F-9A01-DD566A2948FD","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":"Q1972324$68AE0B3C-C2DB-460A-82A9-FE692664E20D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a412e1e0a422dc837ac775e0ee69a8b4db6957ee","datavalue":{"value":"https://doi.org/10.1007/s003730050006","type":"string"},"datatype":"url"},"type":"statement","id":"Q1972324$39821A4E-8E57-4991-AE13-751DFEE66C07","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ec32b49ffe885eaf87298f92eadf0affa20fdb1c","datavalue":{"value":"W2093541724","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972324$69717756-2069-481B-A587-37795D7AF82B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1911a0941de8a082a4d6dcc056c49601e1561f35","datavalue":{"value":"10.1007/S003730050006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972324$F396CEF2-38F3-48B7-B00A-FF83AB674361","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a8aeb3f2cbf050511b7acf4fce0ff33c0ec28d1","datavalue":{"value":{"entity-type":"item","numeric-id":4718732,"id":"Q4718732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48b97aab8369f46938e4821831bf0f340a0b453c","datavalue":{"value":{"amount":"+0.8619715571403503","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":"Q1972324$EC4E2249-5895-4AEC-9E93-3CC47B9E777F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"381271f5506b5163c6e528d8c0f9b807e03cac0d","datavalue":{"value":{"entity-type":"item","numeric-id":4487083,"id":"Q4487083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7ac9ba5145a5dcbfa326c7c3ab1dcc2f2119d38f","datavalue":{"value":{"amount":"+0.8029071688652039","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":"Q1972324$DC90DD70-BCAD-4FFA-BB78-71017FE060B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c28bba41515c544afcc43c0ee93c4e9d7dc81aca","datavalue":{"value":{"entity-type":"item","numeric-id":3504921,"id":"Q3504921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d602e377aca3c7a5fcc74689fd584f7b84f41b5","datavalue":{"value":{"amount":"+0.7741434574127197","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":"Q1972324$22A73224-504F-454D-A829-65E1DD8EE1C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3fdb2937e01f97c0f3e5cfdc7997f30ddccd4a6b","datavalue":{"value":{"entity-type":"item","numeric-id":1802138,"id":"Q1802138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4afa3a0993e53cdf4a5cfef51f0894f64ef01ef","datavalue":{"value":{"amount":"+0.7640298008918762","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":"Q1972324$D95E3FA2-DD2B-4878-8A24-EF039CFF7C30","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Symmetric graph designs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Symmetric_graph_designs"}}}}}