Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Fixee wrote

Every independent set induces a clique in the complement graph (or a biclique in the case of bipartite graphs).

I wonder how an independent set induces a biclique in a bipartite graphs?

Thanks!

share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

This probably refers to its bipartite complement. If you have a bipartite graph with the vertex bipartition $U \cup V$, then the edges in its complement are $$\{uv: u \in U, v \in V \text{ and } uv \text{ not an edge in } G\}.$$

There's a similar ambiguity in the use of the term adjacency matrix for bipartite graphs; some people call the bi-adjacency matrix simply the adjacency matrix.

share|improve this answer
    
Thanks! So do a maximum independent set in a bipartite graph and a maximum biclique in its bipartite complement induce each other? –  Tim Nov 3 '12 at 23:28
add comment

An independent set is a pairwise non-adjacent set of vertices. Thus in the complement, every vertex will be incident to every other vertex, whence the set forms a clique. The only biclique which is also a clique is $K_2$. I think Fixee may have misspoken.

Perhaps what he means is to emphasize that the elements of the first partition are pairwise disconnected from the elements of the second partition (as well as from one another).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.