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
      [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
      0 references
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references