Pantheon Repositorio Institucional
Recopila, preserva y difundi la producción académica digital en todas las áreas del conocimiento.
Comprende los activos del repositorio, además de tesis y disertaciones en la UFRJ, artículos científicos, libros electrónicos, capítulos de libros y trabajos presentados en eventos para los profesores, investigadores, personal administrativo y estudiantes de maestría y doctorado.
Por favor, use este identificador para citar o enlazar este ítem:
http://hdl.handle.net/11422/1560| Especie: | Relatório |
| Título : | On edge transitivity of directed graphs |
| Autor(es)/Inventor(es): | Szwarcfiter, Jayme Luiz |
| Resumen: | Examinamos transitividade em arestas de grafos direcionados. A classe dos grafos de comparabilidade local é definida como os grafos subjacentes dos dígrafos localmente transitivos em arestas. Estes últimos generalizam orientações transitivas em arestas, enquanto que grafos de comparabilidade local incluem os de comparabilidade, anti-comparabilidade e circulares. Reconhecer grafos de comparabilidade local é NP-completo, contudo, eles constituem diferenças de grafos de comparabilidade. Definimos dimensão de modo a generalizar a de um dígrafo transitivo em arestas. Os grafos conexos de intervalo próprio são caracterizados exatamente como a classe dos de comparabilidade local de dimensão um. Finalmente, uma caracterização dos grafos circulares é apresentada em termos de transitividade em arestas. |
| Resumen: | We examine edge transitivity of directed graphs. The class of local comparability graphs is defined as the underlying graphs of locally edge transitive digraphs. The latter generalize edge transitive orientations, while local comparability graphs include comparability, anti-comparability and circle graphs. Recognizing local comperability graphs is NP-complete, however they are differences of comparability graphs. We define dimension so as to generalize that of an edge transitive digraph. Connect proper interval graphs are characterized as exaclty the class of local comparability graphs of dimension one. Finally, a characterization of circle graphs is given also in terms of edge transitivity. |
| Materia: | Grafos direcionados |
| Materia CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
| Unidade de producción: | Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais |
| Es parte de: | Relatório Técnico NCE |
| Número: | 2690 |
| Fecha de publicación: | 31-oct-1990 |
| País de edición : | Brasil |
| Idioma de publicación: | eng |
| Tipo de acceso : | Acesso Aberto |
| Citación : | SZWARCFITER, J. L. On edge transitivity of directed graphs. Rio de Janeiro: NCE, UFRJ, 1990. 14 p. (Relatório Técnico, 26/90) |
| Aparece en las colecciones: | Relatórios |
Ficheros en este ítem:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| 26_90_000040393.pdf | 1.18 MB | Adobe PDF | Visualizar/Abrir |
Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.