Please use this identifier to cite or link to this item:
https://hdl.handle.net/20.500.12008/51365
How to cite
| Title: | Superfluous edges and exponential expansions of De Bruijn and Kautz graphs |
| Authors: | Canale, Eduardo A. Gómez, José |
| Type: | Artículo |
| Keywords: | Large graphs, (Δ,D)-problem, De Bruijn graphs, Kautz graphs, Superfluous edges, Edge-critical graphs |
| Issue Date: | 2004 |
| Abstract: | A new way to expand De Bruijn and Kautz graphs is presented. It consists of deleting superfluous sets of edges (i.e., those whose removal does not increase the diameter) and adding new vertices and new edges preserving the maximum degree and the diameter. The number of vertices added to the Kautz graph, for a fixed maximum degree greater than four, is exponential on the diameter. Tables with lower bounds for the order of superfluous sets of edges and the number of vertices that can be added, are presented. |
| IN: | Discrete Applied Mathematics, vol. 138, no 3, apr. 2004, pp. 303-331. |
| Sponsors: | Con apoyo parcial de CONICYT, Uruguay e Instituto de Matemáticas y Estadística “Prof Laguard.” Facultad. de Ingeniería-UdelaR Trabajo financiado en parte por el Consejo Superior de Investigaciones Científicas (Comisión Interministerial de Ciencia y Tecnología, CICYT) bajo proyectos TIC97-0963 |
| Citation: | Canale, E. y Gómez, J. "Superfluous edges and exponential expansions of De Bruijn and Kautz graphs". Discrete Applied Mathematics [en línea]. 2004, vol. 138, no 3, pp. 303-331. DOI: 10.1016/S0166-218X(03)00463-3. |
| License: | Licencia Creative Commons Atribución - No Comercial - Sin Derivadas (CC - By-NC-ND 4.0) |
| Appears in Collections: | Publicaciones académicas y científicas - IMERL (Instituto de Matemática y Estadística Rafael Laguardia) |
Files in This Item:
| File | Description | Size | Format | ||
|---|---|---|---|---|---|
| CG04.pdf | Versión publicada | 644,18 kB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License
