{"entities":{"Q870972":{"pageid":872820,"ns":120,"title":"Item:Q870972","lastrevid":50052100,"modified":"2026-01-12T19:46:51Z","type":"item","id":"Q870972","labels":{"en":{"language":"en","value":"Minimum degree and the minimum size of \\(K_2^t\\)-saturated graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5134179"}},"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":"Q870972$0A5FC2B8-36C4-4A0C-82EE-E64A646677EA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c63c25295900815126d30b3ca9bee33b03b49958","datavalue":{"value":{"text":"Minimum degree and the minimum size of \\(K_2^t\\)-saturated graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q870972$E57E0FA7-65A7-4B76-AC31-02EBC578ED3C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f17186db50e1eef334a7440118bafba83289897c","datavalue":{"value":"1116.05040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q870972$082AC965-D07D-43B5-8A72-14ED6B1E8A0A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870972$11443059-13BF-4162-B221-AE15C819B3BF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1c617fea8223e0e7484f67fc86050a1dce2e3fa3","datavalue":{"value":{"time":"+2007-03-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q870972$578BBCE5-A4BC-4C10-91DA-4713D9E49762","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"29f5b7debd5cdcd80d0d97bb783a3d2b56a9d6fc","datavalue":{"value":"A graph \\(G\\) is \\(F\\)-saturated if \\(G\\) contains no subgraph isomorphic to \\(F\\) but for any edge \\(e \\not\\in G\\), \\(G + e\\) contains \\(F\\). The minimum number of edges in a graph \\(G\\) of order \\(n\\) that is \\(F\\)-saturated is denoted by \\(\\text{sat}(n, F)\\), and is denoted by \\(\\text{sat}(n, F, \\delta)\\) if only graphs \\(G\\) of minimum degree \\(\\delta\\) are considered. It is shown for \\(t \\geq 3\\) and \\(n \\geq 4t - 4\\) that \\(\\text{sat}(n, K_2^t, 2t - 3) = \\lceil ((4t - 5)n - 4t^2 + 6t - 1)/2 \\rceil\\), and \\(\\text{sat}(n, K_2^t) \\geq \\lceil ((4t - 5)n - 4t^2 + 6t - 1)/2 \\rceil\\), where \\(K_2^t\\) denotes the complete multipartite graph with \\(t\\) parts of size \\(2\\). It is conjectured there is equality if \\(t \\geq 3\\) and \\(n\\) is sufficiently large.","type":"string"},"datatype":"string"},"type":"statement","id":"Q870972$77A7F946-AF75-42D9-B725-EB8950273D2B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q870972$1AB13505-E9FF-4085-BD00-39D1BED85E2B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0fec3520d00379c3727957ef6c84e28aadeddc00","datavalue":{"value":"5134179","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q870972$353D0214-61D8-441C-AEC3-6EA7CD6C46F6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac85d3d7ac91eadbdc14a3224d5dc4f2a1f5b2bc","datavalue":{"value":"minimize size","type":"string"},"datatype":"string"},"type":"statement","id":"Q870972$E10B9BE9-AB2C-457A-BAC4-A8A1A6016C2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4cdf1248bc0ea9c282c5a6c81401c836b40beb98","datavalue":{"value":"complete multipartite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q870972$2AEA1AFC-AE75-4B64-AA6B-1BC2A5E9FA16","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"46a94d04410c6537d8cdaa956c63781ba0b67be4","datavalue":{"value":{"entity-type":"item","numeric-id":175503,"id":"Q175503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870972$F2150813-90C2-4019-8623-75981D45417B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3949fe61a26fe64d4e54dd636eea0a107cb2994a","datavalue":{"value":{"entity-type":"item","numeric-id":418888,"id":"Q418888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870972$E5F4D042-F6D1-40FC-878A-F554B7182BE3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"69ba710ec323ba2b1e2239c5bdd6e4165b935d93","datavalue":{"value":{"entity-type":"item","numeric-id":175582,"id":"Q175582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870972$3B3D3CCD-A1DF-48D9-9B55-E594F3D0B065","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":"Q870972$D83B4578-153C-4E2E-A1E8-19E9962F80CC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9035c79729311a4dff7344cc79ebc3dec47f1d47","datavalue":{"value":"https://doi.org/10.1016/j.disc.2006.08.004","type":"string"},"datatype":"url"},"type":"statement","id":"Q870972$1F3661A6-8C63-43B9-B1DA-AA5237A627AD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2caadd55c8e2f96f9796851edc4a7b339713ae35","datavalue":{"value":"W2157319413","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q870972$ECB470B7-6EA7-4E50-A890-5F04C4462036","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5899e3e12a743d53573a910fcbfa636f0f6c8e3","datavalue":{"value":{"entity-type":"item","numeric-id":3852212,"id":"Q3852212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870972$1DF3119E-D061-4B9C-A77C-1D6592FEDF48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"616c1fc0b0281a6299f5fafa1062dc4e32f49683","datavalue":{"value":{"entity-type":"item","numeric-id":4871771,"id":"Q4871771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870972$D2B0F468-D1E5-47D2-8118-D440AA730C59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85bad6a4cc3cc767bc986564406cc7e839b5bbee","datavalue":{"value":{"entity-type":"item","numeric-id":3722535,"id":"Q3722535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870972$60925EEF-38AB-4E91-B1FF-BD4068196152","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6003b20622a76e9dda63a260950197adafe9dcb8","datavalue":{"value":{"entity-type":"item","numeric-id":5331782,"id":"Q5331782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870972$CE0C568D-58B0-445D-983C-5F52D2AA7059","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cb44fa19ef432ebe70a929dc7ab6c3c9375a250","datavalue":{"value":{"entity-type":"item","numeric-id":3722536,"id":"Q3722536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870972$B6F586CD-D6A7-4D17-911C-FEC99C5E77BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"19693d4199136cbc18283e73930e8f56bf6ba031","datavalue":{"value":{"entity-type":"item","numeric-id":5678889,"id":"Q5678889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870972$A780BC91-2CFC-44EF-A9F4-61F3714032D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59d7427adc632af85510201db03d040d32e5ae5c","datavalue":{"value":{"entity-type":"item","numeric-id":4934787,"id":"Q4934787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870972$42039131-B50D-493D-8712-9684F9566ED5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b71402670da660f99dbee96fb16e733a8ef3da58","datavalue":{"value":{"entity-type":"item","numeric-id":5750884,"id":"Q5750884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870972$A1FEBC82-A9A0-412C-AD20-BCA0E2856268","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3c006beaed3207aff0e3e504a350810ddc8a38fa","datavalue":{"value":"10.1016/J.DISC.2006.08.004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q870972$319723AB-1952-426F-8D24-D3FB4F1A6F4B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c8a960d457c02711a5b46773d4e7c967cc96643f","datavalue":{"value":{"entity-type":"item","numeric-id":5366942,"id":"Q5366942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72d68c588f5724de197d1633aa1a4a6ef51997f3","datavalue":{"value":{"amount":"+0.8647865056991577","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":"Q870972$ED0BD713-67E5-4B4A-819D-46FB05ABD210","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa10888df388c48fb72345df91295714f31a4dd5","datavalue":{"value":{"entity-type":"item","numeric-id":5495889,"id":"Q5495889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47980a94d2425971fc3a3a0990c6299bc65275d2","datavalue":{"value":{"amount":"+0.8547935485839844","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":"Q870972$F063542B-4989-4179-8B87-605C1CCC9804","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c23a74a09e3e2707559824d2abbf8e3860e6b827","datavalue":{"value":{"entity-type":"item","numeric-id":5113451,"id":"Q5113451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e3e62954d792302873696c619cfa0c65861150cd","datavalue":{"value":{"amount":"+0.8191248178482056","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":"Q870972$BAC7437E-E24F-4581-AFE5-FDD2A917DB6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"71b7cd83516f9da9baf475108104b21331b111c3","datavalue":{"value":{"entity-type":"item","numeric-id":5963384,"id":"Q5963384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef6980d99342af090a106bbac729559b99345888","datavalue":{"value":{"amount":"+0.8172475695610046","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":"Q870972$64918D90-9186-48D0-8611-BDC1E9BED483","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2fb5bf4d59e2501dc0f35811441ae46626d9cc33","datavalue":{"value":{"entity-type":"item","numeric-id":482117,"id":"Q482117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6bfa4b25c5f564a3f8301f8329bb1e9f94171665","datavalue":{"value":{"amount":"+0.8141950964927673","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":"Q870972$641A0DD5-61CB-46E6-AA9E-68729E8F5E42","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:870972","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:870972"}}}}}