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

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

Bounds on the Lewin Number for Primitive Non-powerful Signed Digraphs

A digraph D is primitive if for some positive integer k there is a walk of length exactly k from each vertex u to each vertex v(possible u again).A signed digraph S is a digraph where each arc of S is assigned a sign 1 or -1.A signed digraph S is non-powerful if S contains a pair of SSSD walks which they have the same initial vertex,same terminal vertex and same length,but different signs.In this paper,we study lewin number l(S) for a primitive non-powerful signed digraph S,which is a generalization of lewin number for a primitive digraph introduced by Lewin M,some upper bounds on l(S) are given,and an open problem is presented.