{"entities":{"Q1976593":{"pageid":1987335,"ns":120,"title":"Item:Q1976593","lastrevid":72155688,"modified":"2026-04-14T03:00:22Z","type":"item","id":"Q1976593","labels":{"en":{"language":"en","value":"A new property of binary undirected de Bruijn graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1445760"}},"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":"Q1976593$FEFA75EA-DBA3-4458-8A18-A1C169E467FE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"00fef3415aadfca3c4ab11aa529c572176b49309","datavalue":{"value":{"text":"A new property of binary undirected de Bruijn graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1976593$AFD81165-86BE-49C5-9197-4F18A6053983","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1b4fd732d215c2250d01706b948d4e1c638062d7","datavalue":{"value":"0954.05018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1976593$B50B4E6D-02A6-4A66-B4A0-444874599CD9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5d2fb95c47896aa2faad07d25754651421bf7536","datavalue":{"value":"10.1142/S0252959900000066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1976593$F22E4C0C-0653-4940-A244-335F12BB7E07","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3d97c3955a340bf2fabd1dc725af535482e933f3","datavalue":{"value":{"entity-type":"item","numeric-id":181511,"id":"Q181511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1976593$894D1475-709E-45E0-A3D6-037CC4BFF710","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2d1d54670924db26a74d9a3b5e6224e9f60db0e3","datavalue":{"value":{"time":"+2001-01-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1976593$50A0E7B3-9DBF-4AE9-903E-FA0E84D8592C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"070542393b8174b531585072863bf0165c2afefa","datavalue":{"value":"De Bruijn graphs have many good properties and serve as models for interconnection networks. In the note a new property of binary undirected de Bruijn graphs is given. De Bruijn digraphs are defined as iterated line digraphs obtained from a complete directed graph. Another definition of de Bruijn graphs is based on binary sequences of given length. In the case of undirected binary de Bruijn graphs vertices correspond to binary sequences of length \\(n\\) and two vertices are adjacent if the corresponding sequences differ only in the first or in the last element.    It is well known that the diameter of the \\(n\\)-dimensional undirected de Bruijn graph \\(\\text{UB}(n)\\) is equal to \\(n\\) and between any two vertices \\(x\\) and \\(y\\) there are at least two internally disjoint paths of length less than or equal to \\(n\\). It is proved that in \\(\\text{UB}(n)\\) exists at least one vertex \\(x\\) such that for any other vertex \\(y\\) there are at least two internally disjoint paths of length \\(n-1\\) from \\(x\\) to \\(y\\). In other words there is a vertex of eccentricity at most \\(n-1\\) and after deleting any vertex from \\( \\text{UB}(n)\\) its eccentricity still remains at most \\(n-1\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1976593$4AAD61BE-B25E-4D1F-8FE5-3AD044FEAF48","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1976593$E4EE154A-80AF-42E1-829A-1621F9030BA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1976593$8D0F7634-9786-4B64-A84B-15E3C9E4CAC1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"15c42ce943863648eb6e968c4f30f6f6474dafad","datavalue":{"value":"1445760","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1976593$CDE99D11-5AA6-4E4A-8A42-4D42AEF01397","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5486a903d11614b00d306449a6ba3df91c01be08","datavalue":{"value":"de Bruijn graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1976593$2022BFD1-3843-4D95-A5D6-3FC3C76772BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0790746f6410ed142073636c3fdda5375d90359","datavalue":{"value":"distance","type":"string"},"datatype":"string"},"type":"statement","id":"Q1976593$8595A37C-D0FB-480D-BC71-5E65F08EECFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8415b13e13866b2a902e773eb49890a053b3a53","datavalue":{"value":"disjoint paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q1976593$1B8FB2B4-743D-4E5E-924A-5C31B01A2E69","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8cec0dd1a451faaa34236951e23369805db837a4","datavalue":{"value":{"entity-type":"item","numeric-id":329722,"id":"Q329722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1976593$0F595223-16FD-4969-812E-9DAACECB1623","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7a16e1e58ef83ee139c1b19d99d1b0144d5d0f30","datavalue":{"value":{"entity-type":"item","numeric-id":511192,"id":"Q511192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1976593$5AA7B7A6-9297-4ABE-9669-9CB258CD097C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8417b756cfbd4cea93ea14ff194a3e849ce3f41d","datavalue":{"value":{"entity-type":"item","numeric-id":1011780,"id":"Q1011780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1976593$F608E9F7-7B04-4D2D-A25A-06C39A0134FF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"15fb7789dd0d1691819f44cebdb975938d5b89dc","datavalue":{"value":{"entity-type":"item","numeric-id":967347,"id":"Q967347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1976593$959C7ECA-C952-4C31-A07D-B9BE2A54079E","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":"Q1976593$03D72048-77E1-48F5-9109-5F7569BBE30B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60583bfcb2b4aa5040b2b7c4c6e006047ead49b8","datavalue":{"value":{"entity-type":"item","numeric-id":1582075,"id":"Q1582075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a783550dd74c1b8b8badfd5148599107d14391d","datavalue":{"value":{"amount":"+0.8924513","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":"Q1976593$882F2021-55F2-4BB2-9708-2B5B3E6A1873","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa0ba70079a996fa09d3009a60293ddbc73fbc2b","datavalue":{"value":{"entity-type":"item","numeric-id":1105619,"id":"Q1105619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1cae27300a541befb971d8cabce184fa7d13651","datavalue":{"value":{"amount":"+0.8839113","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":"Q1976593$55AF353D-75D0-4312-BFC8-E49674D50905","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d2865d57c1ad20930fe78e78be25a018ea5a4170","datavalue":{"value":{"entity-type":"item","numeric-id":2846654,"id":"Q2846654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8533e17af358b1168965571bbfad120a62aa767a","datavalue":{"value":{"amount":"+0.883855","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":"Q1976593$78A6CA7C-27FF-416B-9162-BC4992B1A1F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d1dd9c9ba20186c6615cc9177a18438022ebf30","datavalue":{"value":{"entity-type":"item","numeric-id":1199424,"id":"Q1199424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df509dffc39f48ea1fd56833fe7ec45fb7a2c96a","datavalue":{"value":{"amount":"+0.8832689","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":"Q1976593$93D875C0-12BF-4D4F-B6CA-0E81C732CF77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91fc585ef24bce3c95cc5520d76b9c58056b77e7","datavalue":{"value":{"entity-type":"item","numeric-id":1364476,"id":"Q1364476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f8d43a323e5dcb2524f9bae93d16fa2e02571ead","datavalue":{"value":{"amount":"+0.88322616","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":"Q1976593$0EF32A5E-ECAA-4A06-AB7F-B1AB05F8CAE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"50e7d0e2c9a747a8f4a51ad8083da752b8948cda","datavalue":{"value":{"entity-type":"item","numeric-id":3825284,"id":"Q3825284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1523228efd5d6292938f8cf58cff3bb185b9930b","datavalue":{"value":{"amount":"+0.88250625","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":"Q1976593$71C4A7EB-87F8-4E72-A1BA-94650363226B","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":"1b46abc4b6bd5b59851e35998ab1bb4dac9c0b6e","datavalue":{"value":{"amount":"+0.87867326","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":"Q1976593$F693D879-5D80-475F-A75D-31AF7DD6D721","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"50945910c4fee7c204e2465116c87e19e37a873d","datavalue":{"value":{"entity-type":"item","numeric-id":3624978,"id":"Q3624978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"231915d3bf03f63fa47fd208895d1a068f9deb7a","datavalue":{"value":{"amount":"+0.87599194","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":"Q1976593$AC171443-5326-4783-A832-799497D274E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b73f061cf7692ad1841865983ed18d795c86a5c","datavalue":{"value":{"entity-type":"item","numeric-id":4595251,"id":"Q4595251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3cd114cfef72414293d8b1697977dcda2572f583","datavalue":{"value":{"amount":"+0.87498957","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":"Q1976593$5C8E8842-E732-4AA7-95B7-FC51D32DBF82","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A new property of binary undirected de Bruijn graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_new_property_of_binary_undirected_de_Bruijn_graphs"}}}}}