Let G be a nontrivial connected and vertex-colored graph. A subset X of the vertex set of G is called rainbow if any two vertices in X have distinct colors. The graph G is called rainbow vertex-disconnected if for any...Let G be a nontrivial connected and vertex-colored graph. A subset X of the vertex set of G is called rainbow if any two vertices in X have distinct colors. The graph G is called rainbow vertex-disconnected if for any two vertices x and y of G, there exists a vertex subset S of G such that when x and y are nonadjacent, S is rainbow and x and y belong to different components of G-S;whereas when x and y are adjacent, S + x or S + y is rainbow and x and y belong to different components of(G-xy)-S. For a connected graph G, the rainbow vertex-disconnection number of G, denoted by rvd(G), is the minimum number of colors that are needed to make G rainbow vertexdisconnected. In this paper, we characterize all graphs of order n with rainbow vertex-disconnection number k for k ∈ {1, 2, n}, and determine the rainbow vertex-disconnection numbers of some special graphs. Moreover, we study the extremal problems on the number of edges of a connected graph G with order n and rvd(G) = k for given integers k and n with 1 ≤ k ≤ n.展开更多
An edge e of a k-connected graph G is said to be a removable edge if G O e is still k-connected, where G O e denotes the graph obtained from G by the following way： deleting e to get G - e, and for any end vertex of ...An edge e of a k-connected graph G is said to be a removable edge if G O e is still k-connected, where G O e denotes the graph obtained from G by the following way： deleting e to get G - e, and for any end vertex of e with degree k - 1 in G - e, say x, deleting x, and then adding edges between any pair of non-adjacent vertices in NG-e （x）. The existence of removable edges of k-connected graphs and some properties of k-connected graphs have been investigated. In the present paper, we investigate the distribution of removable edges on a spanning tree of a k-connected graph （k ≥ 4）.展开更多
Evidence shows that biological systems are composed of separable functional modules. Identifying protein complexes is essential for understanding the principles of cellular functions. Many methods have been proposed t...Evidence shows that biological systems are composed of separable functional modules. Identifying protein complexes is essential for understanding the principles of cellular functions. Many methods have been proposed to mine protein complexes from protein-protein interaction networks. However, the performances of these algorithms are not good enough since the protein-protein interactions detected from experiments are not complete and have noise. This paper presents an analysis of the topological properties of protein complexes to show that although proteins from the same complex are more highly connected than proteins from different complexes, many protein complexes are not very dense （density ≥0.8）. A method is then given to mine protein complexes that are relatively dense （density ≥0.4）. In the first step, a topology property is used to identify proteins that are probably in a same complex. Then, a possible boundary is calculated based on a minimum vertex cut for the protein complex. The final complex is formed by the proteins within the boundary. The method is validated on a yeast protein-protein interaction network. The results show that this method has better performance in terms of sensitivity and specificity compared with other methods. The functional consistency is also good.展开更多
基金Supported by National Natural Science Foundation of China(Grant Nos.11871034,11531011)Natural Science Foundation of Qinghai(Grant No.2017-ZJ-790)。
文摘Let G be a nontrivial connected and vertex-colored graph. A subset X of the vertex set of G is called rainbow if any two vertices in X have distinct colors. The graph G is called rainbow vertex-disconnected if for any two vertices x and y of G, there exists a vertex subset S of G such that when x and y are nonadjacent, S is rainbow and x and y belong to different components of G-S;whereas when x and y are adjacent, S + x or S + y is rainbow and x and y belong to different components of(G-xy)-S. For a connected graph G, the rainbow vertex-disconnection number of G, denoted by rvd(G), is the minimum number of colors that are needed to make G rainbow vertexdisconnected. In this paper, we characterize all graphs of order n with rainbow vertex-disconnection number k for k ∈ {1, 2, n}, and determine the rainbow vertex-disconnection numbers of some special graphs. Moreover, we study the extremal problems on the number of edges of a connected graph G with order n and rvd(G) = k for given integers k and n with 1 ≤ k ≤ n.
基金Supported by the National Natural Science Foundation of China(No.11171134)the Fujian Province Science Foundation(No.2013J01014,2011J01015,2007F3070)
文摘An edge e of a k-connected graph G is said to be a removable edge if G O e is still k-connected, where G O e denotes the graph obtained from G by the following way： deleting e to get G - e, and for any end vertex of e with degree k - 1 in G - e, say x, deleting x, and then adding edges between any pair of non-adjacent vertices in NG-e （x）. The existence of removable edges of k-connected graphs and some properties of k-connected graphs have been investigated. In the present paper, we investigate the distribution of removable edges on a spanning tree of a k-connected graph （k ≥ 4）.
基金Supported in part by the National Natural Science Foundation of China (Nos.61232001 and 61073036)
文摘Evidence shows that biological systems are composed of separable functional modules. Identifying protein complexes is essential for understanding the principles of cellular functions. Many methods have been proposed to mine protein complexes from protein-protein interaction networks. However, the performances of these algorithms are not good enough since the protein-protein interactions detected from experiments are not complete and have noise. This paper presents an analysis of the topological properties of protein complexes to show that although proteins from the same complex are more highly connected than proteins from different complexes, many protein complexes are not very dense （density ≥0.8）. A method is then given to mine protein complexes that are relatively dense （density ≥0.4）. In the first step, a topology property is used to identify proteins that are probably in a same complex. Then, a possible boundary is calculated based on a minimum vertex cut for the protein complex. The final complex is formed by the proteins within the boundary. The method is validated on a yeast protein-protein interaction network. The results show that this method has better performance in terms of sensitivity and specificity compared with other methods. The functional consistency is also good.
