RT info:eu-repo/semantics/article
T1 Structural and spectral properties of minimal strong digraphs
A1 Marijuán López, Carlos
A1 García López, Jesús
A1 Pozo Coronado, Luis Miguel
K1 Digraphs
K1 Dígrafos
K1 Trees
K1 Árboles
K1 Characteristic polynomial
K1 Polinomio característico
AB In this article, we focus on structural and spectral properties of minimal strongdigraphs (MSDs). We carry out a comparative study of properties of MSDs versustrees. This analysis includes two new properties. The first one gives bounds onthe coefficients of characteristic polynomials of trees (double directed trees), andconjectures the generalization of these bounds to MSDs. As a particular case, weprove that the independent coemcient of the characteristic polynomial of a tree oran MSD must be — 1, 0 or 1. For trees, this fact means that a tree has at most oneperfect matching; for MSDs, it means that an MSD has at most one covering bydisjoint cycles. The property states that every MSD can be decomposed in a rootedspanning tree and a forest of reversed rooted trees, as factors. In our opinión, theanalogies described suppose a significative change in the traditional point of viewabout this class of digraphs.
PB Elsevier
SN 1571-0653
YR 2016
FD 2016
LK http://uvadoc.uva.es/handle/10324/40734
UL http://uvadoc.uva.es/handle/10324/40734
LA eng
NO Electronic Notes in Discrete Mathematics, 2016, vol. 54. p. 91-96
NO Producción Científica
DS UVaDOC
RD 17-may-2024