{"entities":{"Q668017":{"pageid":669866,"ns":120,"title":"Item:Q668017","lastrevid":63519570,"modified":"2026-04-11T13:43:12Z","type":"item","id":"Q668017","labels":{"en":{"language":"en","value":"Bandwidth of graphs resulting from the edge clique covering problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7032055"}},"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":"Q668017$DEC59F89-77D7-4AFF-846A-1FB46275B5AD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b6ac4c815923ea7e834b01a6c6630dc133e78008","datavalue":{"value":{"text":"Bandwidth of graphs resulting from the edge clique covering problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q668017$8504D28B-3952-4DB7-8027-E97CDF5E598D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"73f904576a8340bc12bbe9394b54e9a5bd080276","datavalue":{"value":"1409.05174","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668017$C0B97807-CBF3-4E00-9A8E-3290B7A3CBC1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"98c5835a632f59c04c7195e8516df80cfca74bbb","datavalue":{"value":{"entity-type":"item","numeric-id":427811,"id":"Q427811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668017$A933DC45-3247-4E9A-9A53-D87EE6BC9D6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"62756494365242df4b123dedee8673cb343848e7","datavalue":{"value":{"entity-type":"item","numeric-id":668016,"id":"Q668016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668017$B622CA6A-1FCD-43E2-AEC7-CA69845DA252","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":"Q668017$E70F50F3-0D26-40BE-9488-B740E9EDBD5B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c236a5296bce37f0e3594963375752714d7f6e86","datavalue":{"value":{"time":"+2019-03-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q668017$68973FCA-0779-4F94-9F0A-C6DDF82464BF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ba8490c52d8259b04c0d8f80729755de7762fdef","datavalue":{"value":"https://arxiv.org/abs/1605.00450","type":"string"},"datatype":"url"},"type":"statement","id":"Q668017$0C7F530D-A221-4247-81F5-4D1F6A21AFA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"f8b408e5bdf6eef28ec741c729b5623918726167","datavalue":{"value":"https://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i4p49","type":"string"},"datatype":"url"},"type":"statement","id":"Q668017$D70532DE-DEC2-4499-BCF2-95A8D8A48E8B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f10e482f5f916e4c29c4cb9b9ee7233c23c60745","datavalue":{"value":"Summary: Let \\(n,k,b\\) be integers with \\(1 \\leq k-1 \\leq b \\leq n\\) and let \\(G_{n,k,b}\\) be the graph whose vertices are the \\(k\\)-element subsets \\(X\\) of \\(\\{0,\\dots,n\\}\\) with \\(\\max(X)-\\min(X) \\leq b\\) and where two such vertices \\(X,Y\\) are joined by an edge if \\(\\max(X \\cup Y)-\\min(X \\cup Y) \\leq b\\). These graphs are generated by applying a transformation to maximal \\(k\\)-uniform hypergraphs of bandwidth \\(b\\) that is used to reduce the (weak) edge clique covering problem to a vertex clique covering problem. The bandwidth of \\(G_{n,k,b}\\) is thus the largest possible bandwidth of any transformed \\(k\\)-uniform hypergraph of bandwidth \\(b\\). For \\(b\\geq \\frac{n+k-1}{2}\\), the exact bandwidth of these graphs is determined. Moreover, the bandwidth is determined asymptotically for \\(b=o(n)\\) and for \\(b\\) growing linearly in \\(n\\) with a factor \\(\\beta \\in (0,1]\\), where for one case only bounds could be found. It is conjectured that the upper bound of this open case is the right asymptotic value.","type":"string"},"datatype":"string"},"type":"statement","id":"Q668017$22DDEF84-4E4A-4F59-BC3D-510AE0910F53","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668017$2A881648-3056-46E9-BB4C-1FBAB19E67F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668017$DC53409D-D8DA-4C0B-BE1E-3DE1CBD3A9CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668017$A83E0161-1AD4-4AA0-ADE5-BEAFF8C21457","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b7344a2c77a7acab1e292fa27808f6f561c37930","datavalue":{"value":"7032055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668017$A0CCE6E7-BC3D-468B-B03C-60B844AE4D28","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ecdcf283db528fab4ab443c25d73516090c33800","datavalue":{"value":"bandwidth of graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q668017$D7810B02-1E30-4BBC-B538-2C088CFD1A7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9e1ca519f7f9c66308258a5a143f9e7977e4e3d3","datavalue":{"value":"bandwidth numbering","type":"string"},"datatype":"string"},"type":"statement","id":"Q668017$5CF9D1BD-F877-48BE-9242-08EAA54140AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d38cbd3a77971d12cc9398a48e23239f77606b7","datavalue":{"value":"edge clique coverings","type":"string"},"datatype":"string"},"type":"statement","id":"Q668017$CE3C87B9-E64E-42BC-AADE-C1E74C550548","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a01e27e2ee0b2f9407c5320e7f8b30ebef90d87","datavalue":{"value":"vertex clique coverings","type":"string"},"datatype":"string"},"type":"statement","id":"Q668017$BF47247C-494E-45CA-917A-9370BB630369","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3ba21c081fd5cf251799fe2af80cfc232041b136","datavalue":{"value":"\\(k\\)-element subsets","type":"string"},"datatype":"string"},"type":"statement","id":"Q668017$D8BA24C7-105F-4D8D-8A36-A58C780C6504","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":"Q668017$83DB3C9A-2D27-4707-A37D-CA126012B6EE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"52247b48c952ad5cc384f4eca187c1ee41c6fc76","datavalue":{"value":{"entity-type":"item","numeric-id":3629454,"id":"Q3629454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668017$84030DD3-8678-44D3-88E9-8A13AFD40358","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b5b869d5a36ca324443a77608351e5205b1ccfb9","datavalue":{"value":{"entity-type":"item","numeric-id":955026,"id":"Q955026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668017$B4A71B4B-09E5-4B3B-BF4B-103486951ACA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c78c1e7733d602f243656d057e1ed82f32a65d0c","datavalue":{"value":{"entity-type":"item","numeric-id":4677587,"id":"Q4677587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668017$A50AE24F-AE91-44D4-8766-3D1AC8FF2DA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"578e381acbffc8a34628feb054e6ba5627e27c4a","datavalue":{"value":{"entity-type":"item","numeric-id":5233722,"id":"Q5233722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668017$64547CB4-1976-45B8-8D85-2E67132F7952","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"468123f607fe9c0a7affbe6709664ebec53c9057","datavalue":{"value":{"entity-type":"item","numeric-id":3956994,"id":"Q3956994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668017$79111CAB-980E-4B05-BD5D-E6982BD897AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8922b884252f5daff66373222fbaf1cb25a2899","datavalue":{"value":{"entity-type":"item","numeric-id":5596082,"id":"Q5596082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668017$74FE738B-B06A-4C1A-B3D1-947C8C8011C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a03df6159403f8e2819b21b8def7de9a2c76af59","datavalue":{"value":{"entity-type":"item","numeric-id":1214948,"id":"Q1214948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668017$6488AB84-EEDB-4A3C-8B6B-59D65D3741C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"41bdde81084cd9700a59661ba6faf6d727531300","datavalue":{"value":{"entity-type":"item","numeric-id":3803160,"id":"Q3803160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668017$7B7FA26C-621F-456B-8FCC-387C745C45A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73c8099440593cdeb084a942486d782e9734803d","datavalue":{"value":{"entity-type":"item","numeric-id":619902,"id":"Q619902"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668017$8640D7D1-E448-4901-999A-B1557F96E813","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d338bbf31af90a1a999cf28ead3f10a83139ede","datavalue":{"value":{"entity-type":"item","numeric-id":1732614,"id":"Q1732614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668017$D10CEC6B-3D21-4A43-880B-D680AFFDED8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"669ed7ed9b31905b00a8b1e2e2e82fdca18b5b86","datavalue":{"value":{"entity-type":"item","numeric-id":4095771,"id":"Q4095771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668017$67094A12-EABB-469A-A4C2-C5C3F3080FC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9dc2ae67caa4232288e8640bda8a06225eddac86","datavalue":{"value":{"entity-type":"item","numeric-id":5541108,"id":"Q5541108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668017$9BB00F5F-DAAF-4432-822A-D00EF9AD5250","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5174ef1552dc71573cbf33fdee850446520d2d75","datavalue":{"value":{"entity-type":"item","numeric-id":1302164,"id":"Q1302164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668017$5212E0D2-2EEA-4E04-B0FB-83577A5E3F5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e1120693b8c9b8b7acbfbe93248755aed422e6d","datavalue":{"value":{"entity-type":"item","numeric-id":1400004,"id":"Q1400004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668017$505DEAC6-A382-429F-8B4C-17A490231EE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61ced77d0ab7c94e713742bc03608d394a8baa2d","datavalue":{"value":{"entity-type":"item","numeric-id":4018353,"id":"Q4018353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668017$933B86DB-8A93-4881-95D8-99E2919C4C35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44a562aa95e0a07278bdca02b49c4fe5b73f565d","datavalue":{"value":{"entity-type":"item","numeric-id":4144194,"id":"Q4144194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668017$85FA9EA6-96D5-4EFD-8160-D2FD6BB8BD94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24f4aba8e0ee3a2966b3de817d74f8875ab291ae","datavalue":{"value":{"entity-type":"item","numeric-id":1223124,"id":"Q1223124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668017$5B7EB260-7919-4631-BD5F-CF8537ED3635","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e83e4eb2959b9925e3ff367dabc202da2b57d82c","datavalue":{"value":{"entity-type":"item","numeric-id":3321331,"id":"Q3321331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668017$AE133A2E-CC1D-4E54-A4B0-5F2BEC896159","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"14c3287dcfa329f894e30584a4e63c41843861dc","datavalue":{"value":"bafkreih6wjyaze2p4ep2mougn5orl4edd3tgjotkrsql4bed5k3sgbrcki","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668017$3E413FD0-6582-4DD0-8488-701BEE5FF004","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ebdd9447b64a47522f19b1437bdc029127766c7b","datavalue":{"value":{"entity-type":"item","numeric-id":3015662,"id":"Q3015662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fa09eb7bfb0ab2b7b37949c970026884ff9495a3","datavalue":{"value":{"amount":"+0.7496381998062134","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":"Q668017$65EBA335-179A-4624-8FE1-FCA0ED7515FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9ea01edff7842e0a38247ae9f011ba050edfeef2","datavalue":{"value":{"entity-type":"item","numeric-id":4699159,"id":"Q4699159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91e58b5f0a426665be8712947bcb9f3540ef70c8","datavalue":{"value":{"amount":"+0.7435997128486633","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":"Q668017$BA813EFC-6D60-4534-9FC6-639F36072B72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf8dc24ad1a621be6824d7c3d4fb996dc24f4cb0","datavalue":{"value":{"entity-type":"item","numeric-id":1885045,"id":"Q1885045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a37c1fef6dfab784f56868484162c1b548e52d08","datavalue":{"value":{"amount":"+0.7433513402938843","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":"Q668017$43EF7BCD-0002-45D6-8548-138F91EFF077","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3895431d0495d6ad3b411d0a9e82f8ccc967e646","datavalue":{"value":{"entity-type":"item","numeric-id":2503283,"id":"Q2503283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e60623bf456ddd2792180d7f0da968282ab9f537","datavalue":{"value":{"amount":"+0.7425979375839233","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":"Q668017$4B866A8A-B830-4960-970F-1A78418F855A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f069906c6e5a574a961f9a872819abfb343df571","datavalue":{"value":{"entity-type":"item","numeric-id":5150561,"id":"Q5150561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c88ed9788d3037f4457ed01f451f064565b86d85","datavalue":{"value":{"amount":"+0.7233929634094238","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":"Q668017$C57ED3CE-10E3-4FD0-BE3A-3455CD92D20A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Bandwidth of graphs resulting from the edge clique covering problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Bandwidth_of_graphs_resulting_from_the_edge_clique_covering_problem"}}}}}