Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Skew Spectra of Oriented Graphs"

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: Skew Spectra of Oriented Graphs. | Skew Spectra of Oriented Graphs Bryan Shader Department of Mathematics University of Wyoming Laramie WY 82071-3036 USA email bshader@uwyo.edu Wasin So Department of Mathematics San Jose State University San Jose CA 95192-0103 USA email so@math.sjsu.edu Submitted Jul 20 2009 Accepted Nov 5 2009 Published Nov 13 2009 Mathematics Subject Classification 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 Sp G the adjacency spectrum of G. Skew-adjacency matrix S GƠ of Gơ is introduced and its spectrum Sps Gơ is called the skew-spectrum of Gơ. The relationship between Sps Gơ and Sp G is studied. In particular we prove that i Sps Gơ iSp G for some orientation Ơ if and only if G is bipartite ii Sps Gơ iSp G for any orientation Ơ if and only if G is a forest where i 1. 1 Introduction Let G be a simple graph. With respect to a labeling the adjacency matrix A G is the symmetric matrix aij where aij aji 1 if i j is an edge of G otherwise aij aji 0. The spectrum Sp G of G is defined as the spectrum of A G . Note that the definition is well defined because symmetric matrices with respect to different labelings are permutationally similar and so have same spectra. Also note that Sp G consists of only real eigenvalues because A G is real symmetric. Example 1.1. Consider the path graph P4 on 4 vertices. With respect to two different THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 N32 1 labelings A P4 takes the form 0 1 0 0 0 0 1 0 1 0 1 0 or 0 0 1 1 0 1 0 1 1 1 0 0 0 0 1 0 0 1 0 0 4 i i . And the spectrum Sp P4 is Example 1.2. Consider the star graph ST5 on 5 vertices. With respect to two different labelings A ST5 takes the form 0 1 1 1 1 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 or 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 And the spectrum Sp ST5 is -2 0 3 2 . Example 1.3. Consider the cycle graph C4 on 4 .