Page 124 - Textos de Matemática Vol. 39

114 RUSSELL MERRIS
Problem 7. Prove or disprove the existence of nonisomorphic, 3-connected graphs G and H such that per(xI − L(G)) = per(xI − L(H)), where “per” is the permanent function.
References
[1] K. A. Berman, Bicycles and spanning trees, SIAM J. Alg. Disc. Meth. 7 (1986), 1-12.
[2] I. Faria, Multiplicity of integer roots of polynomials of graphs, Linear Algebra Appl. 229
(1995), 15-35.
[3] M. Fiedler, Algebraic connectivity of graphs, Czech. Math. J. 23 (1973), 298-305.
[4] M. Fiedler, Eigenvectors of acyclic matrices, Czech. Math. J. 25 (1975), 607-618.
[5] S. Foldes and P. L. Hammer, Split graphs, Proceedings of the 8th South-Eastern Con-
ference on Combinatorics, Graph Theory and Computing, 1977, pp 311-315.
[6] R. Grone, R. Merris, and W. Watkins, Combinatorial and Graph Theoretic Problems in Linear Algebra (R. Brualdi, S. Friedland and V. Klee, eds.), IMA Vol.s in Math. and Its
Appl. 50, Springer Verlag, NY, 1993, pp 175 180.
[7] W. H¨asselbarth, Die Verzweigtheit von Graphen, Comm. in Math. & Computer Chem.
(MATCH) 16 (1984), 3-17.
[8] D. J. Lorenzini, A finite group attached to the laplacian of a graph, Discrete Math. 91
(1991), 277-282.
[9] A. W. Marshall and I. Olkin, Inequalities: Theory of Majorization and Its Appl., Aca-
demic Press, New York, 1979.
[10] R. Merris, The number of eigenvalues greater than two in the Laplacian spectrum of a
graph, Port. Math. 48 (1991), 345-349.
[11] R. Merris, Degree maximal graphs are Laplacian integral, Linear Algebra Appl. 199
(1994), 381-389.
[12] R. Merris, Graph Theory, Wiley Interscience, New York, 2001.
[13] R. Merris, Split graphs, European J. Combinatorics 24 (2003), 413-430.
[14] R. Merris and T. Roby, The lattice of threshold graphs, J. Inequalities Pure & Appl.
Math. 6 Issue 1, Article 2 (2005), 21 pp.
[15] G. J. Ming and T. S. Wang, A relation between the matching number and Laplacian
spectrum of a graph, Linear Algebra Appl. 325 (2001), 71-74.
[16] S.-L. Peng and C.-K. Chen, On the interval completion of chordal graphs, Discrete Appl.
Math. 154 (2006), 1003-1010.
[17] E. Ruch and I. Gutman, The branching extent of graphs, J. Combin. Inform. System
Sci. 4 (1979), 285-295.
[18] G. Sierksma and H. Hoogeveen, Seven criteria for sequences being graphic, J. Graph
Theory 15 (1991), 223-231.
[19] R. Tyshkevich, Decomposition of graphical sequences and unigraphs, Discrete Math. 220
(2000), 201-238.
Department of Mathematics and Computer Science California State University
Hayward
CA 94542, USA
E-mail address: Russ.Merris@CSUEastBay.edu