Đ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 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@csse.uwa.edu.au 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 et.al 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 .