图的反魔幻猜想的相关研究

发布时间：2020-05-07 23:21

【摘要】：图的反魔幻标记问题是由Hartsfield和Ringel于1990年提出.他们猜想:除K2之外的所有连通图都是反魔幻的.关于这个问题的研究得到最重要的结果是由Alon et al[2]给出的结果:若存在一个常数C使得n顶点图G满足δ(G)≥Clogn,则G是反魔幻的.同时他们也证明了:如果n(n≥4)顶点图G满足△(G≥n-2,那么G是反魔幻的.此后,许多图类都已经被证明是反魔幻的.例如,路径、圈、正则图、笛卡尔乘积图、联图以及某些树类等都已被证明是反魔幻的.但此猜想并没有完全得到解决.图G的边标记f是指其边集E(G)到数集{1,2,…,|E(G)|}的一一映射.如果G存在一个边标记使得它的顶点标记之和是成对不相同的,则称f是反魔幻标记,称G是反魔幻的.其中对于顶点v,它的标记之和是指关联到顶点v的所有边标记之和.在本篇文章中,我们以矩阵为主要工具来证明合成图κm,n[Pk],g[Pn]以及H[κm,n]是反魔幻的.
【图文】：

－＇赢逡逑图１．２路径Ｐ４及完全二部图Ｋ３，４的反魔幻标记逡逑关于图的反魔幻标记是由Ｈａｒｔｓｆｉｅｌｄ和ＲｉｎｇｅｌＷ在１９９０年提出的？他们猜想：逡逑猜想１．２．１Ｗ除了私之外每个连通图都是反魔幻的．逡逑猜想１．２．２Ｗ除了之外每棵树都是反魔幻的．逡逑２逡逑

和Ｕ２在？／／中相邻．逡逑二逡逑图１．１路径Ｐ５与Ｐ４的合成图Ｐ５［＿Ｐ４］逡逑１．２图的反魔幻标记逡逑一个图Ｇ的标记／是一个从边集五（Ｇ）到数集｛Ｉ，，２，…，丨迟（Ｇ）｜｝的一一映射？逡逑关于图的魔幻标记最早是由Ｓｅｄｌ纪ｅｋ［１７】在１９６３年提出．一个图Ｇ称为魔幻的，如逡逑果Ｇ有一个边标记使得每个顶点的边标记之和都是相同的．其中对于Ｇ中的每个逡逑顶点ｕ，它的边标记之和而是关联到顶点ｕ的所有边构逡逑成的集合．与之相反的自然是Ｇ有一个边标记使得灼（Ｗ）是两两不相同的．逡逑定义１．２．１设Ｇ邋＝邋0／，五）是一个图，／邋：五一＞邋｛１，２，…，间｝是一个一一映射．逡逑如果Ｇ中的任意两个顶点ｕ和ｗ都有＜＾（ｕ）邋＃邋Ｗ／ｈ），那么称／为Ｇ的一个反魔幻逡逑标记．一个图Ｇ存在反魔幻标记，则称这个图是反魔幻的．逡逑－＇赢逡逑图１．２路径Ｐ４及完全二部图Ｋ３，４的反魔幻标记逡逑关于图的反魔幻标记是由Ｈａｒｔｓｆｉｅｌｄ和ＲｉｎｇｅｌＷ在１９９０年提出的？他们猜想：逡逑猜想１．２．１Ｗ除了私之外每个连通图
【学位授予单位】：天津工业大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5

【相似文献】

相关期刊论文 前10条

1 程靖龙;吴晓松;;改变称谓 摆脱思维自我设限——从矢量三角形到力合成图[J];物理教师;2016年12期

2 徐峻;张懋森;;计算机辅助合成设计的基本原理[J];化学通报;1989年08期

3 刘靖;;水土保持《合成图法》的研究与应用[J];山西水土保持科技;1991年01期

4 ;英国海军下一代攻击型核潜艇“机敏”号(电脑合成图)[J];环球军事;2006年07期

5 卢大亮;;合成图试题的判读与解题技巧[J];试题与研究;2007年09期

6 孙良;合成图的全着色[J];北京理工大学学报;1993年S1期

7 蒋栋荣,万同山;VLBI综合成图法的发展[J];天文学进展;1992年04期

8 张学孝;Abbott定理的改进[J];兰州铁道学院学报;1997年04期

9 李春光;;随钻测井实时解释综合成图技术研究[J];中外能源;2013年06期

10 卢大亮;;合成图类试题的解题方法探讨[J];中学政史地(高中地理);2006年10期

相关会议论文 前1条

1 黄玲;刘勇;;载人航天条件下心电正交合成图的研究[A];全国第二届信号处理与应用学术会议专刊[C];2008年

相关重要报纸文章 前1条

1 张梦然;NASA新公布不可思议的行星合成图[N];科技日报;2010年

相关博士学位论文 前1条

1 黎英;面向铁路信息共享的语义web服务合成技术及方法研究[D];北京交通大学;2008年

相关硕士学位论文 前3条

1 曾贤镜;基于DEM的地形合成方法研究与实现[D];电子科技大学;2018年

2 陆英宇;图的反魔幻猜想的相关研究[D];天津工业大学;2018年

3 王晓琦;若干合成图的星边染色和星全染色[D];西北民族大学;2013年

本文编号：2653706