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

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

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

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.