{"entities":{"Q1567263":{"pageid":1578003,"ns":120,"title":"Item:Q1567263","lastrevid":74188551,"modified":"2026-04-14T18:51:58Z","type":"item","id":"Q1567263","labels":{"en":{"language":"en","value":"The computational complexity of cordial and equitable labelling"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1455600"}},"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":"Q1567263$BC0FC583-E65D-42A5-89DB-7D9B62484098","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"042fe3908bf646f1ca03b91ce4432a4b91e91f22","datavalue":{"value":{"text":"The computational complexity of cordial and equitable labelling","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1567263$C44264F3-FE7F-4CAB-B12C-BD79C7477B61","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ccbef47aa8b6a5c0636e878fcf06569575fffa64","datavalue":{"value":"0951.05091","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567263$CA964EC6-E874-4A95-A85F-86835DF6D6EF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3ca368a3a31da402836abf9aeae3932174ceb40d","datavalue":{"value":"10.1016/S0012-365X(99)00295-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567263$EFE4CB3A-27F0-47C6-86BB-B46474E74F0A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"620a269ea311c8369f29c3cf92b7bc6d6c006d75","datavalue":{"value":{"entity-type":"item","numeric-id":1567261,"id":"Q1567261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1567263$E35CA326-117E-4C8F-8C1C-A75E25481D74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a6e1f9ad498b53f98afc6a2f82e96c5f4554c2c2","datavalue":{"value":{"entity-type":"item","numeric-id":383737,"id":"Q383737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1567263$87EDE2CE-77B3-4521-8864-8649B5A69ABE","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":"Q1567263$84148FC7-4A22-48EA-85CF-BCA795D5B201","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b5292801f0dd79298539819e0a4ac0e822803e06","datavalue":{"value":{"time":"+2000-12-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1567263$CC639591-443E-4CCD-B256-50FBBCCDAC1D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"78e9586b4c3054543df6c7b1a1b3f8f7ed98c417","datavalue":{"value":"For a graph \\(G=(V,E)\\), a labelling \\(f: V \\rightarrow \\{0,1,\\ldots, k-1\\}\\) is \\(k\\)-equitable, if for each \\(0 \\leq i < j \\leq k-1\\), we have \\(|V_i|- |V_j|\\in \\{-1,0,1\\}\\) and \\(|E_i|- |E_j|\\in \\{-1,0,1\\}\\), where \\(V_i\\) is the set of vertices with label \\(i\\), and \\(E_i\\) is the set of edges \\(\\{v,w\\}\\) with \\(|f(v) - f(w)|= i\\). A 2-equitable labelling is called cordial, i.e., the vertices are partitioned into two sets of equal or almost equal size, such that (about) half of the edges are between vertices in different classes. It is shown that it is NP-complete to decide if a given graph has a cordial labelling; and hence it is also NP-complete to decide if a graph has a \\(k\\)-equitable labelling. As an intermediate result, the authors show that the problem, given a graph with an even number of edges, to decide if the vertices can be partitioned into two classes with exactly half of the edges from one class to the other is NP-complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1567263$C8D1AC06-6E56-4A37-8539-5DF23763B15B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567263$6C5A167A-1FCC-4706-8D8F-C7D63E1CC314","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567263$36316265-E545-469E-B106-F327D40DAA12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567263$0DFF84B9-EE1B-48F6-B1D6-830236A1FA15","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9eaf01aebf28640cc6af67383c3cad6081451ef5","datavalue":{"value":"1455600","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567263$B972E20F-1F93-4152-B1E7-11A30A37A3E9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0e68c8f327b17ce9b529ada2f4d2afbaa0cfae5","datavalue":{"value":"graph labelling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1567263$6CAA8B5B-89CA-4465-83AB-5FD768E92A44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d406d4d9e5d8199a3662df5f8373080eeea6302c","datavalue":{"value":"cordial graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1567263$B638068E-6D03-451E-9074-56EF7474A73A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff51aed71fb6550d711cc1f53df12753e12bc5fa","datavalue":{"value":"equitable labelling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1567263$C39263CE-110C-4E05-BFB2-8831DA79E6F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1567263$79D44AE9-A819-4C68-8C79-473281447AAB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"eea1ea35de576c62b8101835521aa928ecd629a1","datavalue":{"value":{"entity-type":"item","numeric-id":242851,"id":"Q242851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1567263$D77EB464-6143-4354-8B66-883037CB44CB","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":"Q1567263$AC87AA4D-BE26-4D86-868D-83E3A040A91D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5c2351e6852ea789061188768c7bee071649c966","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(99)00295-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1567263$53918CC3-E1B1-446C-B2AE-8226BFFE29C6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7968c4177caad7fd9362411aa85ee2f8f9467ff4","datavalue":{"value":"W1999087527","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567263$A1059283-D417-4AB5-A43E-F59A53EBE56C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3f9c8a3804668ac427fa95d2c0808615a7fe712","datavalue":{"value":{"entity-type":"item","numeric-id":391137,"id":"Q391137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b7236933498ba7a63730fbecb6071555eed5421c","datavalue":{"value":{"amount":"+0.85217434","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1567263$DF22FF82-F416-4659-962E-12A4B3052C21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"226b328a14095acb8d2d00ea190353e5fab9d6f1","datavalue":{"value":{"entity-type":"item","numeric-id":847807,"id":"Q847807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02e3ac821072ac1ee9787a92698ffc54ac0472e6","datavalue":{"value":{"amount":"+0.83444345","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1567263$3D5DBF8F-258B-4A91-8FD8-AA6BC23E6FF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c86e3a180c490beea1807c316611762094bed2db","datavalue":{"value":{"entity-type":"item","numeric-id":967327,"id":"Q967327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"289b1c60ff1f1615842c9f32fa195079da3c344a","datavalue":{"value":{"amount":"+0.8329047","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1567263$609F198F-6766-47EC-80F0-30530BEAFDAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22a7d615bbd419083b6d0178c1fcb722c7e72759","datavalue":{"value":{"entity-type":"item","numeric-id":4997758,"id":"Q4997758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c62a6ccfce92ccbb819355521db54cd8098a669","datavalue":{"value":{"amount":"+0.83264256","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1567263$AAC6FF1F-9EAA-42BA-B339-6CC28F06C5E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc989d7f7e985968889da58213d1bbac0ad93d8e","datavalue":{"value":{"entity-type":"item","numeric-id":5403271,"id":"Q5403271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc28f78622264b67028b0d8f906fe088625bcf59","datavalue":{"value":{"amount":"+0.8289324","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1567263$2DB2228C-AAF4-4CDE-A46F-4A0623DD2286","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63ddf74c349cccb831f00a2e8fa91ed9c6753f19","datavalue":{"value":{"entity-type":"item","numeric-id":3100700,"id":"Q3100700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a82c8ab385d72fd673eaeb412d01c3b63187ac55","datavalue":{"value":{"amount":"+0.8247757","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1567263$1F60644B-EF37-4E3F-958C-2114F1E500AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ecdf7c19e6a874f915f318cfaec60ea707c848f","datavalue":{"value":{"entity-type":"item","numeric-id":6065235,"id":"Q6065235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0617440128b379082b16b65126be61d0ccec71bc","datavalue":{"value":{"amount":"+0.8246217","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1567263$105E8C0F-877E-477F-A285-5CE4B0E5094D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"50191ad05d43650f6dc3e4058f317bba8a924163","datavalue":{"value":{"entity-type":"item","numeric-id":4335302,"id":"Q4335302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4f5c4928bcf078e034e76d71d064401a88cd3b7","datavalue":{"value":{"amount":"+0.8245988","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1567263$4FEB9A26-EDDD-4096-91DF-90017902531A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a6ac61d5dbf2bb2c6534cfeb558fa38bcfa4c25","datavalue":{"value":{"entity-type":"item","numeric-id":2031932,"id":"Q2031932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4cee4e373e67fba0781da037606939c8e7d3ccd2","datavalue":{"value":{"amount":"+0.8225095","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1567263$A0742531-077B-4FC7-AF13-AA598AAD1C47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c94de0bb9cefe8a80b329ceb315613ac0b1b27d8","datavalue":{"value":{"entity-type":"item","numeric-id":3199455,"id":"Q3199455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5fbdff67133c59c8c8ce767777789c7702fb0d83","datavalue":{"value":{"amount":"+0.8216306","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1567263$263BA4B9-446F-424D-A95E-A51E73D0E567","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The computational complexity of cordial and equitable labelling","badges":[]}}}}}