Primitive Non-Powerful Symmetric Loop-Free Signed Digraphs with Base 3 and Minimum Number of Arcs

DOI：10.3770/j.issn:2095-2651.2013.03.002

 作者 单位 尤利华 华南师范大学数学科学学院，广东 广州 510631 吴钰涵 华南师范大学数学科学学院，广东 广州 510631

在文 [给定基指数且具有最小弧数的本原不可幂对称无环带号有向图, Linear Algebra Appl. 434 (2011), 1215--1227]中,作者提出了如下猜想:设$n$是偶数, $S$ 是具有最小弧数且基指数为3的$n$阶本原不可幂对称无环带号有向图,则$D$ 是$S$ 的基础有向图且其本原指数$\exp(D) = 3$当且仅当 $D$同构于有向图 $ED_{n,3,3}$,这里$ED_{n,3,3} =(V,A)$,其顶点集 $V=\{1,2,\ldots,n\}$,弧集$A=\{(1,i),(i,1)\mid 3\leq i \leq n\} \cup \{(2i-1,2i),(2i,2i-1)\mid 2\leq i \leq \frac{n}{2}\}\cup \{(2,3),(3,2), (2,4),(4,2)\}$).在本文中,我们首先证明了此猜想是正确的,进而完全刻画了具有最小弧数且基指数为3的$n$阶本原不可幂对称无环带号有向图的基础有向图.

Let $S$ be a primitive non-powerful symmetric loop-free signed digraph on even $n$ vertices with base 3 and minimum number of arcs. In [Lihua YOU, Yuhan WU. Primitive non-powerful symmetric loop-free signed digraphs with given base and minimum number of arcs. Linear Algebra Appl., 2011, 434(5), 1215--1227], authors conjectured that $D$ is the underlying digraph of $S$ with $\exp(D)=3$ if and only if $D$ is isomorphic to $ED_{n,3,3}$, where $ED_{n,3,3}=(V,A)$ is a digraph with $V=\{1,2,\ldots,n\}$, $A=\{(1,i),(i,1)\mid 3\leq i \leq n\} \cup \{(2i-1,2i),(2i,2i-1)\mid 2\leq i \leq \frac{n}{2}\}\cup \{(2,3),(3,2), (2,4),(4,2)\}$). In this paper, we show the conjecture is true and completely characterize the underlying digraphs which have base 3 and the minimum number of arcs.