A restricted edge cut is an edge cut of a connected graph whose removal resultsin a disconnected graph without isolated vertices. The size of a minimum restricted edge cutof a graph G is called its restricted edge con...A restricted edge cut is an edge cut of a connected graph whose removal resultsin a disconnected graph without isolated vertices. The size of a minimum restricted edge cutof a graph G is called its restricted edge connectivity, and is denoted by λ′(G). Let ξ(G) bethe minimum edge degree of graph G. It is known that λ′(G) ≤ξ(G) if G contains restrictededge cuts. Graph G is called maximal restricted edge connected if the equality holds in thethe preceding inequality. In this paper, undirected Kautz graph UK(2, n) is proved to bemaximal restricted edge connected if n ≥ 2.展开更多
Inspired by the potential computational capability of 3-Dimensional (3D) DNA structure,this paper presents a graph structure constructed by k-armed (k = 3or 4) branched junction DNA molecules to explore the possibilit...Inspired by the potential computational capability of 3-Dimensional (3D) DNA structure,this paper presents a graph structure constructed by k-armed (k = 3or 4) branched junction DNA molecules to explore the possibility of solving some intractable problems. In the proposed procedure,vertex building blocks consisting of 3,4-armed branched junction molecules are selectively used to form different graph structures. After separating these graph structures by gel electrophoresis,the connec-tivity of this graph can be determined. Furthermore,the amount of potential solutions can be reduced by a theorem of graph theory.展开更多
The decay number of a connected graph is defined to be the minimum number of the components of the cotree of the graph. Upper bounds of the decay numbers of graphs are obtained according to their edge connectivities. ...The decay number of a connected graph is defined to be the minimum number of the components of the cotree of the graph. Upper bounds of the decay numbers of graphs are obtained according to their edge connectivities. All the bounds in this paper are tight.Moreover, for each integer k between one and the upper bound, there are infinitely many graphs with the decay number k.展开更多
A. Kaneko and K. Ota proved that for a minimally （n, λ）-connected graph G, if ｜G｜ = p ≥ 3n - 1, then e（G） ≤ nλ（｜G｜ - n）; and if e（G） = nλ（｜G｜ - n）, then G is isomorphic to the graph Kn^λ,p-n whic...A. Kaneko and K. Ota proved that for a minimally （n, λ）-connected graph G, if ｜G｜ = p ≥ 3n - 1, then e（G） ≤ nλ（｜G｜ - n）; and if e（G） = nλ（｜G｜ - n）, then G is isomorphic to the graph Kn^λ,p-n which is obtained from the complete bipartite graph Kn,p-n by replacing each edge with A multiple edges; if 3n - 1 ≥ ｜G}≥ n ＋ 1, then e（G） ≤λ（｜G｜ ＋ n）^2/8. In this paper, we determine all the minimally （n, λ）-connected graphs with order p and the maximum size λ（p＋n）^2/8 for 3n- 1 ≥ p ≥ n＋ 1 for 3n-1≥p≥n＋1.展开更多
A Theorem is given on the number of passages passing throgh a multiply-connected region,which corrects a wrong conjecture in a former paper of the author.
Let X be a noncompact discrete metric space with bounded geometry. Associated with X are two C*-algebras, the so-called uniform Roe algebra B*(X) and coarse Roe algebra C*(X), which arose from the index theory on nonc...Let X be a noncompact discrete metric space with bounded geometry. Associated with X are two C*-algebras, the so-called uniform Roe algebra B*(X) and coarse Roe algebra C*(X), which arose from the index theory on noncompact complete Riemannian manifolds. In this paper, we describe the quasidiagonality of B*(X) and C*(X) in terms of coarse geometric invariants. Some necessary and suficient conditions are given, which involve the Fredholm index and coarse connectedness of metric spaces.展开更多
基金Supported by the NNSF of China(10271105) Supported by the NSF of Fujian EducationMinistry(JA03145) Supported by the NNSF of China(10071080)
文摘A restricted edge cut is an edge cut of a connected graph whose removal resultsin a disconnected graph without isolated vertices. The size of a minimum restricted edge cutof a graph G is called its restricted edge connectivity, and is denoted by λ′(G). Let ξ(G) bethe minimum edge degree of graph G. It is known that λ′(G) ≤ξ(G) if G contains restrictededge cuts. Graph G is called maximal restricted edge connected if the equality holds in thethe preceding inequality. In this paper, undirected Kautz graph UK(2, n) is proved to bemaximal restricted edge connected if n ≥ 2.
基金Supported by the National Natural Science Foundation of China (No.30370356 and No.60574041).
文摘Inspired by the potential computational capability of 3-Dimensional (3D) DNA structure,this paper presents a graph structure constructed by k-armed (k = 3or 4) branched junction DNA molecules to explore the possibility of solving some intractable problems. In the proposed procedure,vertex building blocks consisting of 3,4-armed branched junction molecules are selectively used to form different graph structures. After separating these graph structures by gel electrophoresis,the connec-tivity of this graph can be determined. Furthermore,the amount of potential solutions can be reduced by a theorem of graph theory.
基金Supported by the NSFC(10201022)Supported by the NSFCBJ(1012003)
文摘The decay number of a connected graph is defined to be the minimum number of the components of the cotree of the graph. Upper bounds of the decay numbers of graphs are obtained according to their edge connectivities. All the bounds in this paper are tight.Moreover, for each integer k between one and the upper bound, there are infinitely many graphs with the decay number k.
基金This research is supported by the National Natural Science Foundation of China.
文摘A. Kaneko and K. Ota proved that for a minimally （n, λ）-connected graph G, if ｜G｜ = p ≥ 3n - 1, then e（G） ≤ nλ（｜G｜ - n）; and if e（G） = nλ（｜G｜ - n）, then G is isomorphic to the graph Kn^λ,p-n which is obtained from the complete bipartite graph Kn,p-n by replacing each edge with A multiple edges; if 3n - 1 ≥ ｜G}≥ n ＋ 1, then e（G） ≤λ（｜G｜ ＋ n）^2/8. In this paper, we determine all the minimally （n, λ）-connected graphs with order p and the maximum size λ（p＋n）^2/8 for 3n- 1 ≥ p ≥ n＋ 1 for 3n-1≥p≥n＋1.
文摘A Theorem is given on the number of passages passing throgh a multiply-connected region,which corrects a wrong conjecture in a former paper of the author.
基金supported by National Natural Science Foundation of China (Grant No. 10871140)
文摘Let X be a noncompact discrete metric space with bounded geometry. Associated with X are two C*-algebras, the so-called uniform Roe algebra B*(X) and coarse Roe algebra C*(X), which arose from the index theory on noncompact complete Riemannian manifolds. In this paper, we describe the quasidiagonality of B*(X) and C*(X) in terms of coarse geometric invariants. Some necessary and suficient conditions are given, which involve the Fredholm index and coarse connectedness of metric spaces.
