A graph G is called k-critically n-connected or simply (n, k)-graph, (n≥k≥1), if for all V′(?)V(G) with |V′|≤k, we have k(G-V′)=n-|V′|, where k(G) denotes the connectivity of G. This notion is introduced by Mau...A graph G is called k-critically n-connected or simply (n, k)-graph, (n≥k≥1), if for all V′(?)V(G) with |V′|≤k, we have k(G-V′)=n-|V′|, where k(G) denotes the connectivity of G. This notion is introduced by Maurer and Slater in (1)The following conjecture on a (n, k)-graph is proposed.展开更多
A connected graph G is said to be a factor-critical graph if G - v has a perfect matching for every vertex v of G. In this paper, the 2-connected factor-critical graph G which has exactly ｜E（G）｜＋ 1 maximum matchi...A connected graph G is said to be a factor-critical graph if G - v has a perfect matching for every vertex v of G. In this paper, the 2-connected factor-critical graph G which has exactly ｜E（G）｜＋ 1 maximum matchings is characterized.展开更多
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.展开更多
文摘A graph G is called k-critically n-connected or simply (n, k)-graph, (n≥k≥1), if for all V′(?)V(G) with |V′|≤k, we have k(G-V′)=n-|V′|, where k(G) denotes the connectivity of G. This notion is introduced by Maurer and Slater in (1)The following conjecture on a (n, k)-graph is proposed.
基金supported by the National Natural Science Foundation of China(No.11551003)the Scientific research fund of the Science and Technology Program of Guangzhou,China(No.201510010265)the Qinghai Province Natural Science Foundation(No.2015-ZJ-911)
文摘A connected graph G is said to be a factor-critical graph if G - v has a perfect matching for every vertex v of G. In this paper, the 2-connected factor-critical graph G which has exactly ｜E（G）｜＋ 1 maximum matchings is characterized.
基金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.
基金Project Supported by Natural Science Foundation of Guangxi(No.0640063)Science and Research Foundation of Guangxi Provincial Education Department(Grant No.[2005]47).
