tailieunhanh - Báo cáo toán học: "On Certain Eigenspaces of Cographs"

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: On Certain Eigenspaces of Cographs. | On Certain Eigenspaces of Cographs Torsten Sander Institut far Mathematik Technische Universitat Clausthal D-38678 Clausthal-Zellerfeld Germany Submitted Apr 12 2008 Accepted Oct 27 2008 Published Nov 14 2008 Mathematics Subject Classification Primary 05C50 Secondary 15A18 Abstract For every cograph there exist bases of the eigenspaces for the eigenvalues 0 and 1 that consist only of vectors with entries from 0 1 1 a property also exhibited by other graph classes. Moreover the multiplicities of the eigenvalues 0 and 1 of a cograph can be determined by counting certain vertices of the associated cotree. Keywords cograph eigenspace nullity null space 1 Introduction The class of cographs has can be used to model series-parallel decompositions and hence has numerous applications in areas like parallel computing 9 or even biology 6 . Consequently many research results on cographs have been obtained in recent years see 2 for an overview . The contribution of the present paper is to study the eigenspaces of cographs for eigenvalues 0 and 1 namely to derive the multiplicities of these eigenvalues and to construct particularly simple eigenspace bases. The particular eigenvalues 0 and 1 play a role in several areas of algebraic graph theory. For example in the theory of star partitions the eigenvalues 0 and 1 are special cases cf. 4 chapter 7 . Another interesting result is that singular line graphs of trees can be partitioned into two classes depending on whether a certain graph has either 0 or 1 as a multiple eigenvalue 13 . For easier eigenspace analysis it is often desirable to find a basis for a considered graph eigenspace that is considered structurally simple . For example we may require the basis vectors to have entries only from a very restricted set of values. Most notably we are interested in the set 1 0 1g in which case we call the basis simply structured. Several authors have contributed to this topic in recent years cf. 1 8 .