關(guān)于一致超圖直積的循環(huán)指數(shù)

范益政，田夢宇

(安徽大學(xué) 數(shù)學(xué)科學(xué)學(xué)院, 安徽 合肥 230601)

文獻(xiàn)[1-2]獨立地引入了張量的特征值.文獻(xiàn)[3]引入一致超圖的鄰接張量表示, 并推廣了簡單圖上的若干譜結(jié)論.

定義1

設(shè)

G

為

n

個點

v

,

v

,…,

v

上的

m

-一致超圖, 其鄰接張量定義為

m

階

n

維張量(

G

)=(

a

…), 其中

根據(jù)非負(fù)張量的Perron-Frobenius定理, 如果為不可約或弱不可約非負(fù)張量, 則它的譜半徑

ρ

()是的特征值, 并且對應(yīng)唯一的正特征向量(在相差一個常數(shù)倍意義下), 且有

(1)

在文獻(xiàn)[9]中, 作者定義了一般張量的譜對稱性, 并利用張量的廣義跡給出了循環(huán)指數(shù)的顯式表示.

定義2

設(shè)為張量,

l

為正整數(shù).稱為譜

l

-對稱的, 如果

(2)

滿足式(2)的最大正整數(shù)

l

稱為的循環(huán)指數(shù), 記為

c

().一致超圖

G

稱為是譜

l

-對稱的, 如果其鄰接張量(

G

)是譜

l

-對稱的;

G

的循環(huán)指數(shù)定義為其鄰接張量(

G

)的循環(huán)指數(shù), 記為

c

(

G

). 文獻(xiàn)[3]提出研究

m

-一致超圖的譜

m

-對稱性. 文獻(xiàn)[10]應(yīng)用張量的廣義跡給出

m

階張量的譜

m

-對稱的刻畫. 文獻(xiàn)[11]提出研究

m

-一致超圖的對稱譜問題 (即譜2-對稱問題). 文獻(xiàn)[12]完全刻畫了超圖的對稱譜問題. 文獻(xiàn)[13]刻畫了

m

-一致超圖的對稱

H

-譜問題. 論文主要研究超圖直積的譜對稱性, 證明

G

×

H

是譜[

c

(

G

),

c

(

H

)]-對稱的, 從而[

c

(

G

),

c

(

H

)]|

c

(

G

×

H

), 其中[

a

,

b

]記正整數(shù)

a

,

b

的最小公倍數(shù).

1 預(yù)備知識

設(shè)=(

a

…)為

m

階

n

維張量. 若的所有元素

a

…在其指標(biāo)的任意置換下仍保持不變, 則稱為對稱張量; 若的所有元素

a

…都非負(fù), 則稱為非負(fù)張量. 定義的關(guān)聯(lián)有向圖

D

()如下: 其點集為{1,2,…,

n

},弧集為{(

i

,

i

),…,(

i

,

i

)|

a

…≠0}.

D

()可能包含環(huán)和多重弧. 張量稱為是弱不可約的, 如果

D

()是強連通的.

(

x

-1)=∑,…,∈[]

a

…

x

…

x

,

i

∈[

n

].定義

m

階

n

維單位張量為=(

i

…), 其中, 當(dāng)

i

=

i

=…=

i

∈[

n

]時，

i

…=1; 否則

i

…=0.

張量的特征多項式

φ

(

λ

)定義為多項式系統(tǒng)(

λ

-)

x

-1的結(jié)式， 見文獻(xiàn)[1,14-15]. 易見,

λ

是的特征值當(dāng)且僅當(dāng)它是

φ

(

λ

)的根. 張量的譜定義為

φ

(

λ

)的根的多重集, 記為Spec(). 張量的譜半徑定義為的所有特征值的最大模, 記為

ρ

().

文獻(xiàn)[16]引入同階張量的直積的概念, 并給出若干譜結(jié)論.

定義4

設(shè)和為

m

階且維數(shù)分別為

n

,

n

的張量. 直積?定義為

m

階

n

n

維的張量, 其元素為(?)(,)(,)…(,)=

a

…

b

…,其中：元素的下標(biāo)取集合[

n

]×[

n

]的字典序.設(shè)

G

=(

V

,

E

)為一個超圖. 超圖

G

的一個長為

t

的鏈定義為如下點邊交錯序列

v

e

v

e

