tailieunhanh - Báo cáo toán học: "The Rank of a Cograph"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: The Rank of a Cograph | The Rank of a Cograph Gordon F. Royle Department of Computer Science Software Engineering University of Western Australia Australia gordon@ Submitted Mar 1 2002 Accepted Aug 21 2003 Published Sep 17 2003 MR Subject Classifications 05C50 Abstract The rank of the adjacency matrix of a graph is bounded above by the number of distinct non-zero rows of that matrix. In general the rank is lower than this number because there may be some non-trivial linear combination of the rows equal to zero. We show the somewhat surprising result that this never occurs for the class of cographs. Therefore the rank of a cograph is equal to the number of distinct non-zero rows of its adjacency matrix. 1 Introduction and Motivation The rank of a graph X is the rank of its adjacency matrix A X . As the rank is such a fundamental algebraic concept the relationship between the structure of a graph and its rank is a natural topic of study for algebraic graph theorists. Perhaps the most well-known of such investigations is the study of the relationship between the rank and the chromatic number of a graph see Alon Seymour 1 . Despite this and other efforts there is surprisingly little that can be said about the rank of the adjacency matrix of a graph. In general the known results are limited to calculations of the rank in special cases or how the rank varies under certain operations for example see Bevis 2 . In fact considerably more is known about the rank of other matrices associated with a graph or about the ranks of certain graphs over finite fields for examples see Godsil Rohe 7 . In calculating the rank of a graph the maximum value that it can take is the number of distinct non-zero rows of the adjacency matrix. In general these will not be linearly independent and the rank will be somewhat lower. While experimenting on the rank-chromatic number question by computer Torsten Sillke 8 observed that for all the cographs he checked the rank turned out to be precisely .