On the characteristic polynomial of the power of a path

  • Beatriz Malajovich Universidade Federal do Estado do Rio de Janeiro.
  • Nair Abreu Universidade Federal do Rio de Janeiro.
  • Lilian Markenzon Universidade Federal do Rio de Janeiro.
Palabras clave: Power of a path, 4-cycles, Characteristic coefficients.


We determine a closed-form expression for the fifth characteristic coefficient of the power of a path. To arrive at this result, we establish the number of 4-cycles in the graph by means of their structural prop- erties. The method developed might be applied to other wel l-structured graph classes in order to count 4-cycles or modified to count cycles of different length.

Biografía del autor

Beatriz Malajovich, Universidade Federal do Estado do Rio de Janeiro.
Nair Abreu, Universidade Federal do Rio de Janeiro.
Lilian Markenzon, Universidade Federal do Rio de Janeiro.


[1] N. Alon, R. Yuster, U. Zwick, Finding and counting given length cy- cles, Algorithmica 17 (3), pp. 209—223, (1997).

[2] MR1271140 N. Biggs, Algebraic Graph Theory, 2nd ed., Cambridge University Press, Cambridge, pp. 44—46, (1993).

[3] MR2882891 A. E. Brouwer, W. H. Haemers, Spectra of Graphs, Uni- versitext, Springer, New York, (2012).

[4] K. Buchin, K. Kriegel, A. Schulz, R. Seidel, On the number of cycles in planar graphs, in Graph-Theoretic Concepts in Computer Science. Lect. Notes Comput. Sc., Vol. 1335, Springer-Verlag, Berlin, pp. 15-24, (1997).

[5] D. Cvetkovi´ c, M. Doob, H. Sachs, Spectra of Graphs — Theory and Application, Academic Press, New York, (1980).

[6] D. Cvetkovi c, P. Rowlinson, S. Simic, An Introduction to the Theory of Graph Spectra, Cambridge University Press, Cambridge, (2010).

[7] N. Chiba, T. Nishizeki, Arboricity and subgraph listing algorithms, SIAM J. Comput. 14 (1), pp. 210—223, (1985).

[8] R. Diestel, Graph Theory, 2nd ed., Graduate Texts in Mathematics, 173, Springer-Verlag, New York, (2000).

[9] J. Guo, J. Li, W. C. Shiu, On the Laplacian, signless Laplacian and normalized Laplacian characteristic polynomials of a graph, Czechoslo- vak Math. J. 63 (138), pp. 701—720, (2013).

[10] I. Gutman, D. M. Cvetkovic, The reconstruction problem for charac- teristic polynomials of graphs, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. Fiz., 498—541, pp. 45—48, (1975).

[11] E. M. Hagos, The characteristic polynomial of a graph is recon- structible from the characteristic polynomials of its vertex-deleted sub- graphs and their complements, Electron.J.Combin.7, Research Paper 12, 9 pp. (electronic), (2000).

[12] L. Markenzon, C. Justel, N. Paciornik, Subclasses of k-trees: char- acterization and recognition, Discrete Appl. Math. 154, pp. 818—825, (2006).

[13] L.Markenzon, C.F.E.M.Waga, Uma generaliza¸cao de grafos caminho e leque: o estudo da subcolora¸cao, in Annals XLIV SBPO SOBRAPO, Rio de Janeiro, (2012).

[14] L. Markenzon, C.F.E.M. Waga, Generalizing path and fan graphs: subcoloring and toughness, Pesq. Oper. 34, pp. 107—116, (2014).

[15]P.E.Moraes,N.M.M.Abreu,S.Jurkiewicz,Thefifth and sixth coefficients of the characteristic polynomial of a graph, Electron. Notes Discrete Math. 11, pp. 201—208, (2002).

[16] P.R.C. Pereira, L. Markenzon, O. Vernet, A clique-difference encoding scheme for labelled k-path graphs, Discrete Appl. Math. 156 (17), pp. 3216—3222, (2008).

[17] G. M. Prabhu, N. Deo, On the power of a perturbation for testing nonisomorphism of graphs, BIT 24 (3), pp. 302—307, (1984).

[18] D. Richards, Finding short cycles in planar graphs using separators, J. Algorithms 7 (3), pp. 382—394, (1986).

[19] T. Schank, D. Wagner, Finding, counting and listing all triangles in large graphs, an experimental study, in Experimental and Efficient Algorithms”, Lect. Notes Comput. Sc., Vol. 3503, pp. 606—609, Springer- Verlag, Berlin, (2005).

[20] A. J. Schwenk, Computing the characteristic polynomial of a graph, in Graphs and combinatorics, (Proc. Capital Conf., George Washington Univ., Washington, D.C. 1973). Lect. Notes Math., Vol. 406, pp. 153— 172, Springer Verlag, Berlin, (1974).

[21] S. K. Simic, Z. Stanic, The polynomial reconstruction of unicyclic graphs is unique, Linear Multilinear A. 55 (1), pp. 35—43, (2007).

[22] J. Zhang, X. Zhang, Laplacian coefficients of unicyclic graphs with the number of leaves and girth, Appl. Anal. Discrete Math. 8 (2), pp. 330—345, (2014).
Cómo citar
Malajovich, B., Abreu, N., & Markenzon, L. (2017). On the characteristic polynomial of the power of a path. Proyecciones. Revista De Matemática, 36(3), 529-543. Recuperado a partir de http://www.revistaproyecciones.cl/article/view/2395