|
On the Upper Bounds of the Numbers of Perfect Matchings in Graphs with Given Parameters
Hong Lin, Xiao-feng Guo
Acta Mathematicae Applicatae Sinica(English Series)
2007, 23 (1):
155-160.
Let $\phi (G)$, $\kappa (G)$, $\alpha (G)$, $\chi (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 $\{\phi (G)$: $|V(G)|=2n$, $\kappa (G)\leq k\}=k[(2n-3)!!]$,\\ 2. max$\{\phi (G)$: $|V(G)|=2n$, $\alpha (G)\geq k\}=\Big[\prod\limits_{i=0}^{k-1}(2n-k-i)\Big][(2n-2k-1)!!]$,\\ 3. max$\{\phi (G)$: $|V(G)|=2n$, $\chi (G)\leq k\}=\phi (T_{k,2n})$ \ $T_{k,2n}$ is the Tur$\acute{a}$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$\{\phi (G)$: $|V(G)|=2n$, $cl(G)=2\}=n!$,\\ 5. max$\{\phi (G)$: $|V(G)|=2n$, diam$(G)\geq 2\}=(2n-2)(2n-3)[(2n-5)!!]$,\\ max$\{\phi (G)$: $|V(G)|=2n$, diam$(G)\geq 3\}=(n-1)^2[(2n-5)!!]$.
Related Articles |
Metrics
|
|