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 grap...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 ≥4 and n ≥ 5, P（4, n） ≤n-8/t＋1＋ 3, C（t,n）≤n-8/t＋1＋3 if t is odd and C（t,n） ≤n-7/t＋2 ＋3 if t is even; [n-1/5] ≤P（4,n） ≤ [n＋3/5] [n/4]-1≤C（3,n）≤[n/4]; and f（t, k）≥ （t ＋ 1）k - 2t ＋ 4 if k≥3 and is Odd, which improves some known results.展开更多
基金the National Natural Science Foundation of China (10271114)
文摘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 ≥4 and n ≥ 5, P（4, n） ≤n-8/t＋1＋ 3, C（t,n）≤n-8/t＋1＋3 if t is odd and C（t,n） ≤n-7/t＋2 ＋3 if t is even; [n-1/5] ≤P（4,n） ≤ [n＋3/5] [n/4]-1≤C（3,n）≤[n/4]; and f（t, k）≥ （t ＋ 1）k - 2t ＋ 4 if k≥3 and is Odd, which improves some known results.
