Nordhaus-Gaddum type result for the matching number of a graph
Nordhaus-Gaddum type result for the matching number of a graph
复制标题
图表匹配编号的 Nordhaus-Gaddum 类型结果
DOI：
10.1007/s10878-017-0120-6
复制
发表时间：
2017
影响因子：
1
通讯作者：
Wu Baoyindureng
中科院分区：
文献类型：
--
作者：
Lin Huiqiu;Shu Jinlong;Wu Baoyindureng
For a graphG,is the matching number ofG. Letbe an integer,be the complete graph of ordern. Assume thatis ak-decomposition of. In this paper, we show that (1) $$\begin{aligned} \left\lfloor \frac{n}{2}\right\rfloor \le \sum _{i=1}^{k} \alpha '(G_{i})\le k\left\lfloor \frac{n}{2}\right\rfloor . \end{aligned}$$(2) If eachis non-empty for, then for, $$\begin{aligned} \sum _{i=1}^{k} \alpha '(G_{i})\ge \left\lfloor \frac{n+k-1}{2}\right\rfloor . \end{aligned}$$(3) Ifhas no isolated vertices for, then for, $$\begin{aligned} \sum _{i=1}^{k} \alpha '(G_{i})\ge \left\lfloor \frac{n}{2}\right\rfloor +k. \end{aligned}$$The bounds in (1), (2) and (3) are sharp. (4) When, we characterize all the extremal graphs which attain the lower bounds in (1), (2) and (3), respectively.
For a graphG,is the matching number ofG. Letbe an integer,be the complete graph of ordern. Assume thatis ak-decomposition of. In this paper, we show that (1) $$\begin{aligned} \left\lfloor \frac{n}{2}\right\rfloor \le \sum _{i=1}^{k} \alpha '(G_{i})\le k\left\lfloor \frac{n}{2}\right\rfloor . \end{aligned}$$(2) If eachis non-empty for, then for, $$\begin{aligned} \sum _{i=1}^{k} \alpha '(G_{i})\ge \left\lfloor \frac{n+k-1}{2}\right\rfloor . \end{aligned}$$(3) Ifhas no isolated vertices for, then for, $$\begin{aligned} \sum _{i=1}^{k} \alpha '(G_{i})\ge \left\lfloor \frac{n}{2}\right\rfloor +k. \end{aligned}$$The bounds in (1), (2) and (3) are sharp. (4) When, we characterize all the extremal graphs which attain the lower bounds in (1), (2) and (3), respectively.