On rooted directed path graphs
An asteroidal triple is a stable set of three vertices such that each pair is connected by a path avoiding the neighborhood of the third vertex. An asteroidal quadruple is a stable set of four vertices such that any three of them is an asteroidal triple. Two non adjacent vertices are linked by a spe...
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Articulo |
| Lenguaje: | Inglés |
| Publicado: |
2016
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/95936 https://ri.conicet.gov.ar/11336/55216 http://inmabb.criba.edu.ar/revuma/pdf/v57n1/v57n1a09.pdf http://inmabb.criba.edu.ar/revuma/revuma.php?p=toc/vol57 |
| Aporte de: |
| id |
I19-R120-10915-95936 |
|---|---|
| record_format |
dspace |
| institution |
Universidad Nacional de La Plata |
| institution_str |
I-19 |
| repository_str |
R-120 |
| collection |
SEDICI (UNLP) |
| language |
Inglés |
| topic |
Matemática Path Asteroidals |
| spellingShingle |
Matemática Path Asteroidals Tondato, Silvia Beatriz Gutiérrez, Marisa On rooted directed path graphs |
| topic_facet |
Matemática Path Asteroidals |
| description |
An asteroidal triple is a stable set of three vertices such that each pair is connected by a path avoiding the neighborhood of the third vertex. An asteroidal quadruple is a stable set of four vertices such that any three of them is an asteroidal triple. Two non adjacent vertices are linked by a special connection if either they have a common neighbor or they are the endpoints of two vertex-disjoint chordless paths satisfying certain technical conditions. Cameron, Ho`ang, and L´evˆeque [DIMAP Workshop on Algorithmic Graph Theory, 67–74, Electron. Notes Discrete Math., 32, Elsevier, 2009] proved that if a pair of non adjacent vertices are linked by a special connection then in any directed path model T the subpaths of T corresponding to the vertices forming the special connection have to overlap and they force T to be completely directed in one direction between these vertices. Special connections along with the concept of asteroidal quadruple play an important role to study rooted directed path graphs, which are the intersection graphs of directed paths in a rooted directed tree. In this work we define other special connections; these special connections along with the ones defined by Cameron, Ho`ang, and L´evˆeque are nine in total, and we prove that every one forces T to be completely directed in one direction between these vertices. Also, we give a characterization of rooted directed path graphs whose rooted models cannot be rooted on a bold maximal clique. As a by-product of our result, we build new forbidden induced subgraphs for rooted directed path graphs. |
| format |
Articulo Articulo |
| author |
Tondato, Silvia Beatriz Gutiérrez, Marisa |
| author_facet |
Tondato, Silvia Beatriz Gutiérrez, Marisa |
| author_sort |
Tondato, Silvia Beatriz |
| title |
On rooted directed path graphs |
| title_short |
On rooted directed path graphs |
| title_full |
On rooted directed path graphs |
| title_fullStr |
On rooted directed path graphs |
| title_full_unstemmed |
On rooted directed path graphs |
| title_sort |
on rooted directed path graphs |
| publishDate |
2016 |
| url |
http://sedici.unlp.edu.ar/handle/10915/95936 https://ri.conicet.gov.ar/11336/55216 http://inmabb.criba.edu.ar/revuma/pdf/v57n1/v57n1a09.pdf http://inmabb.criba.edu.ar/revuma/revuma.php?p=toc/vol57 |
| work_keys_str_mv |
AT tondatosilviabeatriz onrooteddirectedpathgraphs AT gutierrezmarisa onrooteddirectedpathgraphs |
| bdutipo_str |
Repositorios |
| _version_ |
1764820493387431939 |