On the characteristic polynomial of the power of a path.
Keywords: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 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.
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,Theﬁfth and sixth coeﬃcients 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-diﬀerence 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 Eﬃcient 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 coeﬃcients of unicyclic graphs with the number of leaves and girth, Appl. Anal. Discrete Math. 8 (2), pp. 330—345, (2014).
How to Cite
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.