Structural and spectral properties of minimal strong digraphs

Garcia López de Lacalle, Jesús; Pozo Coronado, Luis Miguel y Marijuán López, Carlos (2016). Structural and spectral properties of minimal strong digraphs. "Electronic notes in discrete mathematics", v. 54 ; pp. 91-96. ISSN 1571-0653. https://doi.org/10.1016/j.endm.2016.09.017.

Descripción

Título: Structural and spectral properties of minimal strong digraphs
Autor/es:
  • Garcia López de Lacalle, Jesús
  • Pozo Coronado, Luis Miguel
  • Marijuán López, Carlos
Tipo de Documento: Artículo
Título de Revista/Publicación: Electronic notes in discrete mathematics
Fecha: Octubre 2016
Volumen: 54
Materias:
Palabras Clave Informales: Keywords: Minimal strong digraphs, trees, characteristic polynomial, spanning tree.
Escuela: E.T.S.I. de Sistemas Informáticos (UPM)
Departamento: Matemática Aplicada a las Tecnologías de la Información y las Comunicaciones
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (986kB) | Vista Previa

Resumen

EL artículo se centra en las propiedades estructurales y espectrales de los digrafos fuertemente conexos minimales, mediante la comparación de sus propiedades con las propiedades de los árboles. Este análisis incluye dos propiedades nuevas la primera da cotas para los coeficientes de los polinomios característicos de los árboles, y conjetura que esas cotas se generalizan para digrafos fuertemente conexos minimales. Como caso particular, probamos que el término independiente de tale polinomios debe ser -1, 0 o 1. La segunda establece que todo digrafo fuertemente conexo minimal puede descomponerse en un arbol generador dirigido con raíz, y un bosque de árboles con raíz inversos. En nuestra opinión, las analogías descritas entre árboles y digrafos fuertemente conexos minimales suponen un cambio significativo sobre el punto de vista acerca de estos últimos. Abstract 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.

Proyectos asociados

TipoCódigoAcrónimoResponsableTítulo
Gobierno de EspañaMTM2015-65764-C3-1-PSin especificarSin especificarSin especificar

Más información

ID de Registro: 46081
Identificador DC: http://oa.upm.es/46081/
Identificador OAI: oai:oa.upm.es:46081
Identificador DOI: 10.1016/j.endm.2016.09.017
URL Oficial: http://www.sciencedirect.com/science/article/pii/S1571065316301111
Depositado por: Memoria Investigacion
Depositado el: 29 May 2017 18:51
Ultima Modificación: 29 May 2017 20:11
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM