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.

Resumen

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.
CCET -DME.
Nair Abreu, Universidade Federal do Rio de Janeiro.
CT -PEP -COPPE.
Lilian Markenzon, Universidade Federal do Rio de Janeiro.
CCMN -NCE.

Citas

[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).
Publicado
2017-10-20
Cómo citar
Malajovich, B., Abreu, N., & Markenzon, L. (2017). On the characteristic polynomial of the power of a path. Proyecciones. Journal of Mathematics, 36(3), 529-543. Recuperado a partir de http://www.revistaproyecciones.cl/article/view/2395
Sección
Artículos