Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Fractional biclique covers and partitions of graphs"
Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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@mala.bc.ca 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 .