Let G be a graph and A be a subset of the edges of G. A frame decomposition of G is a pair (G-A,A) such t ha t G-A is connected. A smooth frame decomposition of G is a frame decompo sition satisfying the two conditi...Let G be a graph and A be a subset of the edges of G. A frame decomposition of G is a pair (G-A,A) such t ha t G-A is connected. A smooth frame decomposition of G is a frame decompo sition satisfying the two conditions: (1) Every leaf of G-A has a connected cotree and (2) The set of bridges of G-B(G-A) is A, where B(G-A) is the set of bridges of G-A. An efficient algorithm on finding a smooth frame decompositi on of a graph is provided.展开更多
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.展开更多
Let G be a connected graph of order p, and let γ7(G) denote the domination number of G. Clearly, γ(G) ≤[p/2]. The aim of this paper is to characterize the graphs G that reaches this upper bound. The main results ar...Let G be a connected graph of order p, and let γ7(G) denote the domination number of G. Clearly, γ(G) ≤[p/2]. The aim of this paper is to characterize the graphs G that reaches this upper bound. The main results are as follows: (1) when p is even, γ(G) = p/2 if and only if either G C4 or G is the crown of a connected graph with p/2 vertices; (2) when p is odd, γ(G) = (p-1)/2 if and only if every spanning tree of G is one of the two classes of trees shown in Theorem 3.1.展开更多
文摘Let G be a graph and A be a subset of the edges of G. A frame decomposition of G is a pair (G-A,A) such t ha t G-A is connected. A smooth frame decomposition of G is a frame decompo sition satisfying the two conditions: (1) Every leaf of G-A has a connected cotree and (2) The set of bridges of G-B(G-A) is A, where B(G-A) is the set of bridges of G-A. An efficient algorithm on finding a smooth frame decompositi on of a graph is provided.
基金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.
基金Supported by the National Science Foundation of Jiangxi province.
文摘Let G be a connected graph of order p, and let γ7(G) denote the domination number of G. Clearly, γ(G) ≤[p/2]. The aim of this paper is to characterize the graphs G that reaches this upper bound. The main results are as follows: (1) when p is even, γ(G) = p/2 if and only if either G C4 or G is the crown of a connected graph with p/2 vertices; (2) when p is odd, γ(G) = (p-1)/2 if and only if every spanning tree of G is one of the two classes of trees shown in Theorem 3.1.
