冠图的谱及非奇异图的R（SR）—性质
|
摘要
图谱理论是代数图论的一个重要课题,是图论与代数的一个交叉研究领域.该领域主要研究图的谱特征和谱的图特征及相关应用问题.在文献[2]和[3]中已有了一些有关冠图的谱和图的R(SR)-性质的结论.对连通图G1和任一正则图G2,G1(?)G2的邻接谱已完全被确定.在G2是任意图的情况下,G1(?) 2的L-谱也被完全刻画,但很难确定邻接谱和Q-谱.本文继[2]和[3]的研究工作后,主要研究了冠图G1 (?) Km1,m2的邻接谱和Q-谱,并继续研究了非奇异图的R(SR/NR)-性质,主要内容如下：
在第一章引言中,我们回顾了图谱理论的研究历史及现状,给出了图谱的基本定义,符号及记号.我们也给出了冠图和图的R(SR)-性质的相关概念,列举了前人的一些关于冠图的谱,非奇异图的R(SR)-性质的研究成果.我们了解到某些冠图具有R(SR)-性质,但具有R(SR)-性质的图却不一定都是冠图.
第二章分为两节,第一节我们通过分类讨论的方法完全刻画了冠图G1 (?) Km1,m2的邻接谱,第二节我们又类似的刻画了冠图G1 (?) Km1,m2的Q-谱,其中G1是任意的图,Km1,m2是完全二部图,m1 第三章也分为两节,第一节我们根据已有研究成果列举了具有R(SR/NR)-性质的特殊图类,第二节我们利用有关符号逆图和平衡符号图的相关结论,刻画具有R(NR)-性质的一般图类,研究满足什么条件的图具有R(NR)-性质.
The theory of graphs spectra is an important research project, it is a crossing area between graph theory and algebra. This field mostly research the spectral character of graphs, the graphic character of graph spectrum and the corresponding questions. In literature [2] and [3], there has been some results about the spectrum of corona graphs and property R(SR) of nonsingular graphs. For the connected graph G1 and a regular graph G2, the adjacency spec-trum of G1(?)G2 has been determined. In the case of G2 being any graph, the L-spectrum of G1(?)G2 has been completely characterized, but it is quite difficult to determine the adjacency spectrum and Q-spectrum of G1(?)G2. This paper is focus on the adjacency spectrum and Q-spectrum of corona graphs G1(?)Km1,m2, we also further research property R(SR/NR) of nonsingular graphs. The main results are as follows:
In the first chapter, introduction, we review the research history and present situation. Then we give the basic definitions, symbols and notations about graph spectrum. We also give the corresponding concepts about corona graphs and property R(SR) of nonsingular graphs. We know that some corona graphs have property R(SR), but the graphs which have property R(SR) are not always corona graphs.
The second chapter consists of two sections. In the first section, we completely charac-terize the adjacency spectrum of the corona graph G1(?)Km1,m2 by the method of classified discussion. In the second section, we characterize the Q-spectrum of G1(?)Km1,m2 by the similar method. Where G1 is any graph, Km1,m2 is a complete bipartite graph. We also give examples and tables to explain our results.
The third chapter consists of two sections. In the first section, we list some special graphs which have property R(SR/NR) according to the known research results. In the second section, we characterize general graphs which have property R(NR) according to the corresponding results of sign-inverse graph and balanced sign-graph, and research the conditions which these graphs satisfy.
在第一章引言中,我们回顾了图谱理论的研究历史及现状,给出了图谱的基本定义,符号及记号.我们也给出了冠图和图的R(SR)-性质的相关概念,列举了前人的一些关于冠图的谱,非奇异图的R(SR)-性质的研究成果.我们了解到某些冠图具有R(SR)-性质,但具有R(SR)-性质的图却不一定都是冠图.
第二章分为两节,第一节我们通过分类讨论的方法完全刻画了冠图G1 (?) Km1,m2的邻接谱,第二节我们又类似的刻画了冠图G1 (?) Km1,m2的Q-谱,其中G1是任意的图,Km1,m2是完全二部图,m1
The theory of graphs spectra is an important research project, it is a crossing area between graph theory and algebra. This field mostly research the spectral character of graphs, the graphic character of graph spectrum and the corresponding questions. In literature [2] and [3], there has been some results about the spectrum of corona graphs and property R(SR) of nonsingular graphs. For the connected graph G1 and a regular graph G2, the adjacency spec-trum of G1(?)G2 has been determined. In the case of G2 being any graph, the L-spectrum of G1(?)G2 has been completely characterized, but it is quite difficult to determine the adjacency spectrum and Q-spectrum of G1(?)G2. This paper is focus on the adjacency spectrum and Q-spectrum of corona graphs G1(?)Km1,m2, we also further research property R(SR/NR) of nonsingular graphs. The main results are as follows:
In the first chapter, introduction, we review the research history and present situation. Then we give the basic definitions, symbols and notations about graph spectrum. We also give the corresponding concepts about corona graphs and property R(SR) of nonsingular graphs. We know that some corona graphs have property R(SR), but the graphs which have property R(SR) are not always corona graphs.
The second chapter consists of two sections. In the first section, we completely charac-terize the adjacency spectrum of the corona graph G1(?)Km1,m2 by the method of classified discussion. In the second section, we characterize the Q-spectrum of G1(?)Km1,m2 by the similar method. Where G1 is any graph, Km1,m2 is a complete bipartite graph. We also give examples and tables to explain our results.
The third chapter consists of two sections. In the first section, we list some special graphs which have property R(SR/NR) according to the known research results. In the second section, we characterize general graphs which have property R(NR) according to the corresponding results of sign-inverse graph and balanced sign-graph, and research the conditions which these graphs satisfy.
引文
[1]D.M.Cvetkovic, M.Doob and H.Sachs. Spectra of Graphs. Academic Press, NewYork,1980.
[2]S.Barik, S.Pati and B.K.Sarma. The spectrum of the corona of two graphs. Discrete Mathe-matics,21(2007), pp.47-56.
[3]S.Barik, M.Neumann and S.Pati. On nonsingular trees and a reciprocal eigenvalue property. Linear Multilinear Algebra,54(2006), pp.453-465.
[4]R.A.Brualdi and H.J.Ryser. Combinatorial Matrix Theory. Encyclopedia of Mathematics and its Applications, Cambridge University Press,Cambridge, UK,1991.
[5]M.Fiedler. Algebraic connectivity of graphs. Czechoslovak Math.J.,23(1973), pp.298-305.
[6]F.Harary. Graph Theory. Addison -Wesley, Reading, MA,1969.
[7]F.Buckly, L.L.Doty and F.Harary, On graphs with signed inverses, Networks,18(1998), pp.151-157.
[8]F.Harary and H.Minc, Which nonnegative matrices are self-inverse? Math.Mag.,49(1976), pp.91-92.
[9]C.D.Godsil, Inverses of Trees, Combinatorica 5(1)(1985), pp.33-39.
[10]F.Harary, On the notion of balance of a signed graph, Mich.Math.J.2(1953), pp.143-146.
[11]M.Lewin and M.Neumann, On the inverse M-matrix problem for (0,1)-matrices, Linear Alge-bra and its Applications,30(1980), pp.41-50.
[12]S.Pavlikova and J.Krc-jediny, On the inverse and dual index of a tree, Linear and Multilinear Algebra, 28(1990), pp.93-109.
[13]Xu,G.H.,1997, On the spectral radius of trees with perfect matching. Combinatorics and Graph Theory.
[14]Tan Xuezhong, Liu Bolian. On the nullity of graphs. Linear Algebra and its Applications 408(2005), pp.212-220.
[15]Song Chunyan, Huang Qiongxiang, The nullity of Unicyclic Graph.
[16]R.Frucht and F.Harary, On the corona of two graphs. Aequationes Mathematics, 4(1970), pp.322-325.
[17]F.Harary, The determinant of the adjacency matrix of a graph, SIAM Rev, 4(1962), pp.202-210.
[18]D.Cvetkovic, I.Gutman and S.Simic, On Self Pseudo-inverse Graphs, Univ. Beograd Publ. Elektrotechn. Fak.Ser.Math. Fiz., No.602-633(1978), pp.111-117.
[19]S.Friedland, The Maximal Eigenvalue of (0,1)- matrices with Prescribed Number of Ones, Linear Algebra and its Applications, 64(1985), pp.33-69.
[20]L.Lovasz and I.Pelikan, On the Eigenvalues of Trees, Periodica Math. Hung. 3(1973), pp.175-182.
[21]Bridges, W.G., A class of normal (0,1)-martices. Canad. J. Math.25(1973), pp.621-626.
[22]Chao,C.Y., A note on the eigenvalue of a graph. J. Comb.Theory(B) 10(1971), pp.301-302.
[23]E.V.Haynsworth, Applications of a theorem on partitioned matrices. J. Res. Nat. Bureau Stand. 62B(1959), pp.73-78.
[24]J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, American Elsevier, New York, Macmillan, London,1976.
[2]S.Barik, S.Pati and B.K.Sarma. The spectrum of the corona of two graphs. Discrete Mathe-matics,21(2007), pp.47-56.
[3]S.Barik, M.Neumann and S.Pati. On nonsingular trees and a reciprocal eigenvalue property. Linear Multilinear Algebra,54(2006), pp.453-465.
[4]R.A.Brualdi and H.J.Ryser. Combinatorial Matrix Theory. Encyclopedia of Mathematics and its Applications, Cambridge University Press,Cambridge, UK,1991.
[5]M.Fiedler. Algebraic connectivity of graphs. Czechoslovak Math.J.,23(1973), pp.298-305.
[6]F.Harary. Graph Theory. Addison -Wesley, Reading, MA,1969.
[7]F.Buckly, L.L.Doty and F.Harary, On graphs with signed inverses, Networks,18(1998), pp.151-157.
[8]F.Harary and H.Minc, Which nonnegative matrices are self-inverse? Math.Mag.,49(1976), pp.91-92.
[9]C.D.Godsil, Inverses of Trees, Combinatorica 5(1)(1985), pp.33-39.
[10]F.Harary, On the notion of balance of a signed graph, Mich.Math.J.2(1953), pp.143-146.
[11]M.Lewin and M.Neumann, On the inverse M-matrix problem for (0,1)-matrices, Linear Alge-bra and its Applications,30(1980), pp.41-50.
[12]S.Pavlikova and J.Krc-jediny, On the inverse and dual index of a tree, Linear and Multilinear Algebra, 28(1990), pp.93-109.
[13]Xu,G.H.,1997, On the spectral radius of trees with perfect matching. Combinatorics and Graph Theory.
[14]Tan Xuezhong, Liu Bolian. On the nullity of graphs. Linear Algebra and its Applications 408(2005), pp.212-220.
[15]Song Chunyan, Huang Qiongxiang, The nullity of Unicyclic Graph.
[16]R.Frucht and F.Harary, On the corona of two graphs. Aequationes Mathematics, 4(1970), pp.322-325.
[17]F.Harary, The determinant of the adjacency matrix of a graph, SIAM Rev, 4(1962), pp.202-210.
[18]D.Cvetkovic, I.Gutman and S.Simic, On Self Pseudo-inverse Graphs, Univ. Beograd Publ. Elektrotechn. Fak.Ser.Math. Fiz., No.602-633(1978), pp.111-117.
[19]S.Friedland, The Maximal Eigenvalue of (0,1)- matrices with Prescribed Number of Ones, Linear Algebra and its Applications, 64(1985), pp.33-69.
[20]L.Lovasz and I.Pelikan, On the Eigenvalues of Trees, Periodica Math. Hung. 3(1973), pp.175-182.
[21]Bridges, W.G., A class of normal (0,1)-martices. Canad. J. Math.25(1973), pp.621-626.
[22]Chao,C.Y., A note on the eigenvalue of a graph. J. Comb.Theory(B) 10(1971), pp.301-302.
[23]E.V.Haynsworth, Applications of a theorem on partitioned matrices. J. Res. Nat. Bureau Stand. 62B(1959), pp.73-78.
[24]J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, American Elsevier, New York, Macmillan, London,1976.