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
15 April 2005
0 references
diameter bounds
0 references
edge addition
0 references
edge deletion
0 references
0.8933742642402649
0 references
0.8818114399909973
0 references
0.8678432703018188
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