ABSTRACT

The labeling of a graph G is injection g of the labels of vertices to a set of integers, and the labels of each edge e = uv are induced by the g(u) and g(v). In the paper, we obtain the graceful labeling for graphs $P_n⋎S_m$ , which proves its gracefulness, and then extend the original results.

Keywords:Graceful Graph, Vertex Degree, Vertex Labelling

图P_n⋎S_m的优美标号

郭奇¹，刘春峰²

¹东北师范大学数学与统计学院，吉林 长春

²辽宁工业大学理学院，辽宁 锦州

收稿日期：2019年4月9日；录用日期：2019年4月20日；发布日期：2019年5月5日

摘 要

图G的标号是指G的顶点集到一个整数集的映射g，且对 $e=uv\in E\left(G\right)$ 由g(u)和g(v)诱导出边e的标号。本文给出了图 $P_n⋎S_m$ 的优美性。即证明了图 $P_n⋎S_m$ 是优美图。进而推广了原有的一些结果。

关键词 :优美图，顶点的度，顶点标号

Copyright © 2019 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

图的标号理论在编码﹑雷达﹑通信网络﹑射电天文学、密码设计、导弹控制码设计等方面均有广泛的应用。现实生活中的许多问题都可抽象为图的标号问题。在天文学和晶体学中的一些问题的解决需要研究图的标号，特别是优美标号。如在天文学中天文台希望发射的信号互相不发生干扰，发射的信号频率互不相同，并且这些信号的频率差距也互不相同。这些问题可化为图的优美标号来解决。优美图是图论中重要的研究领域之一，有较好的应用价值和广阔的研究前景。1963年G. Ringel提出了一个猜想 [1] ，1960年A. Rosa给出了第一篇论文 [2] 。1972年，S. W. Gomomb明确给出了优美图的定义 [3] 。近年来，在图的标号理论，特别是优美图方面，国内外获得了很多研究成果 [4] 。我们在图的标号理论方面也得到了一些结果 [5] - [10] 。

本文仅考虑没有孤立点的简单图，文中用V(G)和E(G)分别表示图G顶点集和边集，简记为V(G) = V和E(G) = E。本文将讨论图 $P_n⋎S_m$ 的优美性。文中未提及的术语见 [11] 。

定义1 称图 $G=\left(V,E\right)$ 是k-优美(k-graceful)图，如果对任何正整数k，

$f:V\left(G\right)\to \left\{0,1,2,\cdots ,\left|E\right|+k-1\right\}$

使得由

$f^{\prime }\left(uv\right)=\left|f\left(u\right)-f\left(v\right)\right|$

所导出的函数对所有的边 $e=uv\in E\left(G\right)$ ，其映射 $E\left(G\right)\to \left\{k,k+1,\cdots ,k+\left|E\right|-1\right\}$ 是一个双射。则称f为G的一个k-优美标号。显然k-优美图，当k = 1时，就是通常所说的优美图。

用P_n和S_m分别代表n个顶点的路和m个顶点的星，设 $V\left(P_n\right)=\left\{v_1,v_2,\cdots ,v_{n-}{}_1,v_n\right\}$ ， $V\left(S_m\right)=\left\{u_0,u_1,\cdots ,u_{m-}{}_{\text{1}}\right\}$ ，不妨在图P_n和S_m中分别设， $d\left(v_{\text{1}}\right)=d\left(v_n\right)=\text{1}$ ， $d\left(u_0\right)=m-1$ 。用P_n和S_m构造一个新图，记为 $P_n⋎S_m$ ，其中图 $P_n⋎S_m$ 是把P_n中的一个1度点与S_m的r个()顶点依次相连后得到的图，文中设在 $P_n⋎S_m$ 中只有P_n的1度点v₁与S_m中的r个顶点依次相连。在 $P_n⋎S_m$ 中，若 $u_0{v}_{\text{1}}\notin E$ ( $P_n⋎S_m$ )，记 $G_0=P_n⋎S_m$ ，否则记 $G_1=P_n⋎S_m$ ，记 $G_2=G_1\cup \left\{u_0{v}_{\text{2}}\right\}$ 。如图1~3所示。

本文得到了图G_i (I = 1, 2, 3)是优美图，且G₀是k-优美图，从而推广了 [12] 中的结果。

2. 主要结果及证明

定理2.1 图G_i (i = 0, 1, 2)是优美图，且G₀是k-优美图。

图1. 图G₀

图2. 图G₁

图3. 图G₂

在图G_i (i = 0, 1, 2)中，有 $\left|V\left(G_i\right)\right|=m+n\left(i=0,\text{1},\text{2}\right)$ ， $\left|E\left(G_i\right)\right|=m+n+r-2\left(i=0,1,2\right)$ ， $\left|E\left(G_{\text{2}}\right)\right|=m+n+r-\text{1}$ 。在G₀中，由于 $u_0{v}_{\text{1}}\notin E\left(G_0\right)$ ，不妨设， $$ ；在G₁中，由于 $u_0{v}_{\text{1}}\in E\left(G_0\right)$ ，不妨设， $v_{\text{1}}{u}_i\in E\left(G_0\right)\left(i=1,2,\cdots ,r-1\right)$ ；在G₀中，由于 $u_0{v}_{\text{1}},u_0{v}_{\text{2}}\in E\left(G_2\right)$ ，不妨设 $v_{\text{1}}{u}_i\in E\left(G_0\right)\left(i=1,2,\cdots ,r-2\right)$ 。

2.1. 证明G₀是k-优美图

分两种情况证明G₀是k-优美图。

情况1 $n\equiv 0\left(\mathrm{mod}2\right)$

定义G₀的顶点标号f为：

$f\left(u_0\right)=0$ ,

, $i=1,2,\cdots ,r$ ,

$f\left(u_{r+i}\right)=n+k-2+2r+i$ , $i=1,2,\cdots ,m-r-1$ ,

$f\left(v_{\text{2}i-\text{1}}\right)=i$ , $i=1,2,\cdots ,\frac{n}{2}$ ,

$f\left(v_{\text{2}i}\right)=n+k-i$ , $i=1,2,\cdots ,\frac{n}{2}$ .

由f的定义有，f是V(G₀)到 $\left\{0,1,2,\cdots ,n+m+r+k-3\right\}$ 的一个单射。

图G₀中， $\forall x,y\in V\left(G_0\right)$ ， $x\ne y$ ， $f\left(x\right)\ne f\left(y\right)$ ， $\max \left\{f\left(x\right)|x\in V\left(G_0\right)\right\}=f\left(u_m{}_{-1}\right)=\left|E\left(G_0\right)\right|+k-1$ 。 $\forall e=xy\in E\left(G_0\right)$ ，由 $f^{\prime }\left(xy\right)=\left|f\left(x\right)-f\left(y\right)\right|$ 易推得， $\forall e_1,e_2\in E\left(G_0\right)$ ，若 $e_1\ne e_2$ ，有 $f\left(e_1\right)\ne f\left(e_2\right)$ ，且有 $\max \left\{f\left(e\right)|e\in E\left(G_0\right)\right\}=\left|f\left(u_{m-}{}_1\right)-f\left(u_0\right)\right|=f\left(u_m{}_{-1}\right)=\left|E\left(G_0\right)\right|+k-1$ 。事实上，设 $A_1=E\left(P_n\right)$ ， $A_2=\left\{v_1{u}_i|i=1,2,\cdots ,r\right\}$ ， $A_3=\left\{u_0{u}_i|i=1,2,\cdots ,r\right\}$ ， $A_4=\left\{u_0{u}_i|i=r+1,\cdots ,m-1\right\}$ 。于是有

$\begin{array}{c}{I}_1=\left\{f^{\prime }\left(e\right)|e\in E\left(P_n\right)\right\}=\left\{f\left(u_{2i}\right)-f\left(v_{2i-1}\right)|i=1,2,\cdots ,\frac{n}{2}\right\}\\ =\left\{n+k-\text{2}i|i=1,2,\cdots ,\frac{n}{2}\right\}=\left\{k,k+\text{1},\cdots ,n+k-3,n+k-2\right\}\end{array}$ ,

$\begin{array}{c}{I}_2=\left\{f^{\prime }\left(e\right)|e\in E\left(P_n\right)\right\}=\left\{f\left(u_i\right)-f\left(v_1\right)|i=1,2,\cdots ,r\right\}\\ =\left\{n+k-3+\text{2}i|i=1,2,\cdots ,r\right\}=\left\{n+k-1,n+k+\text{1},\cdots ,n+k-3+2r\right\}\end{array}$ ,

$\begin{array}{c}{I}_3=\left\{f^{\prime }\left(e\right)|e\in A_3\right\}=\left\{f\left(u_i\right)-f\left(u_0\right)|i=1,2,\cdots ,r\right\}\\ =\left\{n+k-2+\text{2}i|i=1,2,\cdots ,r\right\}=\left\{n+k,n+k+\text{2},\cdots ,n+k-2+2r\right\}\end{array}$ ,

$\begin{array}{c}{I}_4=\left\{f^{\prime }\left(e\right)|e\in A_4\right\}=\left\{f\left(u_{r+i}\right)-f\left(u_0\right)|i=1,2,\cdots ,m-1-r\right\}\\ =\left\{n+k-2+2r+\text{2}i|i=1,2,\cdots ,m-1-r\right\}\\ =\left\{n+k-1+2r,n+k+2r,\cdots ,m+n+k-3\right\}\end{array}$ .

由集合I_i (i = 1, 2, 3, 4)，有 $I_i\cap I_j=\varnothing$ ， $i\ne j,1\le i,j\le 4$ ，且 $\forall e_1,e_2\in E\left(G_0\right)$ ，若 $e_1\ne e_2$ ，有 f（e₁） ≠ ( f（e₂） $$ 。于是得f是G₀的k-优美标号。

情况2 $n\equiv 1\left(\mathrm{mod}2\right)$

定义G₀的顶点标号f为：

$f\left(u_0\right)=0$ ,

$f\left(u_i\right)=n+k-\text{2}+\text{2}i$ , $$ ,

$f\left(u_{r+i}\right)=n+k-\text{2}+\text{2}r+i$ , $i=1,2,\cdots ,m-r-1$ ,

$f\left(v_{\text{2}i-\text{1}}\right)=i$ , $i=1,2,\cdots ,\frac{n+1}{2}$ ,

$f\left(v_{\text{2}i}\right)=n+k-i$ , $i=1,2,\cdots ,\frac{n-1}{2}$ .

类似情况1的论证，在情况中易验证f是G₀的k-优美标号。

2.2. 证明G₁是优美图

分两种情况证明G₁是优美图。

情况1 $n\equiv 0\left(\mathrm{mod}2\right)$

定义G₁的顶点标号f为：

$f\left(u_0\right)=0$ ,

$f\left(u_i\right)=n+2i$ , $i=1,2,\cdots ,r$ ,

$f\left(u_{r+i}\right)=n+2r+i$ , $i=1,2,\cdots ,m-r-1$ ,

$f\left(v_{\text{2}i-\text{1}}\right)=i$ , $i=1,2,\cdots ,\frac{n}{2}$ ,

$f\left(v_{\text{2}i}\right)=n+2-i$ , $i=1,2,\cdots ,\frac{n}{2}$ .

情况2 $n\equiv 1\left(\mathrm{mod}2\right)$

定义G₁的顶点标号f为：

$f\left(u_0\right)=0$ ,

$f\left(u_i\right)=n+\text{2}i$ , $$ ,

$f\left(u_{r+i}\right)=n+\text{2}r+i$ , $i=1,2,\cdots ,m-r-1$ ,

$f\left(v_{\text{2}i-\text{1}}\right)=i$ , $i=1,2,\cdots ,\frac{n+1}{2}$ ,

$f\left(v_{\text{2}i}\right)=n+2-i$ , $i=1,2,\cdots ,\frac{n-1}{2}$ .

类似2.1的论证，易验证标号f是G₁的优美标号。

2.3. 证明G₂是优美图

分两种情况证明G₂是优美图。

情况1 $n\equiv 0\left(\mathrm{mod}2\right)$

定义G₂的顶点标号f为：

$f\left(u_0\right)=0$ ,

$f\left(u_i\right)=n+1+2i$ , $i=1,2,\cdots ,r$ ,

$f\left(u_{r+i}\right)=n+1+2r+i$ , ,

$f\left(v_{\text{2}i-\text{1}}\right)=i$ , $i=1,2,\cdots ,\frac{n}{2}$ ,

$f\left(v_{\text{2}i}\right)=n+2-i$ , $i=1,2,\cdots ,\frac{n}{2}$ .

情况2 $n\equiv 1\left(\mathrm{mod}2\right)$

定义G₂的顶点标号f为：

$f\left(u_0\right)=0$ ,

$$ , $i=1,2,\cdots ,r$ ,

$f\left(u_{r+i}\right)=n+1+\text{2}r+i$ , $i=1,2,\cdots ,m-r-1$ ,

$f\left(v_{\text{2}i-\text{1}}\right)=i$ , $i=1,2,\cdots ,\frac{n+1}{2}$ ,

$f\left(v_{\text{2}i}\right)=n+2-i$ , $i=1,2,\cdots ,\frac{n-1}{2}$ .

类似2.1的论证，标号f是G₂的优美标号。

定理2.1证毕。

文章引用

郭 奇,刘春峰. 图PnΥSm的优美标号
Graceful Labeling of Graphs PnΥSm[J]. 理论数学, 2019, 09(03): 259-264. https://doi.org/10.12677/PM.2019.93033

参考文献