…

e

v

, 其中

v

≠

v

+1且{

v

,

v

+1}?

e

,

i

=0,1,…,

t

-1. 超圖

G

稱為是連通的, 如果它的任意兩點都有一條鏈連接. 假設(shè)

G

是

m

-一致超圖, 則其鄰接張量(

G

)是非負(fù)對稱的, 且它是弱不可約當(dāng)且僅當(dāng)

G

是連通的. 論文中, 一致超圖

G

的譜、譜半徑、特征值和特征向量均指其鄰接張量的相應(yīng)定義. 一致超圖

G

的譜半徑記為

ρ

(

G

).

定義5

設(shè)

G

和

H

為兩個

m

-一致超圖, 則

G

和

H

的直積, 記為

G

×

H

, 具有點集

V

(

G

×

H

)=

V

(

G

)×

V

(

H

),且{(

i

,

j

),…,(

i

,

j

)}∈

E

(

G

×

H

)當(dāng)且僅當(dāng){

i

,…,

i

}∈

E

(

G

)且{

j

,…,

j

}∈

E

(

H

).

引理1

設(shè)

G

和

H

為兩個

m

-一致超圖, 則

G

×

H

的鄰接張量為(

G

×

H

)=(

m

-1)!((

G

)?(

H

)).如果

λ

是

G

的對應(yīng)于特征向量

x

的特征值,

μ

是

H

對應(yīng)于特征向量

y

的特征值, 則(

m

-1)!

λμ

是

G

×

H

對應(yīng)于特征向量

x

?

y

的特征值.

2 超圖直積的循環(huán)指數(shù)

設(shè)

G

和

H

為兩個

m

-一致超圖. 該節(jié)主要討論

G

×

H

的循環(huán)指數(shù)

c

(

G

×

H

)與

G

和

H

的循環(huán)指數(shù)

c

(

G

)和

c

(

H

)的聯(lián)系, 證明了[

c

(

G

),

c

(

H

)]|

c

(

G

×

H

). 先介紹關(guān)于非負(fù)弱不可約張量的Perron-Frobenius定理, 其中的一個特征值稱為是

H

-特征值, 如果它對應(yīng)一個正特征向量.

定理1

設(shè)為非負(fù)弱不可約張量, 則譜半徑

ρ

()是的唯一

H

-特征值,且對應(yīng)唯一的正特征向量(在相差一個常數(shù)倍意義下).對于

m

階

n

維張量, 以及兩個

n

×

n

的對角矩陣,, 根據(jù)文獻(xiàn)[16]中定義,定義為

m

階

n

維張量, 其元素為()…=

p

a

…

q

…

q

.如果=, 則稱和-1對角相似， 此時,和-1具有相同的譜.

定理2

設(shè)和為

m

階

n

維實張量, 且||≤, 即|

b

…|≤

a

…,

i

∈[

n

],

j

∈[

m

]. 則(1)

ρ

()≤

ρ

();

定理3中的

k

即為的循環(huán)指數(shù).

引理2

設(shè)為

m

階張量. 如果是譜

l

-對稱的, 則

l

|

c

(); 如果還是對稱的, 則

l

|

m

, 從而

c

()|

m

.首先討論超圖直積的連通性. 超圖

G

的2-部分圖(2-section), 記為[

G

], 定義為點集

V

(

G

)上的簡單圖, 其邊集為{{

u

,

v

}|

u

≠

v

,?

e

∈

E

(

G

),{

u

,

v

}?

e

}, 即兩個點在[

G

]中相鄰當(dāng)且僅當(dāng)它們屬于

G

的同一條邊.

引理3

設(shè)

G

和

H

為兩個

m

-一致超圖,

m

≥3. 則

G

×

H

是連通的當(dāng)且僅當(dāng)

G

和

H

都是連通的.

證明

顯然,

G

×

H

是連通的當(dāng)且僅當(dāng)[

G

×

H

]是連通的.根據(jù)文獻(xiàn)[18]的引理6.3,[

G

×

H

]=[

G

]×[

H

]. 根據(jù)文獻(xiàn)[19]的定理1, [

G

]×[

H

]是連通的當(dāng)且僅當(dāng)[

G

]和[

H

]都連通(或等價地,

G

和

H

都連通), 且至少有一個是非二部圖. 由于

m

≥3, [

G

]和[

H

]都含有

