No label defined (Q3834069)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4110714
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4110714 |
Statements
1988
0 references
vulnerability
0 references
digraph
0 references
diameter
0 references
Kautz graphs
0 references
0.8433433175086975
0 references
0.8409397006034851
0 references
0.8402954936027527
0 references
0.8241485953330994
0 references
[For the entire collection see Zbl 0665.00002.] If v is a vertex of a digraph G, then \(\Gamma^+(v)\) and \(\Gamma^-(v)\) denote the out-and-in-neighbourhood of v, respectively. If G is a digraph, then UG the underlying graph of G is the graph obtained from G be deleting the orientation of every arc of G and replacing multiple edges with single edge. The authors show that if G is a strongly connected digraph such that for every pair of vertices x and y, \(| \Gamma^+(x)\cap \Gamma^+(y)| \neq 1\) and \(| \Gamma^-(x)\cap \Gamma^-(y)| \neq 1\), then the diameter of UG-v is at most the diameter of G for all \(v\in V(G)\). It is then shown that in the case of Kautz graphs of diameter D and maximum degree 2d-1 (i) the deletion of one vertex does not change the diameter, (ii) the deletion of up to 2d-5 vertices increases the diameter by at most 1 and (iii) the deletion of at most 2d-2 vertices increases the diameter by at most 2.
0 references