| 赵科,李敬文,魏众德.优雅图猜想[J].,2018,58(6):641-648 |
| 优雅图猜想 |
| Conjecture of elegant graph |
| |
| DOI：10.7511/dllgxb201806013 |
| 中文关键词: 优雅标号 优雅图 非优雅图 优雅空间 优雅图猜想 |
| 英文关键词: elegant labeling elegant graphs non-elegant graphs elegant spaces elegant graphs conjectures |
| 基金项目:国家自然科学基金资助项目(11461038,61163010). |
|
| 摘要点击次数: 770 |
| 全文下载次数: 738 |
| 中文摘要: |
| 对于图G(p，q)，如果存在一个单射f：V(G)→［0，1，2，…，q］，使得f(E(G))={f(uv)=(f(u)+f(v))mod(q+1)|uv∈E(G)}=［1，…，q］，则称图G为优雅图．采用剪枝与预判函数相结合的方式，设计了递归回溯算法，对9个点内的所有简单连通图进行了优雅性验证，得到9个点内所有优雅图和非优雅图．根据实验结果，验证了当3≤p≤9时，所有的树图、单圈图几乎都是优雅的，证明了当3≤q≤9且q≠1(mod 4)时，图G(p，q)是优雅的．最后给出猜想：绝大多数的图是优雅的． |
| 英文摘要: |
| For graph G(p,q), if there exists an injective function f:V(G)→［0,1,2,…,q］, such that f(E(G))={f(uv)=(f(u)+f(v))mod (q+1)|uv∈E(G)}=［1,…,q］, the graph G is called an elegant graph. A combination of pruning and predictive function is used to design a recursive backtracking algorithm. The elegance of all the simple connected graphs in 9 points is verified, and all elegant and non-elegant graphs are obtained. According to the experimental results, it is verified that when 3≤p≤9, all tree graphs and unicyclic graphs are almost elegant, which proves that when 3≤q≤9 and q≠1(mod 4), the graph G(p,q)is elegant. Finally, the conjecture that the majority of the graphs are elegant is given. |
|
查看全文
查看/发表评论 下载PDF阅读器 |
| 关闭 |
|
|
|