On the characteristic polynomial of the power of a path.

• Autores: Beatriz Malajovich, Nair Abreu, Lilian Markenzon
• Localización: Proyecciones: Journal of Mathematics, ISSN 0716-0917, ISSN-e 0717-6279, Vol. 36, Nº. 3, 2017, págs. 529-543
• Idioma: inglés
• DOI: 10.4067/s0716-09172017000300529
• Enlaces
  • Texto completo
• 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 properties. The method developed might be applied to other well-structured graph classes in order to count 4-cycles or modified to count cycles of different length.

• Referencias bibliográficas
  • N. Alon, R. Yuster, U. Zwick, Finding and counting given length cycles, Algorithmica 17 (3), pp. 209—223, (1997).
  • MR1271140 N. Biggs, Algebraic Graph Theory, 2nd ed., Cambridge University Press, Cambridge, pp. 44—46, (1993).
  • MR2882891 A. E. Brouwer, W. H. Haemers, Spectra of Graphs, Universitext, Springer, New York, (2012).
  • K. Buchin, K. Kriegel, A. Schulz, R. Seidel, On the number of cycles in planar graphs, in Graph-Theoretic Concepts in Computer Science. Lect....
  • D. Cvetković, M. Doob, H. Sachs, Spectra of Graphs — Theory and Application, Academic Press, New York, (1980).
  • D. Cvetković, P. Rowlinson, S. Simic, An Introduction to the Theory of Graph Spectra, Cambridge University Press, Cambridge, (2010).
  • N. Chiba, T. Nishizeki, Arboricity and subgraph listing algorithms, SIAM J. Comput. 14 (1), pp. 210—223, (1985).
  • R. Diestel, Graph Theory, 2nd ed., Graduate Texts in Mathematics, 173, Springer-Verlag, New York, (2000).
  • J. Guo, J. Li, W. C. Shiu, On the Laplacian, signless Laplacian and normalized Laplacian characteristic polynomials of a graph, Czechoslovak...
  • I. Gutman, D. M. Cvetkovic, The reconstruction problem for charac- teristic polynomials of graphs, Univ. Beograd. Publ. Elektrotehn. Fak....
  • E. M. Hagos, The characteristic polynomial of a graph is reconstructible from the characteristic polynomials of its vertex-deleted sub- graphs...
  • L. Markenzon, C. Justel, N. Paciornik, Subclasses of k-trees: characterization and recognition, Discrete Appl. Math. 154, pp. 818—825, (2006).
  • L. Markenzon, C. F. E. M. Waga, Uma generalizaçao de grafos caminho e leque: o estudo da subcoloraçao, in Annals XLIV SBPO SOBRAPO, Rio de...
  • L. Markenzon, C. F. E. M. Waga, Generalizing path and fan graphs: subcoloring and toughness, Pesq. Oper. 34, pp. 107—116, (2014).
  • P. E. Moraes,N.M.M.Abreu,S.Jurkiewicz,Thefifth and sixth coefficients of the characteristic polynomial of a graph, Electron. Notes Discrete Math....
  • P.R.C. Pereira, L. Markenzon, O. Vernet, A clique-difference encoding scheme for labelled k-path graphs, Discrete Appl. Math. 156 (17), pp....
  • G. M. Prabhu, N. Deo, On the power of a perturbation for testing nonisomorphism of graphs, BIT 24 (3), pp. 302—307, (1984).
  • D. Richards, Finding short cycles in planar graphs using separators, J. Algorithms 7 (3), pp. 382—394, (1986).
  • T. Schank, D. Wagner, Finding, counting and listing all triangles in large graphs, an experimental study, in Experimental and Efficient Algorithms”,...
  • A. J. Schwenk, Computing the characteristic polynomial of a graph, in Graphs and combinatorics, (Proc. Capital Conf., George Washington Univ.,...
  • S. K. Simić, Z. Stanić, The polynomial reconstruction of unicyclic graphs is unique, Linear Multilinear A. 55 (1), pp. 35—43, (2007).
  • 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,...