{"@context":["https://w3id.org/fdo/context/v1",{"schema":"https://schema.org/","prov":"http://www.w3.org/ns/prov#","fdo":"https://w3id.org/fdo/vocabulary/"}],"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q668017","@type":"DigitalObject","kernel":{"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q668017","digitalObjectType":"https://schema.org/ScholarlyArticle","primaryIdentifier":"mardi:Q668017","kernelVersion":"v1","immutable":true,"modified":"2026-03-26T16:49:36Z"},"profile":{"@context":"https://schema.org","@type":"ScholarlyArticle","@id":"https://portal.mardi4nfdi.de/entity/Q668017","name":"Bandwidth of graphs resulting from the edge clique covering problem","headline":"Bandwidth of graphs resulting from the edge clique covering problem","description":"scientific article; zbMATH DE number 7032055","url":"https://portal.mardi4nfdi.de/entity/Q668017","datePublished":"2019-03-05","author":[{"@id":"https://portal.mardi4nfdi.de/entity/Q427811"},{"@id":"https://portal.mardi4nfdi.de/entity/Q668016"}],"publisher":[{"@id":"https://portal.mardi4nfdi.de/entity/Q161296"}],"comment":"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.","citation":[{"@id":"https://portal.mardi4nfdi.de/entity/Q3629454"},{"@id":"https://portal.mardi4nfdi.de/entity/Q955026"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4677587"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5233722"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3956994"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5596082"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1214948"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3803160"},{"@id":"https://portal.mardi4nfdi.de/entity/Q619902"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1732614"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4095771"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5541108"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1302164"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1400004"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4018353"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4144194"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1223124"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3321331"}]},"provenance":{"prov:generatedAtTime":"2026-03-26T16:49:36Z","prov:wasAttributedTo":"MaRDI Knowledge Graph"}}