Vertex removal in biclique graphs

Abstract: A extit{biclique} is a maximal induced complete bipartite subgraph. The extit{biclique graph} of a graph

H

, denoted by

K B (H)

, is the intersection graph of the family of all bicliques of

H

. In this work we address the following question: Given a biclique graph

G = K B (H)

, is it possible to remove a vertex

q

of

G

, such that

G - q

is a biclique graph? And if possible, can we obtain a graph

H^{'}

such that

G - q = K B (H^{'})

? We show that the general question has a "no" for answer. However, we prove that if

G

has a vertex

q

such that

d (q) = 2

, then

G - q

is a biclique graph and we show how to obtain

H^{'}

.

Recommendations

Cites Work

Cited In (7)

Uses Software

This page was built for publication: Vertex removal in biclique graphs