2024-03-29T11:27:24Zhttp://uvadoc.uva.es/oai/requestoai:uvadoc.uva.es:10324/407342021-06-24T07:41:26Zcom_10324_32197com_10324_952com_10324_894col_10324_32199
Structural and spectral properties of minimal strong digraphs
Marijuán López, Carlos
García López, Jesús
Pozo Coronado, Luis Miguel
Digraphs
Dígrafos
Trees
Árboles
Characteristic polynomial
Polinomio característico
Producción Científica
In this article, we focus on structural and spectral properties of minimal strong
digraphs (MSDs). We carry out a comparative study of properties of MSDs versus
trees. This analysis includes two new properties. The first one gives bounds on
the coefficients of characteristic polynomials of trees (double directed trees), and
conjectures the generalization of these bounds to MSDs. As a particular case, we
prove that the independent coemcient of the characteristic polynomial of a tree or
an MSD must be — 1, 0 or 1. For trees, this fact means that a tree has at most one
perfect matching; for MSDs, it means that an MSD has at most one covering by
disjoint cycles. The property states that every MSD can be decomposed in a rooted
spanning tree and a forest of reversed rooted trees, as factors. In our opinión, the
analogies described suppose a significative change in the traditional point of view
about this class of digraphs.
Ministerio de Economía, Industria y Competitividad (project MTM2015-65764-C3-1-P)
2020-04-13T13:11:53Z
2020-04-13T13:11:53Z
2016
info:eu-repo/semantics/article
info:eu-repo/semantics/acceptedVersion
Electronic Notes in Discrete Mathematics, 2016, vol. 54. p. 91-96
1571-0653
http://uvadoc.uva.es/handle/10324/40734
10.1016/j.endm.2016.09.017
eng
https://www.sciencedirect.com/science/article/abs/pii/S1571065316301111
Attribution-NonCommercial-NoDerivatives 4.0 Internacional
info:eu-repo/semantics/openAccess
http://creativecommons.org/licenses/by-nc-nd/4.0/
© 2016 Elsevier
application/pdf
Elsevier
https://uvadoc.uva.es/bitstream/10324/40734/4/Structural-and-spectral-properties.pdf.jpg
Hispana
TEXT
http://creativecommons.org/licenses/by-nc-nd/4.0/
UVaDOC. Repositorio Documental de la Universidad de Valladolid
http://uvadoc.uva.es/handle/10324/40734