jingzhen Gao

1990、1994年Harary相继提出和图、整和图的概念。令$N(Z)$表示正整数(整数)集，$N(Z)$ 的非空有限子集 $ S$ 的和(整和)图 $ G^{+}(S)$ 是图 $ (S,E)$，其中 $ uv\in E$ 当且仅当 $ u+v\in S$。一个图 $ G$ 称为和(整和)图，若它同构于某个 $ S\subset N(Z) $ 的和(整和)图。我们说 $ S$ 给出了 $G$ 的一个和(整和)标号。$G$ 的和数 (整和数) $\sigma(G)(\zeta(G))$ 是使得 $G\bigcup nK_{1}$ 是和(整和)图的非负整数 $n$ 的最小值。

2003年Miller等人提出排斥图的概念。图 $G\bigcup nK_{1}$ 的和标号 $S$ 称为排斥的，(exclusive) 若对每条边 $uv\in E(G),\ u+v\in S\backslash V(G)$。图 $G$ 的排斥和数 $\varepsilon(G)$ 是使得 $G\bigcup nK_{1}$ 有排斥和标号的非负整数 $n$ 的最小值。

从实用的观点看，计算机可将各种和标号作为图的表示方法。当利用它们工作时，不仅可以节省内存，还可以加快某些图算法的运算速度，并且对于了解图的结构也有帮助。

本文提出如下定义:

用 $\lfloor x \rfloor$ 表示不超过实数 $x$ 的最大整数(称为 $x$ 的下整数)，$Q^{*}$表示正有理数集。$Q^{*}$的非空有限子集$S$的下整和图 $G_{+}(S)$ 是图 $(S,E)$ ，其中 $uv\in E$ 当且仅当 $\lfloor u+v \rfloor \in S$ 。一个图 $G$ 称为下整和图，若它同构于某个 $S\subset Q^{*}$ 的下整和图.我们说 $S$ 给出 $G$ 的一个下整和标号.下整和数 $\sigma^{'}(G)$ 是使得 $G\bigcup nK_{1}$ 是下整和图的非负整数 $n$ 的最小值。

在 $G\bigcup \sigma'(G)K_{1}$ 的一个下整和标号中，对于一个顶点 $w$，如果存在某条边 $uv$，使得 $w=\lfloor u+v\rfloor$，则称 $w$ 为工作顶点.显然，工作顶点均为整数点。图 $G\bigcup nK_{1}$ 的下整和标号 $S$ 称为排斥的(exclusive)，若对每条边$uv\inE(G),\lflooru+v\rfloor\in S\backslash V(G)$。图 $G$ 的排斥下整和数 $\varepsilon^{'}(G)$ 是使得 $G\bigcup nK_{1}$ 有排斥下整和标号的非负整数 $n$ 的最小值。

下整和标号与排斥下整和标号是图的新的压缩表示。在下整和图的结构方面，我们主要研究了：

\item[(1)]下整和图禁用子图的结构，

\item[(2)]对图$G$的下整和标号$S=\{x_{i}|1\leq i\leq n\}$ 与非负整数$k$，$k\lfloorS\rfloor+S$是$G$的下整和标号的充分条件，其中$k\lfloor S\rfloor+S=\{k\lfloor x_{i}\rfloor+x_{i}|1\leq i\leq n\}$，

\item[(3)]对图$G_{1},\,G_{2}$，$\sigma^{'}(G_{1}\bigcupG_{2})\leq \sigma^{'}(G_{1}) +\sigma^{'}(G_{2})-1$ 的充分条件，

\item[(4)] 图的工作点数大于1的充分条件。

\end{kst}在常见图类的(排斥)下整和性与(排斥)下整和数方面，我们证明了 $mK_{2},\,K_{n},$\\ $K_{r,\,s},K_{n}-E(K_{r}),\,K_{n}\bigcup K_{r,\,s},\, K_{1,\,\,n,\,q}$是下整和图，$K_{m,\,n,\,q}(m,\,n,\,q\geq2)$ 的下整和数为2，\ $C_{5},\,C_{5}\bigcup K_{n}$ 的下整和数为1。而 $mK_{2},\,K_{n},\,K_{r,\,s},\,K_{n}\bigcup K_{r,\,s},\,K_{n}-E(K_{r})(1\leq r\leq n-1),\, K_{1,\,n,\,q}$ 的排斥下整和数为1，$ K_{m,\,n,\,q}(m,\,n,\,q\geq2)$ 的排斥下整和数为2，讨论了图 $ C_{n}(n\geq 3),\,K_{n}-E(mK_{2})(2\leq 2m\leq n),\,\overline{C_{n}}(n\geq3),\, K_{r,\,s}-E(mK_{2})( r,\,s\geq m),\, W_{n}(n\geq 3),\,F_{n}(n\geq 2),\,K_{n}-E(P_{m})(n\geq m)$ 在什么条件下是下整和图，还讨论了图$ F_{n}(n\geq 2),\,W_{n}(n\geq 3),\,K_{r,\,s}-E(mK_{2})( r,\,s\geq m),\,K_{n}-E(mK_{2})(2\leq 2m\leq n) ,\,K_{n}-E(P_{m})(n\geq m)$ 在什么条件下排斥下整和数为1。