摘要
Let φ（G）, κ（G）, α（G）, χ（G）, cl（G）, diam（G） denote the number of perfect matchings, connectivity, independence number, chromatic number, clique number and diameter of a graph G, respectively. In this note, by constructing some extremal graphs, the following extremal problems are solved： 1. max {φ（G）： ｜V（G）｜ = 2n, κ（G）≤ k} = k[（2n - 3）!!], 2. max{φ（G）： ｜V（G）｜ = 2n,α（G） ≥ k} =[∏ i=0^k-1 （2n - k-i]（2n - 2k - 1）!!], 3. max{φ（G）： ｜V（G）｜=2n, χ（G） ≤ k} =φ（Tk,2n） Tk,2n is the Turán graph, that is a complete k-partitc graph on 2n vertices in which all parts are as equal in size as possible, 4. max{φ（G）： ｜V（G）｜ = 2n, cl（G） = 2} = n!, 5. max{φ（G）： ｜V（G）｜ = 2n, diam（G） ≥〉 2} = （2n - 2）（2n - 3）[（2n - 5）!!], max{φ（G）： ｜V（G）｜ = 2n, diam（G） ≥ 3} = （n - 1）^2[（2n - 5）!!].
Let φ（G）, κ（G）, α（G）, χ（G）, cl（G）, diam（G） denote the number of perfect matchings, connectivity, independence number, chromatic number, clique number and diameter of a graph G, respectively. In this note, by constructing some extremal graphs, the following extremal problems are solved： 1. max {φ（G）： ｜V（G）｜ = 2n, κ（G）≤ k} = k[（2n - 3）!!], 2. max{φ（G）： ｜V（G）｜ = 2n,α（G） ≥ k} =[∏ i=0^k-1 （2n - k-i]（2n - 2k - 1）!!], 3. max{φ（G）： ｜V（G）｜=2n, χ（G） ≤ k} =φ（Tk,2n） Tk,2n is the Turán graph, that is a complete k-partitc graph on 2n vertices in which all parts are as equal in size as possible, 4. max{φ（G）： ｜V（G）｜ = 2n, cl（G） = 2} = n!, 5. max{φ（G）： ｜V（G）｜ = 2n, diam（G） ≥〉 2} = （2n - 2）（2n - 3）[（2n - 5）!!], max{φ（G）： ｜V（G）｜ = 2n, diam（G） ≥ 3} = （n - 1）^2[（2n - 5）!!].
基金
Supported by the National Natural Science Foundation of China(No.10331020)
