Investigation on Singularity, Signature Matrix and Spectrum of Mixed Graphs
|
摘要
The spectral theory of graph is an important branch of graph theory, and the main part of this theory is the connection between the spectral properties and the structural properties, characterization of the structural properties of graphs. We discuss the problems about singularity, signature matrix and spectrum of mixed graphs. Without loss of generality, parallel edges and loops are permitted in mixed graphs. Let G_1 and G_2 be connected mixed graphs which are obtained from an underlying graph G. When G_1 and G_2 have the same singularity, the number of induced cycles in G_i(i=1, 2) is l(l=1,l>1), the length of the smallest induced cycles is 1, 2, at least 3. According to conclusions and mathematics induction, we find that the singularity of corresponding induced cycles in G_1 and G_2 are the same if and only if there exists a signature matrix D such that L(G_2)=D~TL(G_1)D. D may be the product of some signature matrices. If L(G_2)=D~TL(G_1)D, G_1 and G_2 have the same spectrum.
The spectral theory of graph is an important branch of graph theory, and the main part of this theory is the connection between the spectral properties and the structural properties, characterization of the structural properties of graphs. We discuss the problems about singularity, signature matrix and spectrum of mixed graphs. Without loss of generality, parallel edges and loops are permitted in mixed graphs. Let G_1 and G_2 be connected mixed graphs which are obtained from an underlying graph G. When G_1 and G_2 have the same singularity, the number of induced cycles in G_i(i=1, 2) is l(l=1,l>1), the length of the smallest induced cycles is 1, 2, at least 3. According to conclusions and mathematics induction, we find that the singularity of corresponding induced cycles in G_1 and G_2 are the same if and only if there exists a signature matrix D such that L(G_2)=D~TL(G_1)D. D may be the product of some signature matrices. If L(G_2)=D~TL(G_1)D, G_1 and G_2 have the same spectrum.
The spectral theory of graph is an important branch of graph theory, and the main part of this theory is the connection between the spectral properties and the structural properties, characterization of the structural properties of graphs. We discuss the problems about singularity, signature matrix and spectrum of mixed graphs. Without loss of generality, parallel edges and loops are permitted in mixed graphs. Let G_1 and G_2 be connected mixed graphs which are obtained from an underlying graph G. When G_1 and G_2 have the same singularity, the number of induced cycles in G_i(i=1, 2) is l(l=1,l>1), the length of the smallest induced cycles is 1, 2, at least 3. According to conclusions and mathematics induction, we find that the singularity of corresponding induced cycles in G_1 and G_2 are the same if and only if there exists a signature matrix D such that L(G_2)=D~TL(G_1)D. D may be the product of some signature matrices. If L(G_2)=D~TL(G_1)D, G_1 and G_2 have the same spectrum.
引文
[1] BONDY J A,MURTY U S R.Graph theory[M].London:Springer,2008.
[2] LI X,SHI Y,GUTMAN I.Graph theory[M].Springer Science & Business Media,2012.
[3] GODSIL C,ROYLE G F.Algebraic graph theory[M].Springer Science Business Media,2013.
[4] BAPAT R B,GROSSMAN J W,KULKARNI D M.Generalized matrix tree theorem for mixed graphs[J].Linear and Multilinear Algebra,1999,46:299-312.
[5] ZHANG X D,LI J S.The Laplacian spectrum of a mixed graph[J].Linear Algebra and Its Applications,2002,353(1/2/3):11-20.
[6] ZHANG X D,LUO R.The Laplacian eigenvalues of a mixed graph[J].Linear Algebra and Its Applications,2003,362:109-119.
[7] FAN Y Z.On the least eigenvalue of a unicyclic mixed graph[J].Linear and Multilinear Algebra,2005,53(2):97-113.
[8] CHIEN M T,TAM B S.Circularity of the numerical range[J].Linear Algebra and Its Applications,1994,201:113-133.
[9] GUO J M,LI J,SHUI W C.On the Laplacian,signless Laplacian and normalized Laplacian characteristic polynomials of a graph[J].Czechoslovak Mathematical Journal,2013,63(3):701-720.
[10] WANG W,LI F,XU Z.Graphs determined by their generalized characteristic polynomials[J].Linear Algebra and Its Applications,2011,434:1378-1387.
[11] FIEDLER M.Algebraic connectivity of graphs[J].Czechoslovak Mathematical Jouranl,1973,23(2):298-305.
[12] Yu G H,LIU X,QU H.Singularity of Hermitian(quasi-) Laplacian matrix of mixed graphs[J],Applied Mathematics and Computation,2017,293:287-292.
[13] ADIGA C,RAKSHITH B R,SO W.On the mixed adjacency matrix of a mixed graph[J].Linear Algebra and Its Applications,2016,495:223-241.
[14] WHANG J J,GLEICH D F,DHILLON I S.Overlapping community detection using neighborhood-inflated seed expansion[J].IEEE Transactions on Knowledge and Data Engineering,2016,28(5):1272-1284.
[15] CHEN D,ZOU F,LU R,et al.Multi-objective optimization of community detection using discrete teaching-learning-based optimization with decomposition[J].Information Sciences,2016,369:402-418.
[16] HU D,LI X L,LIU X G,et al.The spectral distribution of random mixed graphs[J].Linear Algebra and Its Applications,2017,519:343-365.
[17] MOHAR B.Hermitian adjacency spectrum and switching equivalance of mixed graphs[J].Linear Algebra and Its Applications,2016,489:324-340.
[2] LI X,SHI Y,GUTMAN I.Graph theory[M].Springer Science & Business Media,2012.
[3] GODSIL C,ROYLE G F.Algebraic graph theory[M].Springer Science Business Media,2013.
[4] BAPAT R B,GROSSMAN J W,KULKARNI D M.Generalized matrix tree theorem for mixed graphs[J].Linear and Multilinear Algebra,1999,46:299-312.
[5] ZHANG X D,LI J S.The Laplacian spectrum of a mixed graph[J].Linear Algebra and Its Applications,2002,353(1/2/3):11-20.
[6] ZHANG X D,LUO R.The Laplacian eigenvalues of a mixed graph[J].Linear Algebra and Its Applications,2003,362:109-119.
[7] FAN Y Z.On the least eigenvalue of a unicyclic mixed graph[J].Linear and Multilinear Algebra,2005,53(2):97-113.
[8] CHIEN M T,TAM B S.Circularity of the numerical range[J].Linear Algebra and Its Applications,1994,201:113-133.
[9] GUO J M,LI J,SHUI W C.On the Laplacian,signless Laplacian and normalized Laplacian characteristic polynomials of a graph[J].Czechoslovak Mathematical Journal,2013,63(3):701-720.
[10] WANG W,LI F,XU Z.Graphs determined by their generalized characteristic polynomials[J].Linear Algebra and Its Applications,2011,434:1378-1387.
[11] FIEDLER M.Algebraic connectivity of graphs[J].Czechoslovak Mathematical Jouranl,1973,23(2):298-305.
[12] Yu G H,LIU X,QU H.Singularity of Hermitian(quasi-) Laplacian matrix of mixed graphs[J],Applied Mathematics and Computation,2017,293:287-292.
[13] ADIGA C,RAKSHITH B R,SO W.On the mixed adjacency matrix of a mixed graph[J].Linear Algebra and Its Applications,2016,495:223-241.
[14] WHANG J J,GLEICH D F,DHILLON I S.Overlapping community detection using neighborhood-inflated seed expansion[J].IEEE Transactions on Knowledge and Data Engineering,2016,28(5):1272-1284.
[15] CHEN D,ZOU F,LU R,et al.Multi-objective optimization of community detection using discrete teaching-learning-based optimization with decomposition[J].Information Sciences,2016,369:402-418.
[16] HU D,LI X L,LIU X G,et al.The spectral distribution of random mixed graphs[J].Linear Algebra and Its Applications,2017,519:343-365.
[17] MOHAR B.Hermitian adjacency spectrum and switching equivalance of mixed graphs[J].Linear Algebra and Its Applications,2016,489:324-340.