Disjoint paths of bounded length in large generalized cycles
type: Item
instance of: scholarly article
title: Disjoint paths of bounded length in large generalized cycles
zbMATH Open document ID: 0943.05052
DOI: 10.1016/S0012-365X(99)90075-4
author: Carles Padró
author: Daniela Ferrero
published in: Discrete Mathematics
publication date: 2000-09-05T00:00:00Z
review text: Graphs (both directed and undirected) are used to model interconnection networks. From this viewpoint, the fault diameter of a graph is related to the fault tolerance of the corresponding network. A generalized \(p\)-cycle is a digraph whose vertex set has a partition into \(p\) parts that can be cyclically ordered in such a way that a vertex is adjacent only to vertices belonging to the next part. A lower bound is found for the fault diameter of a generalized \(p\)-cycle. Both the fault diameter and a related parameter (the wide diameter) are also calculated for two extremal families of generalized \(p\)-cycles, namely \(\text{BGC}(p,d,d^p)\) and \(\text{KGC}(p,d,d^{p+ k}+ d^p)\).
reviewed by: Raffaele Scapellato
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1322018
zbMATH Keywords: fault diameter
zbMATH Keywords: fault tolerance
zbMATH Keywords: digraph
zbMATH Keywords: generalized \(p\)-cycle
MaRDI profile type: Publication
cites work: Q3818315
cites work: On the diameter vulnerability of Kautz digraphs
cites work: Maximally connected digraphs
cites work: Dense bipartite digraphs
cites work: Line Digraph Iterations and the (d, k) Digraph Problem
cites work: Q5616727
cites work: Large generalized cycles
cites work: On the \(k\)-diameter of \(k\)-regular \(k\)-connected graphs
cites work: Design to Minimize Diameter on Building-Block Network
cites work: A Design for Directed Graphs with Minimum Diameter
cites work: Diameter vulnerability of iterated line digraphs
cites work: Diameter-vulnerability of large bipartite digraphs
full work available at URL: s0012-365x(99)90075-4
OpenAlex ID: W4253656615
description: scientific article; zbMATH DE number 1322018