skip to main content


Search for: All records

Creators/Authors contains: "Yin, Mei"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. Abstract

    Given a finite simple graph , anodd cover ofis a collection of complete bipartite graphs, or bicliques, in which each edge of appears in an odd number of bicliques, and each nonedge of appears in an even number of bicliques. We denote the minimum cardinality of an odd cover of by and prove that is bounded below by half of the rank over of the adjacency matrix of . We show that this lower bound is tight in the case when is a bipartite graph and almost tight when 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 . Babai and Frankl proposed the “odd cover problem,” which in our language is equivalent to determining . In this paper, we determine that is when and is when is equivalent to 1 or modulo 8.

     
    more » « less