tailieunhanh - Báo cáo toán học: "Characteristic polynomials of skew-adjacency matrices of oriented graphs"

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í Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Characteristic polynomials of skew-adjacency matrices of oriented graphs. | Characteristic polynomials of skew-adjacency matrices of oriented graphs Yaoping Hou Tiangang Lei Department of Mathematics Department of Mathematical and Physical Sciences Hunan Normal University National Nature Science Foundation of China Changsha Hunan 410081 China Beijing 100875 China yphou@ leitg@ Submitted Jan 18 2011 Accepted Jul 4 2011 Published Aug 5 2011 Mathematics Subject Classification 05C20 05C50 Abstract An oriented graph Gơ is a simple undirected graph G with an orientation which assigns to each edge a direction so that Gơ becomes a directed graph. G is called the underlying graph of Gơ and we denote by S Gơ the skew-adjacency matrix of Gơ and its spectrum Sp Gơ is called the skew-spectrum of Gơ. In this paper the coefficients of the characteristic polynomial of the skew-adjacency matrix S Gơ are given in terms of Gơ and as its applications new combinatorial proofs of known results are obtained and new families of oriented bipartite graphs Gơ with Sp Gơ iSp G are given. 1 Introduction All undirected graphs in this paper are simple and finite. Let G be a graph with n vertices and A G a j the adjacency matrix of G where aitj aji 1 if there is an edge ij between vertices i and j in G denoted by i j otherwise ai j aj i 0. We call G nonsingular if the matrix A G is nonsingular. The characteristic polynomial P G x det xI A G of A G where I stands for the identity matrix of order n is said to be the characteristic polynomial of the graph G. The n roots of the polynomial P G x are said to be the eigenvalues of the graph G. Since A G is symmetric all eigenvalues of A G are real and we denote by Sp G the adjacency spectrum of G. Let Gơ or G be a graph with an orientation which assigns to each edge of G a direction so that Gơ becomes a directed graph. The skew-adjacency matrix S Gơ sij is real skew symmetric matrix where si j 1 and Sji 1 if i j is an arc of Gơ otherwise si j Sj i 0. The skew-spectrum Sp Gơ of Gơ is defined as the .