{"entities":{"Q1196569":{"pageid":1207318,"ns":120,"title":"Item:Q1196569","lastrevid":67072878,"modified":"2026-04-12T14:51:17Z","type":"item","id":"Q1196569","labels":{"en":{"language":"en","value":"Large regular graphs with no induced \\(2K_ 2\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 89199"}},"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":"Q1196569$32A4EBDA-2E1E-4BD0-9209-2B24826FE326","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c1e9114c2f468d7f8dd464c30bd03800e2745e6d","datavalue":{"value":{"text":"Large regular graphs with no induced \\(2K_ 2\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1196569$84A8BD45-D282-45AB-863C-64710B6FEC20","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0ab3bad0db89f12866eb1f89e2dcbc43666b6683","datavalue":{"value":"0764.05081","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1196569$C3459433-98E1-439D-B885-A8D25590986A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"071a2c9f84e73789f8c582b1284f2521f8cb9724","datavalue":{"value":"10.1007/BF02350634","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1196569$4459F868-48D7-4773-B23B-1C9576C517FB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fcb16e991356235c45945b62115ce3036aee697e","datavalue":{"value":{"entity-type":"item","numeric-id":1196568,"id":"Q1196568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196569$56E17824-CBF6-4C01-90A9-F474069255A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"947e64add15a6cbb9bd5eb0151aeee243e02fe24","datavalue":{"value":{"entity-type":"item","numeric-id":789410,"id":"Q789410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196569$513A8971-B940-41A3-B3C6-081A50BCC861","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7a539e6b59a5781e06906f6b0f6a357a21edb017","datavalue":{"value":{"entity-type":"item","numeric-id":792346,"id":"Q792346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196569$295490B3-ADAD-47A9-87AD-F9904418CCB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b4d4c73f0a1fcfa77f8c56f84fd9c0566fb0d581","datavalue":{"value":{"entity-type":"item","numeric-id":185079,"id":"Q185079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196569$39F84C7E-4DA5-4788-9D9E-FC99ADA3F42A","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":"Q1196569$458AB439-D480-489E-9AD1-7F9A6BF9E9D6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be1a65edbb43ce1fc59464f99e70afbd93e8e2a0","datavalue":{"value":{"time":"+1993-01-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1196569$EC66099F-6890-4417-ADCD-EBF24D0AED74","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d904bf521f86ad8e77e144ae4f8ebe2fbbea0e45","datavalue":{"value":"Let \\(H\\) be the disjoint union of two edges. A graph is \\(H\\)-free if it does not contain \\(H\\) as induced subgraph. This paper studies regular \\(H\\)- free graphs, of which the cycle \\(C\\) on 5 nodes is an example. It is first shown that any regular \\(H\\)-free graph of degree \\(r\\) has at most \\(5r/2\\) vertices. Let \\(v\\) denote the number of vertices of a regular \\(H\\)-free graph of degree \\(r\\), then it is conjectured that when \\(v>2r\\) then \\(r\\) is even and \\(v/r\\) is of the form \\(2+1/(2k)\\) for some \\(k\\). After deriving several structural properties of such graphs, a proof of this conjecture is obtained when \\(v\\geq 21r/10\\), in which case only 7 basic graphs exist from which all others may be derived by expansion, i.e. replacing all vertices by a fixed number of nonadjacent vertices, and each edge by a complete bipartite graph. It is also conjectured that this type of result holds more generally.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196569$51DC9471-9626-4923-90EE-8D746E4EA0A7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1196569$64F3D3C5-969D-4486-817E-3E74DA502908","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1196569$D5AE774F-FDAD-4C7B-AFDA-C2EF8A19B3CE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"761a4b0cecf6a83bd7eebd9da0693705c0808bc6","datavalue":{"value":"89199","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1196569$86F08781-3E65-45B5-95BF-8BA5C690DE33","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34012c92c499b6a6beb6c6030b4f33ccbf9f4fcc","datavalue":{"value":"regular graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196569$A7643410-15AF-43AC-9FF5-C8253274B074","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bdefd4725d91bba1e0d0861018fdd0e81ad28b3","datavalue":{"value":"extremal graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196569$6C98BF8B-B503-4701-9136-F4BA9CD70BD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84b8ba90bb01ea8a5ea4668498afd95d1a107981","datavalue":{"value":"excluded graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196569$0525D14C-6499-4751-AC5B-42B247429297","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"67e275f4c5e3f283b692104c20347075fa270e17","datavalue":{"value":"interconnection","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196569$04E9877B-79DD-4799-BA69-9D66C025ECD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"322e81307d2b59f8312b677cec0801774fd4d8e5","datavalue":{"value":"networks","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196569$AD3F702F-3E18-4DA2-98EA-AD69F5DF3C40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3187e84c5efaed03d0bd9515713a70084404d3ee","datavalue":{"value":"bipartite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1196569$CDA9BDE9-A346-461F-B3CE-66950C83807C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5e09f3da1a7483864918926ab5885138a8f45aaa","datavalue":{"value":{"entity-type":"item","numeric-id":166210,"id":"Q166210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196569$3FB99DDA-BA3C-490E-B408-4B700FBC76BF","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":"Q1196569$AF3D5531-A73C-4239-BF6D-5B2A0F86E474","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c0fd39281a799453c11c1f2ece6adebfe56db4c","datavalue":{"value":{"entity-type":"item","numeric-id":3039368,"id":"Q3039368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196569$CF18F03C-D661-4451-B4EC-3A1C857A4B21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f996b3302eb6630198a79cb9560ddd068056c1b","datavalue":{"value":{"entity-type":"item","numeric-id":3780901,"id":"Q3780901"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196569$379C8551-1620-468C-9074-8971A7BA493A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0f73be776408be252e6928c1d0ae615a65f3aa6","datavalue":{"value":{"entity-type":"item","numeric-id":912124,"id":"Q912124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1196569$8063D3B6-F1AC-49B0-AB1C-5906C1FAF77D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"605a35ed10fb7ceb7302c767eb24f917de55e229","datavalue":{"value":{"entity-type":"item","numeric-id":1799386,"id":"Q1799386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0413604b8bd0b06a03795407a859c96ed86060ac","datavalue":{"value":{"amount":"+0.8159637451171875","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":"Q1196569$E26C2A0E-851E-4E32-8DDA-7F89C9E46030","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1121227a7af9e6adc1069634d77f03f7378ae4e1","datavalue":{"value":{"entity-type":"item","numeric-id":1916098,"id":"Q1916098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4e23354eb9dc7b69cb3ac6d7f13dabaac3ef0e9","datavalue":{"value":{"amount":"+0.8082834482192993","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":"Q1196569$D4D2F64F-1A28-4559-84A9-42EADCB27F4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0dcc094b27355f9936556a5536a9ece8de93bbc5","datavalue":{"value":{"entity-type":"item","numeric-id":1182587,"id":"Q1182587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff738754f9bfb0f4ef0c9b0d8a26bda017a7b8f8","datavalue":{"value":{"amount":"+0.7931001782417297","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":"Q1196569$F7163CF3-F848-4788-ADD4-EC081A38895F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1200d6ab8f23c74c95ab5b47274a8bdae8b7aa6d","datavalue":{"value":{"entity-type":"item","numeric-id":2442274,"id":"Q2442274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84db57994246c2e232cb37a250f9b79c664ef32a","datavalue":{"value":{"amount":"+0.7911601066589355","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":"Q1196569$FADE17EE-DB46-4449-8E98-789095DE2C1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"52ae4f858aab5dc909e826d2768f24e022e6fde7","datavalue":{"value":{"entity-type":"item","numeric-id":503635,"id":"Q503635"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56320b0208a2f5e5dd8f540c6454bd1a5936e85f","datavalue":{"value":{"amount":"+0.7909918427467346","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":"Q1196569$FB4659A1-D6D3-441C-957C-CAA5FEC19783","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Large regular graphs with no induced \\(2K 2\\)","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Large_regular_graphs_with_no_induced_%5C(2K_2%5C)"}}}}}