To access the full text documents, please follow this link: http://hdl.handle.net/2117/13303

On large (delta, D, D, 1)-graphs
Gómez Martí, José; Fàbrega Canudas, José; Andrés Yebra, José Luis
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV
Concern about fault tolerance in the design of interconnection networks has aroused interest in finding large graphs such that the subgraphs obtained by deleting any set of up to s vertices have small diameter. Clearly, 1 ≤ S ≤ Δ− 1, where Δ is the maximum degree of the graph. Graphs of maximum degree Δ, diameter ≤ D and such that the graphs obtained by deletion of up to svertices have diameter ≤ D' are known as (Δ,D,D',s)-graphs. This article considers the case S = 1 and D = D'. In other words, it deals with the search for large graphs whose diameter does not increase after deleting one vertex. The article also contains an updated table of the largest known (Δ,D,D,1)-graphs, in which most of the entries correspond to the constructions put forward in this article.
2012-05-11
Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica aplicada a les ciències
Interconnection networks
Large graphs
Compound graphs
Product of graphs
Vulnerability
(Δ,D,D', s)-problem
Grafs, Teoria de -- Informàtica
Restricted access - publisher's policy
Article
         

Show full item record

Related documents

Other documents of the same author

Fiol Mora, Miquel Àngel; Fàbrega Canudas, José; Yebra, José Luis A.
Fàbrega Canudas, José; Martí Farré, Jaume; Muñoz López, Francisco Javier
 

Coordination

 

Supporters