本原不可幂带号有向图的lewin数的界

如果存在正整数k使得对于D中任意两点u和v(允许u=v),在D中都有从u到v的长为k的有向途径,则称有向图D是本原的.给有向图的每条弧赋以符号+1或者一l得到的图s称为带号有向图.如果带号有向图s中包含sSSD途径对,即包含两条有相同的起点,相同的终点,相同的长度,并且有不同的符号的途径对,则称s是不可幂的.在本文中,我们将Lewin M提出的lewin数的概念从本原有向图推广到本原不可幂带号有向图,给出了本原不可幂带号有向图s的lewin数l(s)的若干上界,并提出了一个公开问题.

关于Lewin问题的一个注记

一个有向图称为本原的,如果存在正整数k,使得对每个顶点u到每个顶点v(可以是u)都有一条长为k的途径。如果G是本原的,这种最小的k称为G的本原指数,记作exp(G)。如果从某点u到某点v(可以是u)存在长为k和k+1的途径,这种最小的k称为G的Lewin数,记作l(G)。Jian Shen和Stewart Neufeld猜想,exp(G)≥2l(G)。本文就一类特殊的本原有向图证明猜想成立。