No label defined (Q4669880)

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 2157296
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 2157296

      Statements

      0 references
      0 references
      15 April 2005
      0 references
      diameter bounds
      0 references
      edge addition
      0 references
      edge deletion
      0 references
      Let \(F(t,d)\) [\(P(t,d)\)] denote the minimum diameter of an altered graph obtained by adding \(t\) extra edges to a graph [a path, respectively] with diameter \(d\). Further, let \(f(t,d)\) denote the maximum diameter of a connected graph obtained after deleting \(t\) edges from a graph with diameter \(d\). There are known some bounds on these invariants [see \textit{A. A. Schoone, H. L. Bodlaender} and \textit{J. van Leeuwen}, J. Graph Theory 11, 409--427 (1987; Zbl 0646.05038)]. In this paper it is proved that \(F(t,f(t,d))\leq d\leq f(t,F(t,d))\), \(\frac{d}{t+1}\leq F(t,d)=P(t,d)\leq \frac{d-2}{t+1}+3\), \(F(t,d)\leq \frac{d}{t}+1\) if \(d\) is sufficiently large, \(P(t,(2k-1)(t+1)+1)=2k\), \(\frac{d}{t+1}\leq P(t,d)\leq \frac{d}{t+1}+1\) for \(t=4\) or 5 and \(d\geq 4\).
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references