tailieunhanh - Báo cáo toán học: "Fractional biclique covers and partitions of graphs"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Fractional biclique covers and partitions of graphs. | Fractional biclique covers and partitions of graphs Valerie L. Watts Department of Mathematics Malaspina University-College 900 Fifth Street Nanaimo British Columbia Canada V9R 5S5 wattsv@ Submitted Jun 20 2005 Accepted Aug 8 2006 Published Aug 22 2006 Mathematics Subject Classifications 05C99 90C35 Abstract A biclique is a complete bipartite subgraph of a graph. This paper investigates the fractional biclique cover number bc G and the fractional biclique partition number bp G of a graph G. It is observed that bc G and bp G provide lower bounds on the biclique cover and partition numbers respectively and conditions for equality are given. It is also shown that bc G is a better lower bound on the Boolean rank of a binary matrix than the maximum number of isolated ones of the matrix. In addition it is noted that bc G bp G 3 G the fractional vertex cover number. Finally the application of bc G and bp G to two different weak products is discussed. Keywords fractional biclique covers fractional biclique partitions Boolean rank weak products 1 Introduction Fractional graph theory is the modihcation of integer-valued graph parameters to allow them to take on non-integer values. This article investigates the fractional analogues of the minimum number of complete bipartite subgraphs bicliques needed to cover or partition the edges of a graph. For more on fractional graph theory and other fractional graph parameters see Berge 1 or Scheinerman and Ullman 17 . To begin some dehnitions are given which are used throughout. A simple graph is denoted by G with vertex set V G 1 2 n and edge set E G . An edge of G is an unordered pair of vertices u v usually written uv. For general graph theory terminology used throughout see 2 . A subgraph of G whose edge set forms a complete bipartite graph is called a biclique of G. Let K R S denote the biclique of G with edge set ij i 2 R j 2 S where R and S are disjoint non-empty subsets of vertices of G. THE ELECTRONIC JOURNAL OF .