| 吴叶舟,徐俊明.变更图的直径[J].数学研究及应用,2006,26(3):502~508 |
| 变更图的直径 |
| Diameters of Altered Graphs |
| 投稿时间：2004-12-29 |
| DOI：10.3770/j.issn:1000-341X.2006.03.012 |
| 中文关键词: |
| 英文关键词:diameter altered graph edge addition edge deletion. |
| 基金项目:the National Natural Science Foundation of China (10271114) |
|
| 摘要点击次数: 2724 |
| 全文下载次数: 1482 |
| 中文摘要: |
| |
| 英文摘要: |
| Let $P(t,n)$ and $C(t,n)$ denote the minimum diameter of a connected graph obtained from a single path and a circle of order $n$ plus $t$ extra edges, respectively, and $f(t,k)$ the maximum diameter of a connected graph obtained by deleting $t$ edges from a graph with diameter $k$. This paper shows that for any integers $t\geq4$ and $n\geq5$, $ P(t,n)\leq\frac{n-8}{t+1}+3$, $C(t,n)\leq \frac{n-8}{t+1}+3$ if $t$ is odd and $ C(t,n)\leq \frac{n-7}{t+2}+3$ if $t$ is even; $\left\lceil\frac{n-1}{5}\right\rceil\leq P(4,n)\leq\left\lceil\frac{n+3}{5}\right\rceil$, $\left\lceil\frac{n}{4}\right\rceil-1\leq C(3,n)\leq\left\lceil\frac{n}{4}\right\rceil$; and $f(t,k)\geq (t+1)k-2t+4$ if $k\geq 3$ and is odd, which improves some known results. |
| 查看全文 查看/发表评论 下载PDF阅读器 |
|
|
|
