{"entities":{"Q286751":{"pageid":288518,"ns":120,"title":"Item:Q286751","lastrevid":60810837,"modified":"2026-04-10T19:16:42Z","type":"item","id":"Q286751","labels":{"en":{"language":"en","value":"Transversal designs and induced decompositions of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6585220"}},"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":"Q286751$E6ADDFEB-F66C-4B6E-BC26-821DC6482654","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d6f4519ffa5894a9cfa29c6a14318bcc92f23807","datavalue":{"value":{"text":"Transversal designs and induced decompositions of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q286751$50376A2F-0D51-49EF-A139-5EAFB7BFF65D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7b0c7a79b044609b378bc9403239a91e4eec51b8","datavalue":{"value":"1347.05153","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q286751$3512921B-222F-4547-8485-B2CD1CC68BF3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fa696e5ef25763a69354b976bf97c62b1e59544c","datavalue":{"value":{"entity-type":"item","numeric-id":279226,"id":"Q279226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q286751$D7240DDF-FF9E-46CD-AF84-AA70F19BA960","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"17fcd7139afa5567c823530fba22122acb06092a","datavalue":{"value":{"entity-type":"item","numeric-id":175498,"id":"Q175498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q286751$5A695FC6-7031-438A-A96D-244069DEDC19","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6b8b858ece76e2bb88c236d487f13fce9f1e9789","datavalue":{"value":{"entity-type":"item","numeric-id":247199,"id":"Q247199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q286751$F75C6D97-AA7A-4F04-AA24-3090A39486EE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b3df5911fe2651c5b316b1c434feff8234703d15","datavalue":{"value":{"time":"+2016-05-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q286751$D879199D-8B39-4BAD-8663-E940573DAE34","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ddbc9d181c8bae6c8d67a44cab57c01352233624","datavalue":{"value":"https://arxiv.org/abs/1501.03518","type":"string"},"datatype":"url"},"type":"statement","id":"Q286751$CDAB52F0-F37E-4DCB-A1D7-A14D0A641F26","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q286751$7E04A2BF-AB89-4999-8BF7-FC386D934FD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q286751$619D4300-2454-4817-B51D-D54986E05BD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q286751$B4290412-2ECE-4A08-941A-834AF9AFE50F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b9c4c2599a5aa45285af6a0fdbf3a8d160ccee24","datavalue":{"value":"6585220","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q286751$5277B669-BB37-49AB-A466-0940242E1C6E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eb4dbee0d48d17c0702756f23f68f3af28651233","datavalue":{"value":"induced subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q286751$90FF5B44-D1EF-4A23-993B-B2D6FBD973F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"615f2a3773e3a9a3bad386a540fbc6c58cfa22ee","datavalue":{"value":"decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q286751$D7BB1BE7-743A-425B-AC2A-DA6B339EA10A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"013a665df3872df6518b386ba286fc369d4eed69","datavalue":{"value":"extremal graph theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q286751$C88EEBA2-460B-488D-BA21-3708F0C039D8","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"65ecab2b160d7c5dac7f98d1dfded5f9a41c242e","datavalue":{"value":"Q59072428","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q286751$12AC9CC6-84FC-493C-B46C-BAE16295A9B8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"12c49c6b2683d960df1667a3988cd2add9e5c165","datavalue":{"value":{"entity-type":"item","numeric-id":295821,"id":"Q295821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q286751$22F012A1-B085-4F8D-B137-F162F4137BDA","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":"Q286751$885E3788-66D9-4EB9-9A01-F01688469C95","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3d34340743cb0e75ce014804cb6608f44140e88b","datavalue":{"value":"10.4310/JOC.2016.V7.N2.A3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q286751$CF186FC4-0344-4081-9C60-B5AD25498871","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9bdac223ff7771ecbd6ce61588212c7e5664a2b8","datavalue":{"value":"Given two graphs \\(G\\) and \\(H\\), an induced \\(H\\)-decomposition of \\(G\\) is a collection \\(\\{H_1,\\dots,H_k\\}\\) of pairwise edge-disjoint induced subgraphs of \\(G\\) such that each \\(H_i\\) is isomorphic to \\(H\\) for \\(1\\leq i\\leq k\\) and the edge set of \\(G\\) is a union of the edge sets of \\(H_1,\\dots,H_k\\). Except when \\(H\\) is the complete graph on \\(2\\) vertices, not every graph \\(G\\) has an \\(H\\)-decomposition.NEWLINENEWLINEThe following interesting problem was proposed by \\textit{J. A. Bondy} and \\textit{J. L. Szwarcfiter} [J. Graph Theory 72, No. 3--4, 462--477 (2013; Zbl 1261.05082)]: given a non-complete graph \\(H\\) with \\(v\\) vertices and \\(n\\geq v\\), what is the largest number of edges \\(ex^{\\ast}(n,H)\\) of a graph on \\(n\\) vertices that has an induced \\(H\\)-decomposition ? \\textit{N. Cohen} and \\textit{Z. Tuza} [ibid. 78, No. 2, 97--107 (2015; Zbl 1305.05119)] proved that for every graph \\(H\\), \\({n\\choose 2}-\\mathrm{ex}^{\\ast}(n,H)=o(n^2)\\).NEWLINENEWLINEIn this paper, using design theoretic and combinatorial tools, the authors proved that when \\(H\\) is a complete multipartite graph, then \\({n\\choose 2}-\\mathrm{ex}^{\\ast}(n,H)=O(n)\\). The paper concludes with several interesting directions (5 conjectures and 1 problem) for future research.","type":"string"},"datatype":"string"},"type":"statement","id":"Q286751$F050ACD3-5266-420C-BEAE-74566D6B9A23","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f88c81bf82a4620478d6f1a8734a95bceabf084","datavalue":{"value":{"entity-type":"item","numeric-id":2940990,"id":"Q2940990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea6589e83e60a5b2d92feaf9cb1f60fd2ac79832","datavalue":{"value":{"amount":"+0.8498824834823608","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":"Q286751$182F0127-8CF3-48A0-AB68-3CB0A279836E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5315cb634b115816d5197c5a28bafbba03b7e10b","datavalue":{"value":{"entity-type":"item","numeric-id":4916103,"id":"Q4916103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb0ea6c83d832c76317bfa09c18953726f9c42f0","datavalue":{"value":{"amount":"+0.8341749906539917","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":"Q286751$643C754A-1DB7-4E02-BD9B-717858B9B1ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"876fa2dcccdae65a9c3471897604daf0e5779ca2","datavalue":{"value":{"entity-type":"item","numeric-id":2765166,"id":"Q2765166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"04fba0783f522e446d1a1b28192397c18318a290","datavalue":{"value":{"amount":"+0.775956928730011","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":"Q286751$62ACF20C-E857-4B77-B23D-226C034C53BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f5f9fcd2e485a1ea9d667ddd6af4711ca5d5a1ff","datavalue":{"value":{"entity-type":"item","numeric-id":2760991,"id":"Q2760991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c927457e8cedb75a6a30c98012bca20d0e1a9bf7","datavalue":{"value":{"amount":"+0.7730563879013062","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":"Q286751$1876A0BB-9AE0-4DFB-956B-A74D519D9562","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aaea6a9a0d5a451ad8b0980083d38060d82d0194","datavalue":{"value":{"entity-type":"item","numeric-id":1356692,"id":"Q1356692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7803d998760c8b407de08ae71d5ff796c3253337","datavalue":{"value":{"amount":"+0.7711842060089111","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":"Q286751$6B18FB0E-B405-47C3-B4DE-A7F5D0B075B5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Transversal designs and induced decompositions of graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Transversal_designs_and_induced_decompositions_of_graphs"}}}}}