關(guān)于混合圖H-秩的一個(gè)注記

朱佳敏，李雙東，2

（1．安徽大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，安徽 合肥 230601；2．安徽大學(xué)江淮學(xué)院，安徽 合肥 230031）

1 預(yù)備知識(shí)

引理1.1

（1）如果

v

不在

G

的任何圈上，則（2）如果

v

在

G

的一個(gè)圈上，則

c

(

G

-

v

)≤

c

(

G

)-1；（3）如果

G

中包含頂點(diǎn)相交的圈，則存在位于相交圈上的頂點(diǎn)

v

，滿足

c

(

G

-

v

)≤

c

(

G

)-2；（4）如果

G

中的圈兩兩不交，則

c

(

G

)等于

G

中圈的個(gè)數(shù)。

引理1.2

引理1.3

引理1.4

定義1.5

設(shè)

G

是含懸掛點(diǎn)的簡(jiǎn)單圖，將

G

中的懸掛點(diǎn)及其鄰點(diǎn)一起刪除的操作稱為 -

δ

變換。設(shè)

G

是圈互不相交的簡(jiǎn)單圖。對(duì)

G

連續(xù)實(shí)施

δ

-變換，直到得到的子圖不含懸掛點(diǎn)，稱該子圖是

G

的一個(gè)重要子圖。把

G

中的每個(gè)圈都收縮成一個(gè)新的頂點(diǎn)，所得不含圈的圖記作

T

，所有由圈收縮所得頂點(diǎn)構(gòu)成的集合記作

W

。將

G

中所有的圈和與這些圈上頂點(diǎn)相關(guān)聯(lián)的邊刪除，所得不含圈的圖記作[

T

]。

引理1.6

引理1.7

定理1.8

定理1.9

（1）

G

中任意兩個(gè)圈均沒(méi)有公共頂點(diǎn)；

（3）

m

(

T

)=

m

([

T

])，即存在

T

的一個(gè)最大匹配

M

，使得

M

不覆蓋

W

中的點(diǎn)。

引理1.10

注：由上述引理可知，存在H-秩為2

m

(

G

)- 2

c

(

G

), 2

m

(

G

)- 2

c

(

G

)+ 2, 2

m

(

G

)+

c

(

G

)的單圈混合圖，不存在H-秩為2

m

(

G

)- 2

c

(

G

)+1的單圈混合圖。

2 主要結(jié)果

對(duì)于圖

G

的懸掛點(diǎn)，如果其鄰點(diǎn)不在

G

的圈上，則稱該懸掛點(diǎn)是類型1的；否則，稱該懸掛點(diǎn)是類型2的。

引理2.1

（1）如果

u

是類型1的，則

（2）如果

u

是類型2的，則

證明

（2）如果懸掛點(diǎn)

u

是類型2的，則由引理1.1（2），

由引理1.6，

（1）式與定理1.9矛盾，命題得證。

滿足()

cG

k

= 的連通簡(jiǎn)單圖稱為k-圈圖。設(shè)

G

是-

k

圈圖，

G

不含懸掛點(diǎn)的k-圈子圖稱為

G

的基。習(xí)慣上，2-圈圖也稱為雙圈圖。不難發(fā)現(xiàn)，雙圈圖有兩種類型的基：

D

(

p

, ?,

q

)和

θ

(

r

,

s

,

t

)，如圖1所示。設(shè)

C

和

C

是兩個(gè)頂點(diǎn)不相交的圈，路

P

=

v

v

…

v

，

u

∈

V

(

C

)，

v

∈

V

(

C

)。

D

(

p

, ?,

q

)是分別將 和

v

粘合成同一個(gè)頂點(diǎn)，

v

和

v

粘合成同一個(gè)頂點(diǎn)所得的圖。

θ

(

r

,

s

,

t

)是將三條內(nèi)部不相交的路

P

，

P

和

P

的起點(diǎn)和終點(diǎn)分別粘合所得的圖。同樣不難發(fā)現(xiàn)，3-圈圖有8種不同類型的基，記作

T

,...,

T

，如圖2所示。

圖1 雙圈圖的基

圖2 3-圈圖的基

例2.2

引理2.3

情形1

子情形1.2 c()≥3

如果在

G

的圈上存在一點(diǎn)

x

，滿足

x

?

V

(

G

[

C

,

C

])，則

G

-

x

包含兩個(gè)頂點(diǎn)相交的圈

C

和

C

，不滿足定理1.9的條件（1）。否則，

G

中的每個(gè)圈都是

G

[

C

,

C

]的子圖。這意味著

G

[

C

,

C

]包含3-圈圖的基

T

(

j

= 5,…, 8)（見(jiàn)圖2）作為子圖。因而，在

G

的圈上一定存在一個(gè)頂點(diǎn)

x

，使得

G

x

- 中有兩個(gè)頂點(diǎn)相交的圈，不滿足定理1.9的條件（1），該情形得證。

情形2

情形3

易見(jiàn)，

E

(

T

)≠?；否則

G

是由頂點(diǎn)互不相交的圈和孤立點(diǎn)構(gòu)成，

m

(

T

=

m

([

T

])=0，矛盾。進(jìn)一步地，可以斷言：

T

的每個(gè)最大匹配至少覆蓋一個(gè)懸掛點(diǎn)。否則，

T

的直徑路中一定包含一條

M

-增廣路，與引理1.7矛盾。注意到，

G

不含懸掛點(diǎn)，則

T

的懸掛點(diǎn)在

G

中對(duì)應(yīng)一個(gè)懸掛圈，記其中一個(gè)懸掛圈為

C

，記

C

上度為3的頂點(diǎn)為

v

。

子情形3.1

子情形3.2

定理2.4

證明

（2）式與（3）式矛盾，因 此 - 2

c

(

G

)+1，命題得證。

圖3

定理2.5

因?yàn)?p>k

,

k

,

k

是非負(fù)整數(shù)，令

k

=

k

+

k

+

k

，，

l

= 3

k

+2

k

，則

l

可以取[ 0,3

k

]中除1之外的任意整數(shù)，命題得證。