Mostrar el registro sencillo del ítem

dc.contributor.author
de Caria, Pablo Jesús  
dc.date.available
2023-02-06T14:34:58Z  
dc.date.issued
2022-12  
dc.identifier.citation
de Caria, Pablo Jesús; Intersection graphs of induced subtrees of any graph and a generalization of chordal graphs; Elsevier Science; Discrete Applied Mathematics; 323; 12-2022; 171-183  
dc.identifier.issn
0166-218X  
dc.identifier.uri
http://hdl.handle.net/11336/186989  
dc.description.abstract
This paper is inspired by the well known characterization of chordal graphs as the intersection graphs of subtrees of a tree. We consider families of induced trees of any graph and we prove that their recognition is NP-Complete. A consequence of this fact is that the concept of clique tree of chordal graphs cannot be widely generalized. Finally, we consider the fact that every graph is the intersection graph of induced trees of a bipartite graph and we characterize some classes that arise when we impose restrictions on the host bipartite graph.  
dc.format
application/pdf  
dc.language.iso
eng  
dc.publisher
Elsevier Science  
dc.rights
info:eu-repo/semantics/restrictedAccess  
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/  
dc.subject
BIPARTITE GRAPH  
dc.subject
CHORDAL GRAPH  
dc.subject
CLIQUE REPRESENTATION  
dc.subject
CLIQUE TREE  
dc.subject
INTERSECTION GRAPH  
dc.subject
SUBTREE  
dc.subject.classification
Matemática Pura  
dc.subject.classification
Matemáticas  
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS  
dc.title
Intersection graphs of induced subtrees of any graph and a generalization of chordal graphs  
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
2022-01-06T15:00:56Z  
dc.journal.volume
323  
dc.journal.pagination
171-183  
dc.journal.pais
Países Bajos  
dc.journal.ciudad
Amsterdam  
dc.description.fil
Fil: de Caria, Pablo Jesús. Universidad Nacional de La Plata. Facultad de Ciencias Exactas. Departamento de Matemáticas; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - La Plata; Argentina  
dc.journal.title
Discrete Applied Mathematics  
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.dam.2021.04.006  
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S0166218X21001487  

Archivos asociados
Tamaño: 1.148Mb
Formato: PDF
.