A Note on the Permanental Roots of Bipartite Graphs

Heping Zhang; Shunyi Liu; Wei Li

Discussiones Mathematicae Graph Theory (2014)

  • Volume: 34, Issue: 1, page 49-56
  • ISSN: 2083-5892

Abstract

top
It is well-known that any graph has all real eigenvalues and a graph is bipartite if and only if its spectrum is symmetric with respect to the origin. We are interested in finding whether the permanental roots of a bipartite graph G have symmetric property as the spectrum of G. In this note, we show that the permanental roots of bipartite graphs are symmetric with respect to the real and imaginary axes. Furthermore, we prove that any graph has no negative real permanental root, and any graph containing at least one edge has complex permanental roots.

How to cite

top

Heping Zhang, Shunyi Liu, and Wei Li. "A Note on the Permanental Roots of Bipartite Graphs." Discussiones Mathematicae Graph Theory 34.1 (2014): 49-56. <http://eudml.org/doc/267601>.

@article{HepingZhang2014,
abstract = {It is well-known that any graph has all real eigenvalues and a graph is bipartite if and only if its spectrum is symmetric with respect to the origin. We are interested in finding whether the permanental roots of a bipartite graph G have symmetric property as the spectrum of G. In this note, we show that the permanental roots of bipartite graphs are symmetric with respect to the real and imaginary axes. Furthermore, we prove that any graph has no negative real permanental root, and any graph containing at least one edge has complex permanental roots.},
author = {Heping Zhang, Shunyi Liu, Wei Li},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {permanent; permanental polynomial; permanental roots},
language = {eng},
number = {1},
pages = {49-56},
title = {A Note on the Permanental Roots of Bipartite Graphs},
url = {http://eudml.org/doc/267601},
volume = {34},
year = {2014},
}

TY - JOUR
AU - Heping Zhang
AU - Shunyi Liu
AU - Wei Li
TI - A Note on the Permanental Roots of Bipartite Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2014
VL - 34
IS - 1
SP - 49
EP - 56
AB - It is well-known that any graph has all real eigenvalues and a graph is bipartite if and only if its spectrum is symmetric with respect to the origin. We are interested in finding whether the permanental roots of a bipartite graph G have symmetric property as the spectrum of G. In this note, we show that the permanental roots of bipartite graphs are symmetric with respect to the real and imaginary axes. Furthermore, we prove that any graph has no negative real permanental root, and any graph containing at least one edge has complex permanental roots.
LA - eng
KW - permanent; permanental polynomial; permanental roots
UR - http://eudml.org/doc/267601
ER -

References

top
  1. [1] B. Anderson, J. Jackson and M. Sitharam, Descartes’ rule of signs revisited, Amer. Math. Monthly 105 (1998) 447-451. doi:10.2307/3109807[Crossref] Zbl0913.12001
  2. [2] F. Belardo, V.D. Filippis and S.K. Simić, Computing the permanental polynomial of matrix from a combinatorial viewpoint , MATCH Commun. Math. Comput. Chem. 66 (2011) 381-396. Zbl1289.05268
  3. [3] G.D. Birkhoff and D.C. Lewis, Chromatic polynomials, Trans. Amer. Math. Soc. 60 (1946) 355-451. doi:10.2307/1990348[Crossref] 
  4. [4] M. Borowiecki, On spectrum and per-spectrum of graphs, Publ. Inst. Math. (Beograd) 38 (1985) 31-33. Zbl0581.05036
  5. [5] M. Borowiecki and T. Jóźwiak, A note on characteristic and permanental polynomials of multigraphs, in: Graph Theory, Borowiecki, Kennedy and Syslo (Ed(s)), (Berlin, Springer-Verlag, 1983) 75-78. Zbl0525.05046
  6. [6] M. Borowiecki and T. Jóźwiak, Computing the permanental polynomial of a multigraph, Discuss. Math. V (1982) 9-16. Zbl0514.05044
  7. [7] G.G. Cash, The permanental polynomial , J. Chem. Inf. Comput. Sci. 40 (2000) 1203-1206. doi:10.1021/ci000031d[Crossref] 
  8. [8] G.G. Cash, Permanental polynomials of smaller fullerenes, J. Chem. Inf. Comput. Sci. 40 (2000) 1207-1209. doi:10.1021/ci0000326[Crossref] 
  9. [9] R. Chen, A note on the relations between the permanental and characteristic polynomials of coronoid hydrocarbons, MATCH Commun. Math. Comput. Chem. 51 (2004) 137-148. Zbl1051.05058
  10. [10] D. Cvetković, M. Doob and H. Sachs, Spectra of Graphs: Third Edition (Johann Ambrosius Barth Verlag, Heidelberg-Leipzig, 1995). Zbl0824.05046
  11. [11] E.J. Farrell, An introduction to matching polynomials, J. Combin. Theory (B) 27 (1979) 75-86. doi:10.1016/0095-8956(79)90070-4[Crossref] 
  12. [12] I. Gutman and G.G. Cash, Relations between the permanental and characteristic polynomials of fullerenes and benzenoid hydrocarbons, MATCH Commun. Math. Comput. Chem. 45 (2002) 55-70. Zbl1026.05081
  13. [13] D. Kasum, N. Trinajstić and I. Gutman, Chemical graph theory. III. On permanental polynomial , Croat. Chem. Acta 54 (1981) 321-328. 
  14. [14] L. Lovász and M.D. Plummer, Matching Theory, Annals of Discrete Mathematics, Vol. 29 (North-Holland, New York, 1986). 
  15. [15] R. Merris, K.R. Rebman and W. Watkins, Permanental polynomials of graphs, Linear Algebra Appl. 38 (1981) 273-288. doi:10.1016/0024-3795(81)90026-4[Crossref][WoS] Zbl0474.05049
  16. [16] J. Turner, Generalized matrix functions and the graph isomorphism problem, SIAM J. Appl. Math. 16 (1968) 520-526. doi:10.1137/0116041[Crossref] Zbl0185.51701
  17. [17] L.G. Valiant, The complexity of computing the permanent , Theoret. Comput. Sci. 8 (1979) 189-201. doi:10.1016/0304-3975(79)90044-6[Crossref] 
  18. [18] W. Yan and F. Zhang, On the permanental polynomials of some graphs, J. Math. Chem. 35 (2004) 175-188. doi:10.1023/B:JOMC.0000033254.54822.f8[Crossref] Zbl1048.05062
  19. [19] H. Zhang and W. Li, Computing the permanental polynomials of bipartite graphs by Pfaffian orientation, Discrete Appl. Math. 160 (2012) 2069-2074. doi:10.1016/j.dam.2012.04.007 [Crossref][WoS] Zbl1246.05100

NotesEmbed ?

top

You must be logged in to post comments.