Special asteroidal quadruple on directed path graph non rooted path graph

An asteroidal triple in a graph G is a set of three non- adjacent vertices such that for any two of them there exists a path be- tween them that does not intersect the neighborhood of the third. Special asteroidal triple in a graph G is an asteroidal triple such that each pair is linked by a special...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Gutierrez, M., Tondato, Silvia Beatriz
Formato: Objeto de conferencia Resumen
Lenguaje:Inglés
Publicado: 2013
Materias:
Ciencias Informáticas
Asteroidal quadruples
Forbidden subgraphs
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/94552
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-94552
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Informáticas
Asteroidal quadruples
Forbidden subgraphs
spellingShingle Ciencias Informáticas
Asteroidal quadruples
Forbidden subgraphs
Gutierrez, M.
Tondato, Silvia Beatriz
Special asteroidal quadruple on directed path graph non rooted path graph
topic_facet Ciencias Informáticas
Asteroidal quadruples
Forbidden subgraphs
description An asteroidal triple in a graph G is a set of three non- adjacent vertices such that for any two of them there exists a path be- tween them that does not intersect the neighborhood of the third. Special asteroidal triple in a graph G is an asteroidal triple such that each pair is linked by a special connection. A special asteroidal triples play a central role in a characterization of directed path graphs by Cameron, Hoáng and Lévêque. They also introduce a related notion of asteroidal quadru- ple and conjecture a characterization of rooted path graphs. In its original form this conjecture is not complete, still in leafage four, as was showed in. But, as suggested by the conjecture, a characterization by forbidding particular types of asteroidal quadruples may hold. We prove that the conjecture in the original form is true on directed path graphs with leafage four having two minimal separators with multiplicity two. Thus we build the family of forbidden subgraphs in this case.
format Objeto de conferencia
Resumen
author Gutierrez, M.
Tondato, Silvia Beatriz
author_facet Gutierrez, M.
Tondato, Silvia Beatriz
author_sort Gutierrez, M.
title Special asteroidal quadruple on directed path graph non rooted path graph
title_short Special asteroidal quadruple on directed path graph non rooted path graph
title_full Special asteroidal quadruple on directed path graph non rooted path graph
title_fullStr Special asteroidal quadruple on directed path graph non rooted path graph
title_full_unstemmed Special asteroidal quadruple on directed path graph non rooted path graph
title_sort special asteroidal quadruple on directed path graph non rooted path graph
publishDate 2013
url http://sedici.unlp.edu.ar/handle/10915/94552
work_keys_str_mv AT gutierrezm specialasteroidalquadrupleondirectedpathgraphnonrootedpathgraph
AT tondatosilviabeatriz specialasteroidalquadrupleondirectedpathgraphnonrootedpathgraph
bdutipo_str Repositorios
_version_ 1764820491552423936

Ejemplares similares