PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2014 | 34 | 1 | 49-56
Tytuł artykułu

A Note on the Permanental Roots of Bipartite Graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Słowa kluczowe
Wydawca
Rocznik
Tom
34
Numer
1
Strony
49-56
Opis fizyczny
Daty
wydano
2014-02-01
online
2014-02-14
Twórcy
autor
  • School of Mathematics and Statistics Lanzhou University Lanzhou, Gansu 730000, P.R. China, zhanghp@lzu.edu.cn
autor
  • School of Mathematics and Statistics Lanzhou University Lanzhou, Gansu 730000, P.R. China, liushuny@gmail.com
autor
  • School of Mathematics and Statistics Lanzhou University Lanzhou, Gansu 730000, P.R. China, li_w07@lzu.edu.cn
Bibliografia
  • [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]
  • [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.
  • [3] G.D. Birkhoff and D.C. Lewis, Chromatic polynomials, Trans. Amer. Math. Soc. 60 (1946) 355-451. doi:10.2307/1990348[Crossref]
  • [4] M. Borowiecki, On spectrum and per-spectrum of graphs, Publ. Inst. Math. (Beograd) 38 (1985) 31-33.
  • [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.
  • [6] M. Borowiecki and T. Jóźwiak, Computing the permanental polynomial of a multigraph, Discuss. Math. V (1982) 9-16.
  • [7] G.G. Cash, The permanental polynomial , J. Chem. Inf. Comput. Sci. 40 (2000) 1203-1206. doi:10.1021/ci000031d[Crossref]
  • [8] G.G. Cash, Permanental polynomials of smaller fullerenes, J. Chem. Inf. Comput. Sci. 40 (2000) 1207-1209. doi:10.1021/ci0000326[Crossref]
  • [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.
  • [10] D. Cvetković, M. Doob and H. Sachs, Spectra of Graphs: Third Edition (Johann Ambrosius Barth Verlag, Heidelberg-Leipzig, 1995).
  • [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] 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.
  • [13] D. Kasum, N. Trinajstić and I. Gutman, Chemical graph theory. III. On permanental polynomial , Croat. Chem. Acta 54 (1981) 321-328.
  • [14] L. Lovász and M.D. Plummer, Matching Theory, Annals of Discrete Mathematics, Vol. 29 (North-Holland, New York, 1986).
  • [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]
  • [16] J. Turner, Generalized matrix functions and the graph isomorphism problem, SIAM J. Appl. Math. 16 (1968) 520-526. doi:10.1137/0116041[Crossref]
  • [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] 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]
  • [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]
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1704
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.