定向图的斜邻接矩阵的积和多项式（英文）
|
摘要
设G~σ为简单图G的一个定向.介绍了定向图G~σ的积和多项式,得到了G~σ的积和多项式根据图的结构表示的系数公式,证明了一个图G的所有定向图有相同的积和多项式当且仅当G没有偶圈.对定向图G~σ的积和多项式的根也进行了研究.
Let G~σ be an orientation of a simple graph G.The permanental polynomial of an oriented graph G~σwas introduced and the coefficients of the permanent polynomial of G° were interpreted in terms of the graph structure of G~σ.It was proved that all orientations G~σ of G have the same permanental polynomial if and only if G has no even cycle.The roots of the permanental polynomial of G~σ were studied.
Let G~σ be an orientation of a simple graph G.The permanental polynomial of an oriented graph G~σwas introduced and the coefficients of the permanent polynomial of G° were interpreted in terms of the graph structure of G~σ.It was proved that all orientations G~σ of G have the same permanental polynomial if and only if G has no even cycle.The roots of the permanental polynomial of G~σ were studied.
引文
[1]Lovasz L,Plummer M D.Matching theory(annals of discrete mathematics 29)[M].Amsterdam:North-Holland,1986:315-329.
[2]Cavers M,Cioaba S M,Fallat S,et al.Skew-adjacency matrices of graphs[J].Linear Algebra Appl,2012,436(12):4512-4529.
[3]Adiga C,Balakrishnan R,So W.The skew energy of a digraph[J].Linear Algebra Appl,2010,432(7):1825-1835.
[4]Valiant L G.The complexity of computing the permanent[J].Theoret Comput Sci,1979,8(2):189-201.
[5]Merris R,Rebman K R,Watkins W.Permanental polynomials of graphs[J].Linear Algebra Appl,1981,38:273-288.
[6]Kasum D,Trinajstic N,Gutman I.Chemical graph theory M:on permanental polynomial[J].Croat Chem Acta,1981,54(3):321-328.
[7]Yan Wei-geng,Zhang Fu-ji.On the permanental polynomials of some graphs[J].Journal of Mathematical Chemistry,2004,35(3):175-188.
[8]Godsil C D,Gutman I.On the theory of the matching polynomial[J].Journal of Graph Theory,1981,5(2):137-144.
[9]Zhang H,Liu S,Li W.A note on the permanental roots of bipartite graphs[J].Discussiones Mathematicae Graph Theory,2014,34(1):49-56.
[10]Borowiecki M.On spectrum and per-spectrum of graphs[J].Publications De L Institut Mathematique,1985,38(52):31-33.
[11]Borowiecki M,Jozwiak T.A note on characteristic and permanental polynomials of multigraphs[C]//Graph Theory,Berlin:Springer-Verlag,1983:75-78.
[2]Cavers M,Cioaba S M,Fallat S,et al.Skew-adjacency matrices of graphs[J].Linear Algebra Appl,2012,436(12):4512-4529.
[3]Adiga C,Balakrishnan R,So W.The skew energy of a digraph[J].Linear Algebra Appl,2010,432(7):1825-1835.
[4]Valiant L G.The complexity of computing the permanent[J].Theoret Comput Sci,1979,8(2):189-201.
[5]Merris R,Rebman K R,Watkins W.Permanental polynomials of graphs[J].Linear Algebra Appl,1981,38:273-288.
[6]Kasum D,Trinajstic N,Gutman I.Chemical graph theory M:on permanental polynomial[J].Croat Chem Acta,1981,54(3):321-328.
[7]Yan Wei-geng,Zhang Fu-ji.On the permanental polynomials of some graphs[J].Journal of Mathematical Chemistry,2004,35(3):175-188.
[8]Godsil C D,Gutman I.On the theory of the matching polynomial[J].Journal of Graph Theory,1981,5(2):137-144.
[9]Zhang H,Liu S,Li W.A note on the permanental roots of bipartite graphs[J].Discussiones Mathematicae Graph Theory,2014,34(1):49-56.
[10]Borowiecki M.On spectrum and per-spectrum of graphs[J].Publications De L Institut Mathematique,1985,38(52):31-33.
[11]Borowiecki M,Jozwiak T.A note on characteristic and permanental polynomials of multigraphs[C]//Graph Theory,Berlin:Springer-Verlag,1983:75-78.