双正则可二部图的反魔幻标号

摘要

一个简单图G的反魔幻标号是一个双射,使得对于G中任意两点u,v,有 。如果一个图具有反魔幻标号,那么这个图就是反魔幻的。在1990年,Hartsfield和Ringe定义了图的反魔幻标号,并且猜想除K2以外的每一个连通图都是反魔幻的。此猜想自1990年被提出以来受到广泛关注,但仍未完全解决。本文从完全图入手,设计出一种新的标号方式区分了完全图中的各点并且可以得到各点具体的标号和,并且运用这种标号方式将猜想推广到了一类特殊图上——双正则可二部图,证明了每一个双正则可二部图都是反魔幻的。