{"entities":{"Q1583541":{"pageid":1594281,"ns":120,"title":"Item:Q1583541","lastrevid":72251097,"modified":"2026-04-14T03:38:28Z","type":"item","id":"Q1583541","labels":{"en":{"language":"en","value":"Bounding the bandwidths for graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1521898"}},"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":"Q1583541$C860AAF5-A271-4B7F-8CF0-C3BBCF494209","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fa3c4dc0973bb2f735af275eac83c79635264fe2","datavalue":{"value":{"text":"Bounding the bandwidths for graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1583541$E733E60D-8387-41EE-82E2-7685205545E3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"50157d586d13cc1f3f2027fd752440572fa13572","datavalue":{"value":"0949.68120","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1583541$B70A747F-F625-4891-865D-23F137945E0D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"24b86648a7dc94ec24bdc84e24b9a81fb7bfef0a","datavalue":{"value":"10.1016/S0304-3975(00)00068-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1583541$15ABE1BE-C83C-4553-AFEB-4E1033985793","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1583541$F2BC6F5C-2EF7-42AC-8AEA-FFF7EF2A46A3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7ccf67db9ec606552e3b39a88e0b26e8e698006b","datavalue":{"value":{"time":"+2000-10-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1583541$BCD946D3-7376-4649-8AB2-BB8832B425C6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"097d51fe928fc3e9b637718aca01a89e8ab870c4","datavalue":{"value":"Let \\(G,H\\) be finite graphs with \\(|V(H)|\\geqslant|V(G)|\\). The bandwidth of \\(G\\) with respect to \\(H\\) is defined to be \\(B_H(G)=\\min_{\\pi} \\max_{uv\\in E(G)} d_H(\\pi(u),\\pi(v))\\), with the minimum taken over all injections \\(\\pi\\) from \\(V(G)\\) to \\(V(H),\\) where \\(d_{H}(x,y)\\) is the distance in \\(H\\) between two vertices \\(x,y \\in V(H)\\). This number is involved with the VLSI design and optimization, especially when the ``host'' graph \\(H\\) is a path \\(P_{n}\\) or a cycle \\(C_{n}\\) of length \\(n=|V(G)|\\). In these two cases, \\(B_{H}(G)\\) is known to be the ordinary bandwidth \\(B(G)\\) and the cyclic bandwidth \\(B_{c}(G),\\) respectively, and the corresponding decision problem is NP-complete. So estimations of \\(B(G),\\) \\(B_{c}(G)\\) and in general \\(B_{H}(G)\\) are needed, especially in determining the bandwidths of some specific graphs. We first propose a systematic method for obtaining lower bounds for the bandwidth \\(B_{H}(G).\\) By using this method, we then get a number of lower bounds for \\(B(G)\\) and \\(B_{c}(G)\\) in terms of some distance- and degree-related parameters.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1583541$98D9068C-9CED-4D7D-96A9-53154C8F62C8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1583541$421A9295-6A8A-46BA-9D36-12558D398592","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a2f349c0579246381875d183e4058a3c552af26f","datavalue":{"value":"1521898","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1583541$0A246B36-C390-4249-BF08-FF24A8A7AA8D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"72494967642b9ea1b87091d53eb77ad552577f43","datavalue":{"value":"bandwidth","type":"string"},"datatype":"string"},"type":"statement","id":"Q1583541$E808C508-5A0C-427D-85F0-ED5E7E7718B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac892312b4483bba614318aa69e51ae4e3be669b","datavalue":{"value":"cyclic bandwidth","type":"string"},"datatype":"string"},"type":"statement","id":"Q1583541$3B6B41F9-598A-41E4-905D-3D049CAFFB28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"22bf57f5dd7fd116d34a1a789bd1bf0b6d51d6a1","datavalue":{"value":"VLSI layout","type":"string"},"datatype":"string"},"type":"statement","id":"Q1583541$E45DE097-38D2-492C-B8A2-53061F84A6FB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a1da51825dbac02dbae2b1fae272f812e9417016","datavalue":{"value":{"entity-type":"item","numeric-id":201997,"id":"Q201997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1583541$9874E992-1871-4D07-9C42-7E689BD963D0","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":"Q1583541$82216F3C-FE7E-4F98-B821-37C038439E9A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d823bde0afa959f545aa85998f405220b941317","datavalue":{"value":{"entity-type":"item","numeric-id":796306,"id":"Q796306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1583541$314BBFF7-81CD-4C94-BD33-7927567F1DB7","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":"Q1583541$26A01BD8-3821-4B6C-86BA-8DBDE894CF23","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":"Q1583541$6002EE71-E9E1-4AC9-8BD8-8E60C87A2350","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":"Q1583541$157CE91F-3F98-4C54-B409-A6ACCFC181AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"751bb518407806a0775e238de3cb997abdfa1f23","datavalue":{"value":{"entity-type":"item","numeric-id":1324287,"id":"Q1324287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1583541$C5817D99-733A-42CE-A40A-FC1B82359394","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":"Q1583541$757BBD64-C4C6-45A9-93DB-1B0A516C97E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e06b373fcee790160bd241fadec2cf8e08086b4d","datavalue":{"value":{"entity-type":"item","numeric-id":4294611,"id":"Q4294611"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1583541$83D5125C-8338-4308-9C63-B65CC8ECBB6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0c371e8c34ace627f21fbc6d0f9ba592fdb7c0c","datavalue":{"value":{"entity-type":"item","numeric-id":4321827,"id":"Q4321827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1583541$79A2CE5A-A3CE-402D-A64A-BE3158FC6B3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5297fcddca28f8cbe49413fd68dca4d511a0b5c","datavalue":{"value":{"entity-type":"item","numeric-id":4871643,"id":"Q4871643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1583541$07466AE8-982B-4EAF-A60A-104173CF22ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"990074c91420b1d00395c0f26edb59f35f333da7","datavalue":{"value":{"entity-type":"item","numeric-id":4347280,"id":"Q4347280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1583541$7F5763E1-22EB-41BD-96C7-207A51F59C5C","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":"Q1583541$BAED2928-8190-4168-BC93-C993D983D6B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c15572c6f4f8c9bfd2f81c12f3068036ff44d05","datavalue":{"value":{"entity-type":"item","numeric-id":1381861,"id":"Q1381861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1583541$02AD6CA2-A734-493D-976C-E3789EB8152E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b577f2e8c8dc50ff284f9f4c80919f0a8e84fda","datavalue":{"value":{"entity-type":"item","numeric-id":1584241,"id":"Q1584241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1583541$7F64F798-F333-4C98-B90B-1A05D60C42F8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e12cb204f9ce0a276eb936b99427aabcb0defd2","datavalue":{"value":{"entity-type":"item","numeric-id":4347280,"id":"Q4347280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d11e9842ea7263e5c694dfcb4e962f3e24d35e74","datavalue":{"value":{"amount":"+0.8216823935508728","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":"Q1583541$BD9ED6AA-AFA0-4CD6-9895-F69843684EDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24230ed0f214fc5859577eb703006baaa0066f8c","datavalue":{"value":{"entity-type":"item","numeric-id":1584358,"id":"Q1584358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28c398729eb38d7975719f1ad0afd7d8c213223c","datavalue":{"value":{"amount":"+0.821103572845459","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":"Q1583541$F5449663-E525-45BC-BCCD-C9BFCC20667E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1004af0593485dfde1b5761ca1fbc3660af59119","datavalue":{"value":{"entity-type":"item","numeric-id":4940077,"id":"Q4940077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24b1d0510dad2e521aeacdb739a283bb3bc82d2e","datavalue":{"value":{"amount":"+0.8194308876991272","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":"Q1583541$1160123C-E4F4-4129-A0B8-C77656B8D99D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ea5bd94ac9e0c3d74ead229652363e3f686036d","datavalue":{"value":{"entity-type":"item","numeric-id":4853762,"id":"Q4853762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e38389b8b48800d5c3179c0a13dca0441f636848","datavalue":{"value":{"amount":"+0.8050234913825989","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":"Q1583541$794E1D9F-BB27-4B28-B9C6-2E82771CE7F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a4e3adb1ce9c0a53340c68c03f4dfa541cbbd7a2","datavalue":{"value":{"entity-type":"item","numeric-id":4733889,"id":"Q4733889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84574bf4fb8eef2d2e44464027c21bff7729d339","datavalue":{"value":{"amount":"+0.8008996248245239","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":"Q1583541$3B2C9A55-1BEC-4E1F-9191-AAFBEDD47C78","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Bounding the bandwidths for graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Bounding_the_bandwidths_for_graphs"}}}}}