Odd covers of graphs

Abstract: Given a finite simple graph

G

, an odd cover of

G

is a collection of complete bipartite graphs, or bicliques, in which each edge of

G

appears in an odd number of bicliques and each non-edge of

G

appears in an even number of bicliques. We denote the minimum cardinality of an odd cover of

G

by

b_{2} (G)

and prove that

b_{2} (G)

is bounded below by half of the rank over

m a t h b b F_{2}

of the adjacency matrix of

G

. We show that this lower bound is tight in the case when

G

is a bipartite graph and almost tight when

G

is an odd cycle. However, we also present an infinite family of graphs which shows that this lower bound can be arbitrarily far away from

b_{2} (G)

. Babai and Frankl (1992) proposed the "odd cover problem," which in our language is equivalent to determining

b_{2} (K_{n})

. Radhakrishnan, Sen, and Vishwanathan (2000) determined

b_{2} (K_{n})

for an infinite but density zero subset of positive integers

n

. In this paper, we determine

b_{2} (K_{n})

for a density

3 / 8

subset of the positive integers.

Recommendations

Cites Work

Cited In (2)

This page was built for publication: Odd covers of graphs