On the characteristic polynomial of the power of a path.

Authors

  • 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.

Keywords:

Power of a path, 4-cycles, Characteristic coefficients

Abstract

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.

Author Biographies

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.

References

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. Notes Comput. Sc., Vol. 1335, Springer-Verlag, Berlin, pp. 15-24, (1997).

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 Math. J. 63 (138), pp. 701—720, (2013).

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).

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

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 Janeiro, (2012).

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. 11, pp. 201—208, (2002).

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).

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”, Lect. Notes Comput. Sc., Vol. 3503, pp. 606—609, Springer- Verlag, Berlin, (2005).

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).

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, (2014).

Published

2017-10-20

How to Cite

[1]
B. Malajovich, N. Abreu, and L. Markenzon, “On the characteristic polynomial of the power of a path.”, Proyecciones (Antofagasta, On line), vol. 36, no. 3, pp. 529-543, Oct. 2017.

Issue

Section

Artículos