{"entities":{"Q1359371":{"pageid":1370110,"ns":120,"title":"Item:Q1359371","lastrevid":67488357,"modified":"2026-04-12T18:21:11Z","type":"item","id":"Q1359371","labels":{"en":{"language":"en","value":"Binary labeling of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1029264"}},"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":"Q1359371$6E3CDE6F-2703-44A5-8A36-D66EF850FA71","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8a29ab22c7800296d97b80e84ebd4944892319ca","datavalue":{"value":{"text":"Binary labeling of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1359371$3B99AE30-91AC-43BB-9B61-C0163315A6D4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fdf04eba2fa0ef050d9f00f1d5cd202b7cb591bd","datavalue":{"value":"0878.05074","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1359371$CFC1E63D-87CB-4270-8B4D-B2FDD937D1D7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2af7e4201821ce1c9dc67b7f2917f9f02f10bd47","datavalue":{"value":"10.1007/BF03352990","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1359371$B5CA21E7-0851-4DF0-A0F0-635F22A5ED23","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e620da4866036e8f0d7f7254068b12c32cb4afa0","datavalue":{"value":{"entity-type":"item","numeric-id":328466,"id":"Q328466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1359371$F29493CA-8D92-4336-AC6C-65225576553C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"17db24281319b2394a2c233ebef5f5e55ce49ef5","datavalue":{"value":{"entity-type":"item","numeric-id":1347954,"id":"Q1347954"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1359371$F1706E66-B81F-47F0-B26D-DCBD634DF2D4","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":"Q1359371$87202313-5C92-4B5B-A740-C1B51D89E464","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0a6aa0fabb8302c7b392ccf1aabfb5c0ffb70a1f","datavalue":{"value":{"time":"+1997-07-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1359371$8C4CC586-55C0-4E8A-B5D9-A70914F6F20C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"51dbbadfcb449600e9954f7e0f54488e09fae977","datavalue":{"value":"A mapping \\(f: E\\to\\{0,1\\}^m\\) of a graph \\(G=(V,E)\\) is called a mod 2 coding of \\(G\\), if the induced mapping \\(g:V\\to \\{0,1\\}^m\\), defined by \\(g(v)= \\sum_{u\\in V,\\{u,v\\}\\in E}f(\\{u,v\\})\\) assigns a different number to each vertex, where summations are taken modulo 2.   This paper studies the number \\(m(G)\\), which is the smallest value of \\(m\\) for which a mod 2 coding exists. A necessary and sufficient condition for the existence of a mod 2 coding is that every connected component of \\(G\\) has at least three vertices. This paper establishes a precise formula for \\(m(G)\\): it is shown that for graphs with no connected component with less than three vertices, \\(m(G)=\\lceil\\log_2|V|\\rceil\\), if \\(|V|\\) is not of the form \\(2^k-2\\), and \\(m(G)=\\lceil\\log_2|V|+1\\rceil\\), if \\(|V|\\) is of the form \\(2^k-2\\), for some integer \\(k\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1359371$EE354D43-08C6-4A6A-A7A8-9EEBE3FAAD66","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1359371$28DC83D2-F49F-4702-8E7F-1AB50796CAF6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"511f8d14a4ebf1c6be0638d683ec72d3d3f3edca","datavalue":{"value":"1029264","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1359371$CBA0FDF6-C506-4CE3-B8DB-4A7BF1127AE4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb5dbb9c018c941d87d8ebd9a9c3e079d8ffa0f1","datavalue":{"value":"labeling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1359371$7DE323B7-D1AD-4DB8-94CA-90135B28423B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8ddc84d0bd7587c2bd86897b4a6314bdd2914d19","datavalue":{"value":"coding","type":"string"},"datatype":"string"},"type":"statement","id":"Q1359371$917E58B1-4B84-4E8F-BB0C-FD33A2F17E58","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":"Q1359371$837E14F9-8531-4304-8B6D-693AA477399F","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":"Q1359371$B9BFF6A6-D0D3-4B32-875B-22CB64CBF610","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd8ed1031c484366eb171d8a68af52813a54e447","datavalue":{"value":{"entity-type":"item","numeric-id":1323484,"id":"Q1323484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1359371$F58EC10B-6295-4331-983B-3E56ADB95AF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e3a890dad0d12ea3eced2498b454491b8adfcb6","datavalue":{"value":{"entity-type":"item","numeric-id":3970584,"id":"Q3970584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1359371$8C961540-27C2-4041-A573-78FADFE33A15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"87e526e77d3b54cb7f01f30178c69c66b84084b5","datavalue":{"value":{"entity-type":"item","numeric-id":3971995,"id":"Q3971995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1359371$98A89A36-5486-4CD7-8C32-7A81D2B8CB13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aebac9cb7e2f47a54c3fb82c2b619fdd3b8a641c","datavalue":{"value":{"entity-type":"item","numeric-id":4044627,"id":"Q4044627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1359371$BDC9642C-3CFB-4ED2-802F-22A01C4427EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b655f65f59e6f2997d770fc5a3523570e020ab6e","datavalue":{"value":{"entity-type":"item","numeric-id":3472148,"id":"Q3472148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1359371$8C9BD9B3-C588-4292-A335-426AA7A78813","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7eff687c123f7105211d942b54ab55e76a2186d9","datavalue":{"value":{"entity-type":"item","numeric-id":4373384,"id":"Q4373384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1359371$D75E3786-BEB7-413C-B5F9-70281856C81E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c3b074efccc27c3aa25ebb2b0341556544efffc","datavalue":{"value":{"entity-type":"item","numeric-id":3803160,"id":"Q3803160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36cfdba30944fba816324323379d591be3f12405","datavalue":{"value":{"amount":"+0.93214387","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":"Q1359371$8AAAAAE3-DAD5-454C-9AF8-B7024E8B7DB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66089fe92926e5c92ad1dd7a29ec056a85abf6f2","datavalue":{"value":{"entity-type":"item","numeric-id":1323484,"id":"Q1323484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c6c8388876d61eb480a90be04e294f458a8be700","datavalue":{"value":{"amount":"+0.91753596","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":"Q1359371$48B76196-376A-4546-94BC-5681BB86BD1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b86a7ec9b0c1d3c53bdb3e52b3d10fe7bb836653","datavalue":{"value":{"entity-type":"item","numeric-id":5284649,"id":"Q5284649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a776b5911c20f375bdfab4f8538f5a39cc64566","datavalue":{"value":{"amount":"+0.91705537","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":"Q1359371$FE6C0FA9-9B33-441B-865B-246ADC0A1C3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e4854a664bd22f51b8191cacd1a54eedb6d9bc9","datavalue":{"value":{"entity-type":"item","numeric-id":2760983,"id":"Q2760983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4bde6e460d0236f4649c42530745f20da861ebd1","datavalue":{"value":{"amount":"+0.90600884","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":"Q1359371$D7E70BB8-20B5-4908-B821-F6A8D27199E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"649c910ecbdd0a7e799660610270a4d19275b15c","datavalue":{"value":{"entity-type":"item","numeric-id":3682513,"id":"Q3682513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24ca87c40cdd0d69ff5618d5217e60471372341c","datavalue":{"value":{"amount":"+0.90495574","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":"Q1359371$1A3F865B-26DE-4FD7-AC43-AD231AF73D33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"497990f06a3b545326766145a1b96ce7f1626ab8","datavalue":{"value":{"entity-type":"item","numeric-id":3472148,"id":"Q3472148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"678122d7ef9b23b8a8a9d7ff45555f95df1690aa","datavalue":{"value":{"amount":"+0.90279865","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":"Q1359371$7B26F1A9-EAF5-487B-8C03-151F851EEE9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2741d5f3853c1a8515e11b247b37ac96a564c184","datavalue":{"value":{"entity-type":"item","numeric-id":5284572,"id":"Q5284572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c3dc5af39ed9d6dd07c8a806d72aad53c62e60c","datavalue":{"value":{"amount":"+0.9026927","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":"Q1359371$7021C275-6B4F-43AE-9AAC-719E739ACB5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"851cdd49d66dc081a119b9d6cbb292ea41c83566","datavalue":{"value":{"entity-type":"item","numeric-id":5505216,"id":"Q5505216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ca6dfba88c3592fd04388f1efa3a3cd4893bc3d","datavalue":{"value":{"amount":"+0.89784324","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":"Q1359371$79D00EAD-D3F8-48A4-AFED-4CF9C31A77F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b449238ad8e28cbd83332fc1aebb85ab9b331665","datavalue":{"value":{"entity-type":"item","numeric-id":5411933,"id":"Q5411933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c004d0f10ad1334989e750077e0d9bd0f17e78d6","datavalue":{"value":{"amount":"+0.89582294","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":"Q1359371$6646616D-0E30-4604-8135-106519D04E4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ed2642287c9c0b08c71364c8daa00982b3e5239","datavalue":{"value":{"entity-type":"item","numeric-id":3989019,"id":"Q3989019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"325fdd72a4841790108f6eb9f39734abe14c37c9","datavalue":{"value":{"amount":"+0.8957752","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":"Q1359371$6C50B712-51B5-458B-AB3B-9B12E2CB88B2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Binary labeling of graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Binary_labeling_of_graphs"}}}}}