×

On the spectral characterization of some unicyclic graphs. (English) Zbl 1242.05165

Let \(H(n;q,n_1,n_2)\) be a graph with \(n\) vertices containing a cycle \(C_q\) and two hanging paths \(P_{n_1}\) and \(P_{n_2}\) attached at the same vertex of the cycle. In this work
(i)
it is proved that except for the \(A\)-cospectral graphs \(H(12; 6,1,5)\) and \(H(12; 8,2,2)\), no two non-isomorphic graphs of the form \(H(n;q,n_1,n_2)\) are \(A\)-cospectral;
(ii)
it is proved that all graphs \(H(n;q,n_1,n_2)\) are determined by their \(L\)-spectra and
(iii)
all graphs \(H(n;q,n_1,n_2)\) are determined by their \(Q\)-spectra, except for graphs \(H(2a+4;a+3,\frac{a}{2},\frac{a}{2}+1)\) with \(a\) being a positive even number and \(H(2b;b,\frac{b}{2},\frac{b}{2})\) with \(b\geq 4\) being an even number.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Biggs, N. L., Algebraic Graph Theory (1993), Cambridge University Press · Zbl 0501.05039
[2] Boulet, R.; Jouve, B., The lollipop graph is determined by its spectrum, Electron. J. Combin., 15, R74 (2008) · Zbl 1163.05324
[3] Brualdi, R. A.; Ryser, H. J., Combinatorial Matrix Theory (1991), Cambridge U. P.: Cambridge U. P. New York · Zbl 0746.05002
[4] Cvetković, D. M., New theorems for signless Laplacians eigenvalues, Bull. Acad. Serbe Sci. Arts, Cl. Sci. Math. Natur., Sci. Math., 137, 33, 131-146 (2008) · Zbl 1199.05212
[5] Cvetković, D. M.; Doob, M.; Sachs, H., Spectral of Graphs Theory and Applications (1980), Academic press: Academic press New York, San Francisco, London
[6] Cvetković, D. M.; Rowlinson, P., Spectra of unicyclic graph, Graphs Combin., 3, 7-23 (1987) · Zbl 0623.05038
[7] Cvetković, D. M.; Rowlinson, P.; Simić, S. K., Signless Laplacians of finite graphs, Linear Algebra Appl., 423, 155-171 (2007) · Zbl 1113.05061
[8] Cvetković, D. M.; Simić, S. K., Towards a spectral theory of graphs based on signless Laplacian, I, Publ. Inst. Math. (Beograd) (N.S.), 85, 99, 1-15 (2009)
[9] Gantmacher, F. R., The Theory of Matrices, vol. II (1959), Chelsea: Chelsea New York · Zbl 0085.01001
[10] Godsil, C. D.; McKay, B. D., Constructing cospectral graphs, Aequationes Math., 25, 257-268 (1982) · Zbl 0527.05051
[11] Haemers, W. H.; Liu, X.-G.; Zhang, Y.-P., Spectral characterizations of lollipop graphs, Linear Algebra Appl., 428, 2415-2423 (2008) · Zbl 1226.05156
[12] Horn, R. A.; Johnson, C. R., Matrix Analysis (1985), Cambridge University Press: Cambridge University Press New York · Zbl 0576.15001
[13] Kelmans, A. K., The number of trees in a graph I, II, Autom. Remote Control, 26, 2118-2129 (1965), 27 (1966) 233-241, translated from Avtomatika i Telemekhanika 26 (1965) 2194-2204 and 27 (1966) 56-65 [in Russian] · Zbl 0146.45902
[14] Kelmans, A. K.; Chelnokov, V. M., A certain polynomial of a graph and graphs with an extremal number of trees, J. Combin. Theory, Ser. B, 16, 197-214 (1974) · Zbl 0277.05104
[15] Li, J.-S.; Pan, Y.-L., A note on the second largest eigenvalue of the Laplacian matrix of a graph, Linear Multilinear Algebra, 48, 20, 117-121 (2000) · Zbl 0979.15016
[16] Liu, X.-G.; Zhang, Y.-P.; Gui, X.-Q., The multi-fan graphs are determined by their Laplacian spectra, Discrete Math., 308, 4267-4271 (2008) · Zbl 1225.05172
[17] Li, J.-S.; Zhang, X.-D., On the Laplacian eigenvalues of a graph, Linear Algebra Appl., 285, 305-307 (1998) · Zbl 0931.05052
[18] Oliveira, C. S.; de Abreu, N. M.M.; Jurkiewilz, S., The characteristic polynomial of the Laplacian of graphs in \((a, b)\)-linear cases, Linear Algebra Appl., 365, 113-121 (2002)
[19] Omidi, G. R., On a signless Laplacian spectral characterizaiton of \(T\)-shape trees, Linear Algebra Appl., 431, 1607-1615 (2009) · Zbl 1169.05351
[20] Omidi, G. R.; Tajbakhsh, K., Starlike trees are determined by their Laplacian spectrum, Linear Algebra Appl., 422, 654-658 (2007) · Zbl 1114.05064
[21] Simić, S. K.; Stanić, Z., \(Q\)-integral graphs with edge-degrees at most five, Discrete Math., 308, 4625-4634 (2008) · Zbl 1156.05037
[22] Smith, J. H., Some properties of spectrum of graphs, (Guy, R.; Hanani, H.; Sauer, N.; Schönheim, J., Combinatorial Structures and their Applications (1970), Gordon and Breach, Science Publ., Inc.: Gordon and Breach, Science Publ., Inc. New York, London, Paris), 403-406
[23] van Dam, E. R.; Haemers, W. H., Which graphs are determined by their spectrum?, Linear Algebra Appl., 373, 241-272 (2003) · Zbl 1026.05079
[24] van Dam, E. R.; Haemers, W. H., Developments on spectral characterizations of graphs, Discrete Math., 309, 576-586 (2009) · Zbl 1205.05156
[25] Wang, J.-F.; Huang, Q.-X.; Belardo, F.; Li Marzi, E. M., On the spectral characterizations of \(\infty \)-graphs, Discrete Math., 310, 1845-1855 (2010) · Zbl 1231.05174
[26] Wang, W.; Xu, C.-X., Note: the T-shape tree is determined by its Laplacian spectrum, Linear Algebra Appl., 419, 78-81 (2006) · Zbl 1107.05064
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.