Biclique covers and partitions (Q405095): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Changed an Item
ReferenceBot (talk | contribs)
Changed an Item
 
(3 intermediate revisions by 3 users not shown)
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / arXiv ID
 
Property / arXiv ID: 1307.6363 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5688995 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the coverings of graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3312268 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the decomposition of graphs into complete bipartite graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Graph Theory and Probability / rank
 
Normal rank
Property / cites work
 
Property / cites work: Covering a graph by complete bipartite graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Bipartite dimensions and bipartite degrees of graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the Addressing Problem for Loop Switching / rank
 
Normal rank
Property / cites work
 
Property / cites work: Turán and Ramsey Properties of Subcube Intersection Graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: On set intersection representations of graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: On covering graphs by complete bipartite subgraphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5525916 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Communication Complexity / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3236503 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Topics in Intersection Graph Theory / rank
 
Normal rank
Property / cites work
 
Property / cites work: Bipartite coverings and the chromatic number / rank
 
Normal rank
Property / cites work
 
Property / cites work: A mathematical analysis of human leukocyte antigen serology / rank
 
Normal rank
Property / cites work
 
Property / cites work: Bipartite Coverings of Graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the decomposition ofkn into complete bipartite graphs / rank
 
Normal rank
links / mardi / namelinks / mardi / name
 

Latest revision as of 23:47, 8 July 2024

scientific article
Language Label Description Also known as
English
Biclique covers and partitions
scientific article

    Statements

    Biclique covers and partitions (English)
    0 references
    0 references
    4 September 2014
    0 references
    Summary: The biclique cover number (resp. biclique partition number) of a graph \(G\), \(\text{bc}(G\)) (resp. \(\text{bp}(G)\)), is the least number of bicliques -- complete bipartite subgraphs -- that are needed to cover (resp. partition) the edges of \(G\). { }The local biclique cover number (resp. local biclique partition number) of a graph \(G\), \(\text{lbc}(G\)) (resp. \(\text{lbp}(G)\)), is the least \(r\) such that there is a cover (resp. partition) of the edges of \(G\) by bicliques with no vertex in more than \(r\) of these bicliques.{ }We show that \(\text{bp}(G)\) may be bounded in terms of \(\text{bc}(G)\), in particular, \(\text{bp}(G)\leq \frac{1}{2}(3^{\text{bc(G)}}-1)\). However, the analogous result does not hold for the local measures. Indeed, in our main result, we show that \(\text{lbp}(G)\) can be arbitrarily large, even for graphs with \(\text{lbc}(G)=2\). For such graphs, \(G\), we try to bound \(\text{lbp}(G)\) in terms of additional information about biclique covers of \(G\). We both answer and leave open questions related to this.{ }There is a well known link between biclique covers and subcube intersection graphs. We consider the problem of finding the least \(r(n)\) for which every graph on \(n\) vertices can be represented as a subcube intersection graph in which every subcube has dimension \(r\). We reduce this problem to the much studied question of finding the least \(d(n)\) such that every graph on \(n\) vertices is the intersection graph of subcubes of a \(d\)-dimensional cube.
    0 references
    biclique covers
    0 references
    biclique partitions
    0 references
    local biclique cover number
    0 references
    subcube intersection graphs
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references