✦ LIBER ✦

Biclique graphs and biclique matrices

✍ Scribed by Marina Groshaus; Jayme L. Szwarcfiter

Publisher: John Wiley and Sons
Year: 2010
Tongue: English
Weight: 203 KB
Volume: 63
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20442

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A biclique of a graph G is a maximal induced complete bipartite subgraph of G. Given a graph G, the biclique matrix of G is a {0,1,−1} matrix having one row for each biclique and one column for each vertex of G, and such that a pair of 1, −1 entries in a same row corresponds exactly to adjacent vertices in the corresponding biclique. We describe a characterization of biclique matrices, in similar terms as those employed in Gilmore's characterization of clique matrices. On the other hand, the biclique graph of a graph is the intersection graph of the bicliques of G. Using the concept of biclique matrices, we describe a Krausz‐type characterization of biclique graphs. Finally, we show that every induced P~3~ of a biclique graph must be included in a diamond or in a 3‐fan and we also characterize biclique graphs of bipartite graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 1–16, 2010

📜 SIMILAR VOLUMES

Bicliques and Eigenvalues

✍ Willem H. Haemers 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 147 KB

A biclique in a graph 1 is a complete bipartite subgraph of 1. We give bounds for the maximum number of edges in a biclique in terms of the eigenvalues of matrix representations of 1. These bounds show a strong similarity with Lova sz's bound (1) for the Shannon capacity of 1. Motivated by this simi

On cliques and bicliques

✍ Henning, Michael A. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 97 KB 👁 1 views

For integers m, n ≥ 2, let g(m, n) be the minimum order of a graph, where every vertex belongs to both a clique K m of order m and a biclique K(n, n). or, if m is sufficiently large and (m -1)(n -1) is not an integer.

Approximating Clique and Biclique Proble

Approximating Clique and Biclique Problems

✍ Dorit S. Hochbaum 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 317 KB

We present here 2-approximation algorithms for several node deletion and edge deletion biclique problems and for an edge deletion clique problem. The biclique problem is to find a node induced subgraph that is bipartite and complete. The objective is to minimize the total weight of nodes or edges de

Rank and biclique partitions of the comp

Rank and biclique partitions of the complement of paths

✍ Boyer, Elizabeth D. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 230 KB 👁 1 views

The problem was posed of determining the biclique partition number of the complement of a Hamiltonian path (Monson, Rees, and Pullman, Bull. Inst. Combinatorics and Appl. 14 (1995), 17-86). We define the complement of a path P , denoted P , as the complement of P in K m,n where P is a subgraph of K

Realization of Matrices and Directed Gra

Realization of Matrices and Directed Graphs

✍ Rajeev Motwani 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 182 KB

We consider the problem of constructing a matrix with prescribed row and Ä 4 column sums, subject to the condition that the off-diagonal entries are in 0, 1 and the diagonal entries are nonnegative integers. The pair of row and column sum vectors is called realizable if such a matrix exists. This is

Graphs with nilpotent adjacency matrices

✍ Martin W. Liebeck 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 149 KB

## Abstract Given any integer __t__ ≥ 2 and any prime number __p__, a graph Γ~__p,t__~ is constructed whose adjacency matrix is nilpotent of index __t__ over Z~__p__'~ the field of __p__ elements.