{"entities":{"Q1322229":{"pageid":1332979,"ns":120,"title":"Item:Q1322229","lastrevid":70135746,"modified":"2026-04-13T12:41:23Z","type":"item","id":"Q1322229","labels":{"en":{"language":"en","value":"Independence and the Havel-Hakimi residue"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 562631"}},"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":"Q1322229$06E7F951-B612-4D5D-80EA-9A6C15C2BD5B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4102f204fefe285a0d1102ee7762ccdeaf7aaec5","datavalue":{"value":{"text":"Independence and the Havel-Hakimi residue","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1322229$34002EAB-5B5F-4105-84B1-850CFD9088D0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d6537a38bef98acce69606149fdd4ecbd72a542f","datavalue":{"value":"0805.05082","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322229$19E1ADBA-C95C-4460-99BB-4D127EC8A81D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3020559bd49d03381e3c3ed7b8b61efd7612fe6e","datavalue":{"value":"10.1016/0012-365X(92)00479-B","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322229$8D325934-B1E8-4CB3-9519-17BBD2B32175","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7eea8e7d77c3bd85961dad34f48622f9613bb045","datavalue":{"value":{"entity-type":"item","numeric-id":594100,"id":"Q594100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322229$AA16CE0F-CDDF-4671-879B-A0790252A608","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c19618e3b9c4bf1bd311347b0631dba005878939","datavalue":{"value":{"entity-type":"item","numeric-id":228778,"id":"Q228778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322229$674FD078-4416-4A6E-A2E2-7FDAF213A834","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":"Q1322229$C69D31D3-B9FC-4EF3-868B-16E8BF61BFB5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e2370192b51581a9089045828e517d05f104e988","datavalue":{"value":{"time":"+1994-06-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1322229$797A2101-25DC-4ABB-A857-B17B4C9129B2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"238908b679d63c7372f3565e4597255f81ab23c3","datavalue":{"value":"It is known that for every graph \\(G\\) the number of zeros left after fully reducing the degree sequences (as in the Havel-Hakimi theorem) is at most the independence number of \\(G\\) (cf. \\textit{O. Favaron}, \\textit{M. Mah\u00e9o} and \\textit{J.-F. Sacl\u00e9} [J. Graph Theory 15, No 1, 39-64 (1991; Zbl 0751.05075)]). In the present paper the authors find how the residue relates to a natural greedy algorithm for constructing large independent sets in \\(G\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322229$DB466039-F6B5-47F0-AC1C-5A36F35B92F2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322229$8EB33FCA-CDBD-46EB-AFAA-F1D711C9B16D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ab8eef56e70f4344928a6ab2df1e044698959c62","datavalue":{"value":"11B83","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322229$578C65B2-1C6D-4982-A5F5-F9C15190D71F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ca75fc0bcb64a6c86d64f8a947f745a95e08b921","datavalue":{"value":"562631","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322229$56B33F13-64B5-44C3-BD57-CCE172E77396","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d67aea78932b35b41389284d895628a7a3db6ffb","datavalue":{"value":"degree sequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322229$DA7C4CEF-38A7-4A9B-95AB-7364CC8F00C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fa99d059bb8a600e8ddcc9e1781e97ad348b3d6b","datavalue":{"value":"Havel-Hakimi theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322229$580DB2AB-C697-4E67-B8B9-48CD0DC99816","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b89aa1b9eed71217ebf6a719487a219071558409","datavalue":{"value":"independence number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322229$058E98AE-33F2-43EB-957E-B3E2429FEEF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dae2f4c43b81f5dbf7a3b5468af248257c9d9172","datavalue":{"value":"residue","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322229$C0A7931A-E65D-48E8-B3FC-675AEB49B8B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e1e7eb452ae4c92c43fa47bb0afb8177365a429","datavalue":{"value":"greedy algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322229$D8C03198-4B64-442E-B689-9D8961FFB012","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9890d2d31de82fcf86b74b799289b36efeaabea2","datavalue":{"value":"independent sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322229$159522F9-D8D3-46E5-B1F5-7A54068A636C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b2c2655a640349f26e36b17bff804844b8b0fc11","datavalue":{"value":{"entity-type":"item","numeric-id":1056904,"id":"Q1056904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322229$8603B907-C724-4981-BA7D-F7ACB51C9097","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"46dddb69316252419883bbcaa807e09be308a899","datavalue":{"value":{"entity-type":"item","numeric-id":19524,"id":"Q19524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322229$55485762-0807-4FD4-A269-0423B0C7A14D","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":"Q1322229$C7EB617C-82A5-4F2F-AE63-819D050CB4E4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"13625bd5a8f36e424a6da73bb05877a54ee3cc46","datavalue":{"value":{"entity-type":"item","numeric-id":922723,"id":"Q922723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322229$E7C0222E-C211-4097-8614-AF7B9876917D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6813a3de92e62c4b8c0b35a196fcd89d24362f9e","datavalue":{"value":{"entity-type":"item","numeric-id":3970965,"id":"Q3970965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322229$BC240CC3-B382-45D7-BBB5-3022E8AA7221","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf6dd27ad1e0108f4014296aa58a9a489aabf84c","datavalue":{"value":{"entity-type":"item","numeric-id":1835927,"id":"Q1835927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322229$2A1ED31D-E7FE-4B18-A4D5-DEF53A62221E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26f3059e4f940eac09d1b1f27f742e6ceca91277","datavalue":{"value":{"entity-type":"item","numeric-id":3845889,"id":"Q3845889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322229$C7660E8B-ED7D-4250-BDB1-BADD07F027DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c7c2eaf8e4da4c4ea6a292122f8940e233bcad7","datavalue":{"value":{"entity-type":"item","numeric-id":3230887,"id":"Q3230887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322229$E45754BE-4285-419D-B23E-381C584B3161","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a567a0bd5149009c58baa277d371437f0fed769","datavalue":{"value":{"entity-type":"item","numeric-id":1213733,"id":"Q1213733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322229$0F54CF78-E28C-4252-9385-C795396E60F9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a86b58d3127cd669484d2c0dbd9a7c40ca5f0048","datavalue":{"value":"https://doi.org/10.1016/0012-365x(92)00479-b","type":"string"},"datatype":"url"},"type":"statement","id":"Q1322229$1B417C57-E99F-4670-AC6A-EC182A24ADFF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6a57684a00f1d3d5a013f21d6013e40df2100a55","datavalue":{"value":"W2089356095","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322229$7AE377C4-93FF-422E-9263-AB540AE74B58","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c299ba3f0d6608402d97860265b410a30f71181a","datavalue":{"value":{"entity-type":"item","numeric-id":763488,"id":"Q763488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47bf2d88c80a384f4ea8d3fb1e01f42235dfbf52","datavalue":{"value":{"amount":"+0.8681964874267578","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":"Q1322229$389CB98B-587D-4AAE-AA8B-9DD2047BEE28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"922055752d07393bad896d4fa4892aa37803aa27","datavalue":{"value":{"entity-type":"item","numeric-id":343704,"id":"Q343704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32361493c09d7fbdbe3af1435f4a4adb355ce251","datavalue":{"value":{"amount":"+0.8638903498649597","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":"Q1322229$FE21201C-7BD9-4B3D-B742-3DEDC09CAAE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e5106f58b4c5a5c7dbd1e797c718ce406fea8148","datavalue":{"value":{"entity-type":"item","numeric-id":3970965,"id":"Q3970965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15fa398fd4b6644fc8306e0a047bfc18a31e9577","datavalue":{"value":{"amount":"+0.8019849061965942","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":"Q1322229$F73BFFF8-07CB-4418-A5D3-A6848FA18E91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7dc374e57d82d288482c027a2a12d781256bcc56","datavalue":{"value":{"entity-type":"item","numeric-id":4718734,"id":"Q4718734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d98e9ebccf5fdb781a0cd4e4d3026d29daa95e6","datavalue":{"value":{"amount":"+0.7828636765480042","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":"Q1322229$EA1DB568-88B1-4645-97E3-C17B181266F8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Independence and the Havel-Hakimi residue","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Independence_and_the_Havel-Hakimi_residue"}}}}}