On the Upper Bounds of the Numbers of Perfect Matchings in Graphs with Given Parameters |
| |
| Authors: | Hong Lin Xiao-feng Guo |
| |
| Institution: | (1) School of Mathematical Sciences, Xiamen University, Xiamen 361005, China |
| |
| Abstract: | Abstract
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 {\left\{ {\phi {\left( G \right)}:{\left| {V{\left( G \right)}} \right|} = 2n,\alpha {\left( G \right)} \geqslant k} \right\}} = {\left {{\prod\limits_{i = 0}^{k - 1} {{\left( {2n - k - i} \right)}} }} \right]}{\left {{\left( {2n - 2k - 1} \right)}!!} \right]},
$$](/content/h135417312123qm5/10255_2006_Article_360_TeX2GIFIEq1.gif)
3. max{ϕ(G): |V (G)| = 2n, χ(G) ≤ k} = ϕ(T
k,2n
) T
k,2n
is the Turán graph, that is a complete k-partite 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). |
| |
| Keywords: | Perfect matching connectivity chromatic number clique number diameter |
| 本文献已被 CNKI 维普 SpringerLink 等数据库收录！ |
|
