Minimal strong digraphs

García Lopez de Lacalle, Jesús and Marijuán López, Carlos (2012). Minimal strong digraphs. "Discrete Mathematics", v. 312 (n. 4); pp. 737-744. ISSN 0012-365X. https://doi.org/10.1016/j.disc.2011.11.010.

Description

Title: Minimal strong digraphs
Author/s:
  • García Lopez de Lacalle, Jesús
  • Marijuán López, Carlos
Item Type: Article
Título de Revista/Publicación: Discrete Mathematics
Date: 28 February 2012
ISSN: 0012-365X
Volume: 312
Subjects:
Freetext Keywords: Minimal strong digraphs; Strong digraphs; Isospectral strong digraphs
Faculty: E.U. de Informática (UPM)
Department: Matemática Aplicada
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (962kB) | Preview

Abstract

We introduce adequate concepts of expansion of a digraph to obtain a sequential construction of minimal strong digraphs. We obtain a characterization of the class of minimal strong digraphs whose expansion preserves the property of minimality. We prove that every minimal strong digraph of order nmayor que=2 is the expansion of a minimal strong digraph of order n-1 and we give sequentially generative procedures for the constructive characterization of the classes of minimal strong digraphs. Finally we describe algorithms to compute unlabeled minimal strong digraphs and their isospectral classes.

More information

Item ID: 22680
DC Identifier: http://oa.upm.es/22680/
OAI Identifier: oai:oa.upm.es:22680
DOI: 10.1016/j.disc.2011.11.010
Official URL: http://www.sciencedirect.com/science/article/pii/S0012365X11005073
Deposited by: Memoria Investigacion
Deposited on: 04 Apr 2014 14:45
Last Modified: 21 Apr 2016 17:40
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM