The gracefulness of graphs (n≤9)

WEI Zhongde; LI Jingwen; WU Yonglan

您当前的位置：

首页 >

文章列表页 >

The gracefulness of graphs (n≤9)

更新时间：2023-12-11

- The gracefulness of graphs (n≤9)
- Acta Scientiarum Naturalium Universitatis SunYatseni Vol. 57, Issue 4, Pages: 76-85(2018)
- 作者机构：
  
  兰州交通大学电子与信息工程学院,甘肃,兰州,730070
- 作者简介：
- 基金信息：
- DOI：
  CLC：
- Published：2018，
  
  Published Online：25 July 2018，
扫描看全文
WEI Zhongde, LI Jingwen, WU Yonglan. The gracefulness of graphs (n≤9). [J]. Acta Scientiarum Naturalium Universitatis SunYatseni 57(4):76-85(2018)
DOI：

WEI Zhongde, LI Jingwen, WU Yonglan. The gracefulness of graphs (n≤9). [J]. Acta Scientiarum Naturalium Universitatis SunYatseni 57(4):76-85(2018) DOI：

摘要

设计了一种递归回溯算法，采用了剪枝函数与预判函数相结合的算法优化策略，实现了对有限点内任意图的优美性验证。利用该算法，对9个点内的所有简单连通图进行了优美性验证，得到该范围内所有优美图和非优美图的数量。结果表明，在该范围内绝大多数的图是优美的。并且根据实验数据，文中还得出以下结果：K

-m由完全图减去

条边所得的图）是非优美图的确定下界；当

、

满足一定条件时，这类(

）图（

为顶点数

为边数）中的所有图全部是优美的；当

(mod 4)={0

3}，且

≤［3.7

-9.3］时，(

)图中几乎所有的图都是优美的。且进一步猜测，当

9时，相关结论成立。

Abstract

A recursive backtracking algorithm is designed

which uses the algorithm optimization strategy combined with pruning and prejudging function. It achieves the graceful verification for any graphs within finite points. Using this algorithm

the gracefulness of all the simple connected graphs are verifying in 9 points

and the number of all the graceful and ungraceful graphs is obtained in this range. the results show that the vast majority of the graphs are graceful in this range. And according to the experimental data

the following conclusions are also shown: a definite lower bound of graph K

-m (a graph of complete graph minus

edges) is ungraceful; when

and

satisfy certain conditions

all of this kind of (

）graphs (

is the number of vertex

and

is the number of edges) are graceful; when

(mod 4)={0

and

≤［3.7

-9.3

almost all of this kind of (

) graphs are graceful. And further guess

when

the relevant conclusions are rational.

关键词

优美标号优美图非优美图优美空间算法

Keywords

graceful labelinggraceful graphungraceful graphsgraceful spacealgorithm

references

Views

211

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

The Graceful Labeling of the Graph S(4m+1,4(t+1),4m－1) Based on the Balanced Labeling of the Path P_8m+4t+2

Graceful Labeling of the Corona for Two Kinds of Graceful Graphs

The alternating labeling of the graph F_n,4（r₁,r₂,…,r_3n+1）

L（2，1）-edge coloring algorithm for some composite graphs

The Graceful Graphs on Several Kinds of Union Graphs

Related Author

WU Yuesheng

唐保祥

任韩

WU Yuesheng

ZHU Lina

LI Jingwen

SUN Shuai

ZHANG Kunlong

Related Institution

School of Science, East China Jiaotong University

School of Mathematics and Statistics, Tianshui Normal University



School of Electronic and Information Engineering，Lanzhou Jiaotong University

North China Institute of Science and Technology

Postal code：510275
Tel：020-84112585，84113223 Email：xuebaozr@mail.sysu.edu.cn
Technical support is provided by Beijing Founder electronics co., LTD 京ICP备09064830号-19 京公网安备11010802024621
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