Mostrar el registro sencillo del ítem
dc.contributor.author
Safe, Martin Dario
dc.date.available
2021-02-04T18:55:38Z
dc.date.issued
2020-02-20
dc.identifier.citation
Safe, Martin Dario; Characterization and linear-time detection of minimal obstructions to concave-round graphs and the circular-ones property; John Wiley & Sons Inc; Journal of Graph Theory; 93; 2; 20-2-2020; 268-298
dc.identifier.issn
0364-9024
dc.identifier.uri
http://hdl.handle.net/11336/124849
dc.description.abstract
A graph is concave-round if its vertices can be circularly enumerated so that the closed neighborhood of each vertex is an interval in the enumeration. In this study, we give a minimal forbidden induced subgraph characterization for the class of concave-round graphs, solving a problem posed by Bang-Jensen, Huang, and Yeo [SIAM J. Discrete Math., 13 (2000), pp. 179–193]. In addition, we show that it is possible to find one such forbidden induced subgraph in linear time in any given graph that is not concave-round. As part of the analysis, we obtain characterizations by minimal forbidden submatrices for the circular-ones property for rows and for the circular-ones property for rows and columns and show that, also for both variants of the property, one of the corresponding forbidden submatrices can be found (if present) in any given matrix in linear time. We make some final remarks regarding connections to some classes of circular-arc graphs.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
John Wiley & Sons Inc
dc.rights
info:eu-repo/semantics/restrictedAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.subject
CIRCULAR-ARC GRAPHS
dc.subject
CIRCULAR-ONES PROPERTY
dc.subject
CONCAVE-ROUND GRAPHS
dc.subject
FORBIDDEN INDUCED SUBGRAPHS
dc.subject
FORBIDDEN SUBMATRICES
dc.subject.classification
Matemática Aplicada
dc.subject.classification
Matemáticas
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
dc.title
Characterization and linear-time detection of minimal obstructions to concave-round graphs and the circular-ones property
dc.type
info:eu-repo/semantics/article
dc.type
info:ar-repo/semantics/artículo
dc.type
info:eu-repo/semantics/publishedVersion
dc.date.updated
2020-12-04T14:43:40Z
dc.journal.volume
93
dc.journal.number
2
dc.journal.pagination
268-298
dc.journal.pais
Estados Unidos
dc.description.fil
Fil: Safe, Martin Dario. Universidad Nacional del Sur. Departamento de Matemática; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Bahía Blanca. Instituto de Matemática Bahía Blanca. Universidad Nacional del Sur. Departamento de Matemática. Instituto de Matemática Bahía Blanca; Argentina
dc.journal.title
Journal of Graph Theory
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.22486
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1002/jgt.22486
Archivos asociados