{"entities":{"Q640456":{"pageid":642304,"ns":120,"title":"Item:Q640456","lastrevid":57091008,"modified":"2026-03-26T13:36:50Z","type":"item","id":"Q640456","labels":{"en":{"language":"en","value":"The maximum independent sets of de Bruijn graphs of diameter 3"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5960056"}},"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":"Q640456$8B0953B4-9408-4BF5-B5CA-CBACAB05B028","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"08b632f35d29114af43acf079c38138d2c10e965","datavalue":{"value":{"text":"The maximum independent sets of de Bruijn graphs of diameter 3","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q640456$3141A718-396B-4994-B54B-D69562BBC3F0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d281d5646e1dc6a91ffdadc0e7b2a1d28728917e","datavalue":{"value":"1229.05217","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640456$93651E7B-6F4B-4A0E-990E-E6934A8E296C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d7a46643405b69ec3954e19555cc85579823d312","datavalue":{"value":{"entity-type":"item","numeric-id":640455,"id":"Q640455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640456$3A8DD290-31DC-43EC-9364-2227F1499798","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e2493e823d7ac9f97263dc65c2365ee9c0501e58","datavalue":{"value":{"entity-type":"item","numeric-id":358840,"id":"Q358840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640456$001A4410-5EA7-4F27-A391-FC9BC0A36D75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7addd87657686e24dc3682d1890357bb247b56e5","datavalue":{"value":{"entity-type":"item","numeric-id":607053,"id":"Q607053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640456$2B762E82-F6E4-4451-9A70-1D2210051965","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640456$4F690FC8-1045-49B7-9C07-4A3636085F85","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9767fe8dd1d6f9791ae763e9a67550b5f9aa27e1","datavalue":{"value":{"time":"+2011-10-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q640456$FA484A8F-6493-452F-A0C5-66CA713C8D8B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6992ca95c69e323c11d10aae9c7a86899268ec66","datavalue":{"value":"https://arxiv.org/abs/0905.3820","type":"string"},"datatype":"url"},"type":"statement","id":"Q640456$AF44C78E-CD08-46FF-95FF-600431C7388C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"3096c19820dcc8223f6809ea6a7da59b21906df1","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p194.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q640456$AB5E24AA-941E-445C-A77C-F24920C1F1FB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"edac65486a80e92044704f5d6c9e7040eb052d42","datavalue":{"value":"Summary: The nodes of the de Bruijn graph \\(B(d, 3)\\) consist of all strings of length 3, taken from an alphabet of size \\(d\\), with edges between words which are distinct substrings of a word of length 4. We give an inductive characterization of the maximum independent sets of the de Bruijn graphs \\(B(d, 3)\\) and for the de Bruijn graph of diameter three with loops removed, for arbitrary alphabet size. We derive a recurrence relation and an exponential generating function for their number. This recurrence allows us to construct exponentially many comma-free codes of length 3 with maximal cardinality.","type":"string"},"datatype":"string"},"type":"statement","id":"Q640456$14A412CB-662C-4E8F-94D9-A30AB9D33600","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640456$5040167C-8569-4F1B-88E5-4DC2F93F0A67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b6a686fef1013593a32f9e8e67eecdd50e96866a","datavalue":{"value":"05A15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640456$30AE36A3-18F2-4AB0-B640-3B68E4CD3BC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640456$45C6F809-07D1-4EB9-A19A-B939596142DF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c95ae87b52fa6c4182ac7984393f43bb1ee6a0aa","datavalue":{"value":"5960056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640456$D9A6333E-C131-4559-B4F0-67EA545DF4C8","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"c9c1f58b8025297b76815155d9e858d1b402d938","datavalue":{"value":{"entity-type":"item","numeric-id":12911,"id":"Q12911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q640456$A0CEA973-9495-4C36-8770-7C06E1119767","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":"Q640456$C0691C4F-93A0-4C39-9D94-877C2B145191","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"fba182a976b2660b93a460bfa4e2c0c144964329","datavalue":{"value":"bafkreigyovuyrli7wxje4gxfhisg57mkrk4h6zuh4eoiprs7du6m6ogv2a","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q640456$FBECAB42-28ED-47B0-95FE-D3638281F154","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1eebf12aed9759577005a99b73c7dca2ee6e1c9","datavalue":{"value":{"entity-type":"item","numeric-id":3343914,"id":"Q3343914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4ed4ea55755cb8c26e8a7d5623511b757784078","datavalue":{"value":{"amount":"+0.8234047293663025","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":"Q640456$92BA84DC-0C2E-4E1A-BD38-0C0AFBFC2C53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7e9faab194b289cc504e9642c323ed846a44661","datavalue":{"value":{"entity-type":"item","numeric-id":2497496,"id":"Q2497496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"279adea6d99c434731f6c93bfd8da5f59b6bf531","datavalue":{"value":{"amount":"+0.8085110783576965","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":"Q640456$6B3698C8-78E2-44C0-B671-FBE57F410226","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"583cdf8cca65b569c0534eb63ae61a5bc0a3ee98","datavalue":{"value":{"entity-type":"item","numeric-id":4795848,"id":"Q4795848"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"caaba8c60049c33550d399258e058e8626b87141","datavalue":{"value":{"amount":"+0.8012415170669556","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":"Q640456$381116D3-C51A-47E6-A232-7AD8A6A71B59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e03bb68caf7f52f18ff0cb992632075024724a7e","datavalue":{"value":{"entity-type":"item","numeric-id":4453135,"id":"Q4453135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e3cdbff3a7351487d28dec7b9a7ecf8ec4d9aae","datavalue":{"value":{"amount":"+0.7980232834815979","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":"Q640456$2652C898-1E68-4EE1-ADAF-50996B391FEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66c994f59efe8195bf9e5c6eb45dd94afae24ff0","datavalue":{"value":{"entity-type":"item","numeric-id":1176741,"id":"Q1176741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b7f00792847fb621f58572e2af75222fc9e412c3","datavalue":{"value":{"amount":"+0.7844904661178589","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":"Q640456$2B40CF75-A88C-4F07-A8CE-2A3417EF4D19","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:640456","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:640456"}}}}}