n维扭曲立方体是超k-匹配图

The TQ_n Is Super k-Matching Graph

摘要: 图$G$ 的整数$k$ -匹配是由$E\left(G\right)$ 到$\left\{0,1,\cdots ,k\right\}$ 上的映射$f$ ，满足对任意点$u$ ，所有$f\left(e\right)$ 的加和不超过$k$ ，其中$f\left(e\right)$ 之和为所有以点$u$ 为端点的边$e$ 。当$k=1$ 时，整数$k$ -匹配即为匹配。(强)整数$k$ -匹配排除数由$m{p}^k\left(G\right)$ $\left(sm{p}^k\left(G\right)\right)$ 表示，是被一个图删去后该图既不存在完美整数$k$ -匹配，也不存在几乎完美整数$k$ -匹配的最小点集(点集与边集)的元素数。Caibing Chang、Xianfu Li and Yan Liu介绍了$sm{p}^k\left(T{Q}_n\right)$ 。本文提出超强整数$k$ -匹配的定义并证明$T{Q}_n$ 是超强整数$k$ -匹配图。

Abstract: An integer $k$ -matching of a graph $G$ is a function $f$ from $E\left(G\right)$ to $\left\{0,1,\cdots ,k\right\}$ such that the sum of $f\left(e\right)$ is not more than $k$ for any vertex $u$ , where the sum of $f\left(e\right)$ is taken over all edges $e$ incident to $u$ . When $k=1$ , the integer $k$ -matching is a matching. The (strong) integer $k$ -matching preclusion number, denoted by $m{p}^k\left(G\right)$ $\left(sm{p}^k\left(G\right)\right)$ , is the number of elements of the minimum vertex (vertices and edges) whose deletion results in a graph with neither perfect integer $k$ -matching nor almost perfect integer $k$ -matching. The $sm{p}^k\left(T{Q}_n\right)$ was introduced by Caibing Chang, Xianfu Li and Yan Liu. In this paper, we denote the super strong integer $k$ -matching and prove that $T{Q}_n$ is super strong integer $k$ -matching graph.