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.展开更多
Constrained Delaunay triangulated irregular network is one kind of dynamic data structures used in geosciences. The research on point and edges insertion in CD-TIN is the basis of its application. Comparing with the a...Constrained Delaunay triangulated irregular network is one kind of dynamic data structures used in geosciences. The research on point and edges insertion in CD-TIN is the basis of its application. Comparing with the algorithms of points and constrained edge insertion, there are very a few researches on constrained edge deletion in CD-TIN. Based on the analysis of the polymorphism of constrained edge, virtual points are used to describe the intersection of constrained edges. A new algorithm is presented, called as influence domain retriangulating for virtual point （IDRVP）, to delete constrained edges with virtual points. The algorithm is complete in topology. Finally, the algorithm is tested by some applications cases.展开更多
We propose a new expected value of rooted graph in this article,that is, when G is a rooted graph that each vertex may independently succeed with probability p when catastrophic thing happened, we consider the expecte...We propose a new expected value of rooted graph in this article,that is, when G is a rooted graph that each vertex may independently succeed with probability p when catastrophic thing happened, we consider the expected number of edges in the operational component of G which containing the root. And we get a very important and useful compute formula which is called deletion-contraction edge formula. By using this formula, we get the computational formulas of expected value for some special graphs. We also discuss the mean of expected value when parameter p has certain prior distribution. Finally, we propose mean-variance optimality when rooted graph has the equilibrium point which has larger mean and smaller variance.展开更多
基金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.
文摘Constrained Delaunay triangulated irregular network is one kind of dynamic data structures used in geosciences. The research on point and edges insertion in CD-TIN is the basis of its application. Comparing with the algorithms of points and constrained edge insertion, there are very a few researches on constrained edge deletion in CD-TIN. Based on the analysis of the polymorphism of constrained edge, virtual points are used to describe the intersection of constrained edges. A new algorithm is presented, called as influence domain retriangulating for virtual point （IDRVP）, to delete constrained edges with virtual points. The algorithm is complete in topology. Finally, the algorithm is tested by some applications cases.
基金Supported by the National Natural Science Foundation of China(No:6087206011071158)+1 种基金the Science Foundation of Shanghai Education Committee(No:12ZZ193)the Natural Science Foundation of Shanghai city(No:12ZR1421000)
文摘We propose a new expected value of rooted graph in this article,that is, when G is a rooted graph that each vertex may independently succeed with probability p when catastrophic thing happened, we consider the expected number of edges in the operational component of G which containing the root. And we get a very important and useful compute formula which is called deletion-contraction edge formula. By using this formula, we get the computational formulas of expected value for some special graphs. We also discuss the mean of expected value when parameter p has certain prior distribution. Finally, we propose mean-variance optimality when rooted graph has the equilibrium point which has larger mean and smaller variance.
