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/1078| Especie: | Relatório |
| Título : | On clique convergent graphs |
| Autor(es)/Inventor(es): | Bornstein, Claudson Ferreira Szwarcfiter, Jayme Luiz |
| Resumen: | Um grafo G é convergente quando existe um inteiro finito n≥0, tal que o n-ésimo grafo clique iterado Kn(G) possui um único vértice. O menor n que satisfaz esta condição é o índice de G. A deficiência Helly de um grafo convergente é o menor inteiro h tal que Kʰ(G) é clique Helly, ou seja. suas cliques maximais satisfazem a propriedade Helly. Bandelt e Prisner provaram que a deficiência Helly de um grafo cordal é no máximo um e indagaram acerca da existência de algum grafo cuja deficiência Helly excede a diferença entre seu índice e diâmetro por mais de um. Neste artigo é fornecida uma resposta afirmativa a esta questão. Para um inteiro arbitrário n, é exibido um grafo cuja deficiência Helly excede em n unidades a diferença entre seu índice e diâmetro. |
| Resumen: | A graph G is convergent when there is some finite integer n≥0, such that the n-th iterated clique graph Kn (G) has only one vertex. The smallest such n is the index of G. The Helly defect of a convergent graph is the smallest h such that Kʰ(G) is clique Helly, that is, its maximal cliques satisfy the Helly property. Bandelt and Prisner proved that the Helly defect of a chordal graph is at most one and asked whether there is a graph whose Helly defect exceeds the difference of its index and diameter by more than one. In the present paper an affirmative anwer to the question is given. For any arbitrary finite integer n, it is exhibited a graph, the Helly defect of which exceeds by n the difference of its index and diameter. |
| Materia: | Graphs teory Deficiência Helly Teoria dos grafos |
| Materia CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::MATEMATICA |
| Unidade de producción: | Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais |
| Es parte de: | Relatório Técnico NCE |
| Número: | 0592 |
| Fecha de publicación: | 26-oct-1992 |
| País de edición : | Brasil |
| Idioma de publicación: | eng |
| Tipo de acceso : | Acesso Aberto |
| Citación : | BORNSTEIN, C. F.; SZWARCFITER, J. L. On clique convergent graphs. Rio de Janeiro: NCE, UFRJ, 1992. 12 p. (Relatório Técnico, 05/92) |
| Aparece en las colecciones: | Relatórios |
Ficheros en este ítem:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| 05_92_000040433.pdf | 783.44 kB | 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.