m

-團(即

m

個點上的完全子圖), 因而它們都是非二部的. 因此,

G

×

H

是連通的當(dāng)且僅當(dāng)

G

和

H

都是連通的.

定理4

設(shè)

G

和

H

為兩個連通的

m

-一致超圖, 且

G

×

H

連通. 則

G

×

H

是譜[

c

(

G

),

c

(

H

)]-對稱的, 從而[

c

(

G

),

c

(

H

)]|

c

(

G

×

H

).

證明

由于

G

和

H

都是連通的, 從而(

G

)和(

H

)都是弱不可約的. 根據(jù)定理1,

ρ

(

G

)和

ρ

(

H

)分別為(

G

)和(

H

)的特征值, 且分別對應(yīng)于正特征向量

x

和

y

. 根據(jù)引理1, (

m

-1)!

ρ

(

G

)

ρ

(

H

)是(

G

×

H

)的特征值, 且對應(yīng)于正特征向量

x

?

y

. 因此, 根據(jù)定理1, (

m

-1)!

ρ

(

G

)

ρ

(

H

)是

G

×

H

的譜半徑, 即

ρ

(

G

×

H

)=(

m

-1)!

ρ

(

G

)

ρ

(

H

).

(3)

設(shè)

λ

和

μ

分別為(

G

)和(

H

)的特征值. 根據(jù)引理1, (

m

-1)!

λμ

是

G

×

H

的特征值, 且|(

m

-1)!

λμ

|=(

m

-1)!|

λ

|·|

μ

|≤(

m

-1)!

ρ

(

G

)

ρ

(

H

)=

ρ

(

G

×

H

).

(4)

考慮集合

S

∶={|(

m

-1)!

λμ

|=

ρ

(

G

×

H

)∶

λ

∈Spec(

G

),

μ

∈Spec(

H

)}.若|(

m

-1)!

λμ

|=

ρ

(

G

×

H

), 根據(jù)式(4), |

λ

|=

ρ

(

G

)且|

μ

|=

ρ

(

H

). 根據(jù)定理3,可得

設(shè)

|

S

|=|

S

·

S

|=∶

β

,

[

c

(

G

),

c

(

H

)]|

β

.

(5)

因為

c

(

G

)·

c

(

H

)=[

c

(

G

),

c

(

H

)]·(

c

(

G

),

c

(

H

)), 其中(

a

,

b

)記正整數(shù)

a

,

b

的最大公約數(shù), 故

S

·

S

的任一個元素都可以表示為

β

|[

c

(

G

),

c

(

H

)]，

(6)

推論1

設(shè)

G

和

H

為兩個連通的

m

-一致超圖, 且

G

×

H

連通. 如果

c

(

G

)=

m

或者

c

(

H

)=

m

, 則

c

(

G

×

H

)=

m

.

證明

根據(jù)引理2,

c

(

G

)|

m

且

c

(

H

)|

m

. 如果

c

(

G

)=

m

或者

c

(

H

)=

m

, 則[

c

(

G

),

c

(

H

)]=

m

. 根據(jù)定理4, [

c

(

G

),

c

(

H

)]|

c

(

G

×

H

), 從而

m

|

c

(

G

×

H

). 而根據(jù)引理2,

c

(

G

×

H

)|

m

, 故結(jié)論成立.

推論2

設(shè)

G

為連通

m

-一致超圖,

e

為僅由有一條邊構(gòu)成的

m

-一致超圖, 且

G

×

e

連通. 則

c

(

G

×

e

)=

m

.

證明

根據(jù)文獻(xiàn)[3]或[10]的結(jié)論,

c

(

e

)=

m

. 故根據(jù)推論1, 結(jié)論成立.在定理4及推論1和2中, 如果

m

≥3, 根據(jù)引理3, 顯然

G

×

H

或

G

×

e

連通. 在推論2中, 當(dāng)

m

=2, 即

G

為連通簡單圖, 并且假設(shè)

G

為非二部圖, 則根據(jù)文獻(xiàn)[19]的結(jié)論,

G

×

e

連通, 此時

G

×

e

也是

G

的雙覆蓋(double cover). 根據(jù)推論2,

c

(

G

×

e

)=2, 從而根據(jù)非負(fù)矩陣的Perron-Frobenius定理,

G

×

e

為二部圖.