Kragujevac Journal of Mathematics
University of Kragujevac - Faculty of Science

Reconstructing the Characteristic (Permanental) Polynomial of a Digraph from Similar Polynomials of its Arc-Deleted Subgraphs

Download PDF

Authors: V. R. ROSENFELD

DOI: 10.46793/KgJMat2505.741R

Abstract:

Let D = D(V,E) be an arbitrary digraph with the set V of vertices and the set E of arcs ; loops, if any, are considered reduced arcs with the same head and tail. The characteristic polynomial ϕ⁻(D; x) (resp. permanental polynomial (ϕ⁺)) of D is the characteristic (permanental) polynomial of its adjacency matrix A: ϕ(D; x):= det(xI −A) , where I is an identity matrix. A t-arcs-deleted subgraph D_t of D is the digraph D less exactly t arcs (while all n vertices are preserved). Also, let ????_t and R_t⁻(D; x) be the collection (multiset) of all t-arc-deleted subgraphs of D and the sum of the characteristic (permanental) polynomials of all subgraphs from ????_t, respectively. We consider the reconstruction of the characteristic polynomial ϕ⁻(D; x) (permanental polynomial ϕ⁺(D; x)) of D from the polynomial sum R_t⁻(D; x) , t ∈{1, 2,…,m − n + n₀}, where n₀ is the number of zero roots of ϕ⁻(D; x) . Then, we also carry over our reasoning to the case of reconstructing both polynomials of undirected graphs (where edges are deleted).

Keywords:

Characteristic polynomial, permanental polynomial, t-arcs-deleted subgraph.

References:


[1] I. Gutman and D. M. Cvetković, The reconstruction problem for characteristic polynomials of
graphs, Univ. Beograd Publ. Elektrotehn. Fak., Ser. Mat. Fiz. 498–541 (1975), 45–48.
[2] J. A. Bondy and R. L. Hemminger, Graph reconstruction – A survey, J. Graph Theory 1(3)
(1977), 227–268.
[3] W. T. Tutte, The reconstruction problem in graph theory, British Polymer Journal 9(3) (1977),
180–183.
[4] D. Cvetković, Constructing trees with given eigenvalues and angles, Linear Algebra Appl. 105(1)
(1988), 1–8.
[5] S. K. Simić, A note on reconstructing the characteristic polynomial of a graph, Annals of Discrete
Mathematics 51 (1992), 315–319.
[6] D. Cvetković, On the reconstruction of the characteristic polynomial, Discrete Math. 212 (2000),
45–52.
[7] E. M. Hagos, The characteristic polynomial of a graph is reconstructible from the characteristic
polynomials of its vertex-deleted subgraphs and their complements, Electron. J. Comb. 7 (2000),
Article ID #R12, 9 pages.
[8] S. K. Simić and Z. Stanić, The polynomial reconstruction of unicyclic graphs is unique, Linear
Multilinear Algebra 55(1) (2007), 35–43.

[9] H. S. Ramane, S. B. Gudimani, and S. S. Shinde, Signless Laplacian polynomial and characteristic
polynomial of a graph, J. Discrete Math. 2013 (2013), Article ID 105624, 4 pages. https:
//doi.org/10.1155/2013/105624
[10] D. M. Cvetković, M. Doob, and H. Sachs, Spectra of Graph - Theory and Application, VEB
Deutscher Verlag der Wissenschaften, Berlin, 1980. Also, Academic Press, New York, San Fran-
cisco, London, 1980.
[11] G. N. Lin and F. J. Zhang, Characteristic polynomials of directed line graphs, and a class of
directed graphs with the same spectrum, Kexue Tongbao (Chinese) 28(22) (1983), 1348–1350.
[12] H. Zhang, F. Zhang and Q. Huang, On the number of spanning trees and Eulerian tours in
iterated line digraphs, Discrete Appl. Math. 73 (1997), 59–67.
[13] V. R. Rosenfeld, Some spectral properties of the arc-graph, MATCH Commun. Math. Comput.
Chem. 43 (2001), 41–48.
[14] V. R. Rosenfeld, The cycle (circuit) polynomial of a graph with double and triple weights of
edges and cycles, Electron. J. Graph Theory Appl. (EJGTA) 7(1) (2019), 189–205.
[15] V. R. Rosenfeld, A new recursion relation for the characteristic polynomial of a molecular
graph, in: Proceedings of the 5th International Conference on Mathematical and Computational
Chemistry, Kansas City, MO, May 17–21, 1993, 35–36.
[16] V. R. Rosenfeld and I. Gutman, A new recursion relation for the characteristic polynomial of a
molecular graph, Journal of Chemical Information and Modeling 36 (1996), 527–530.