一類特殊三色有向圖的本原條件和指數(shù)上界

羅美金，歐陽云

(河池學院數(shù)學與統(tǒng)計學院，廣西 宜州 546300)

若D是包含紅弧、黃弧和藍弧的有向圖，則稱D是一個三色有向圖。若D中每一對頂點(i,j)都存在從i到j的途徑，則稱三色有向圖D是強連通的，給定D中的一條途徑ω，用r(ω)、y(ω)和b(ω)分別表示ω中紅弧、黃弧和藍弧的條數(shù)，稱ω為一條(r(ω),y(ω),b(ω))-途徑，ω的分解為向量(r(ω),y(ω),b(ω))或(r(ω),y(ω),b(ω))T[1]。

一個三色有向圖D是本原的，當且僅當存在非負整數(shù)h、k和v，且h+k+v>0，使得D中的每一對頂點(i,j)都存在從i到j的(h,k,v)-途徑，h+k+v的最小值定義為三色有向圖D的本原指數(shù)，記為exp(D)[1]。

設D中含有圈γ1,γ2,…,γl，C={γ1,γ2,…,γl}是D的圈集合，定義D的圈矩陣M是一個3×l矩陣，它的第i列是γi圈的分解。M的content(記為content(M))定義為0，如果M的秩小于3，否則定義為M所有非零3階主子式的最大公因數(shù)[2]。

引理1[1]一個至少包含1條紅弧、1條黃弧和1條藍弧的三色有向圖D是本原的，當且僅當D是強連通的，且content(M)=1。

圖1 未著色三色有向圖Dn,4,2

根據(jù)矩陣與有向圖的對應關系，非負矩陣簇也可以與其伴隨有向圖(即多色有向圖)建立一一對應關系。當前，國內(nèi)外關于多色有向圖的本原指數(shù)已經(jīng)取得一些成果[1～5]，筆者研究了一類含有n(n≥5，且n為奇數(shù))個頂點，包含3個圈，且至少包含1條紅弧、1條黃弧和1條藍弧的三色有向圖Dn,4,2,其未著色有向圖如圖1所示。結(jié)合圖1可得，Dn,4,2是強連通的，對任意的D∈Dn,4,2，D中恰包含1個n-圈、1個4-圈和1個2-圈，且3個圈有唯一的一條公共弧n→1。由引理1得，D若本原，則content(M)=1，即det(M)=±1。容易驗證，2-圈中的2條弧若著相同顏色，即著色為(2,0,0)T，(0,2,0)T或(0,0,2)T時，則det(M)≠±1，即D是不本原的。因此，D若本原，2-圈中的2條弧必含2種顏色，不妨設2-圈的著色為(1,1,0)T。同理，容易驗證，當2-圈的著色為(1,1,0)T,且4-圈中著色為(4,0,0)T，(0,4,0)T(0,0,4)T，(2,2,0)T，(2,0,2)T，(0,2,2)T， (1,1,2)T，(1,3,0)T或(3,1,0)T時，則det(M)≠±1，即D是不本原的。因方法類似，以下只考慮4-圈中至少包含1條紅弧、2條藍弧和1條黃弧的情形，且設D的圈矩陣為：

其中x,y都為非負整數(shù)。

1 本原條件

定理1 若任意的D∈Dn,4,2是本原的，且4-圈的著色為(1,2,1)T，則-n+2y=±1。

證明 顯然，圖1所示的有向圖D是強連通的，根據(jù)引理1得，若D是本原的，當且僅當content(M)=1，即det(M)=±1，而此時所對應的圈矩陣為M，det(M)=-n+2y。因此，D若是本原的，即-n+2y=±1。

2 指數(shù)上界

定理2 若任意的D∈Dn,4,2是本原的，且4-圈的著色為(1,2,1)T，則：

證明 對D中的任意一對頂點(i,j)，記pij是從i到j的最短路，r(pij)=s，y(pij)=t，b(pij)=w。結(jié)合定理1，分以下2種情形討論：

情形1：-n+2y=1。此時，所對應的逆矩陣M-1為：

=n2+n-1

情形2：-n+2y=-1。此時所對應的逆矩陣M-1為：