三圈圖的(2,2)-可選性的證明

摘要：

每一個(gè)圖是 （2，2）-可選的猜想迄今未被解決，為了推動(dòng)（2，2）-可選猜想的證明，利用積和指數(shù)的方法證明了所有三圈圖是 （2，2）-可選的。

關(guān)鍵詞：

列表分配；總賦權(quán)可選性；積和指數(shù)；三圈圖

中圖分類號(hào)：O157.5

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：10061037（2024）03000108

doi：10.3969/j.issn.10061037.2024.03.01

收稿日期：2024-03-08

基金項(xiàng)目：

國(guó)家自然科學(xué)基金（批準(zhǔn)號(hào)：12261071）資助；青海省自然科學(xué)基金（批準(zhǔn)號(hào)：2020-ZJ-920）資助。

通信作者：

吳廷增，男，博士，教授，主要研究方向?yàn)閳D論與組合優(yōu)化、復(fù)雜網(wǎng)絡(luò)與數(shù)據(jù)科學(xué)。E-mail：mathzwu@163.com

1" 引言及預(yù)備知識(shí)

令圖G=（V，E）是一個(gè)有n個(gè)頂點(diǎn)m條邊的簡(jiǎn)單圖，如果m=n+2，則稱連通圖 G是一個(gè)三圈圖，設(shè)Gn，n+2是所有三圈圖構(gòu)成的集合。本文中采用常用的圖論定義與符號(hào)參見(jiàn)相關(guān)文獻(xiàn)［1］。

圖 G的總賦權(quán)是一個(gè)映射f：V∪E→R ，給每一個(gè)頂點(diǎn)及每一條邊賦予一個(gè)實(shí)數(shù)作為權(quán)重。對(duì)于一個(gè)總賦權(quán)f，用s（v）=f（v）+∑e∈E（v）f（e） 表示點(diǎn)v∈V（G）的權(quán)重，其中，E（v） 表示與點(diǎn)v相鄰的邊的集合。如果對(duì)于任意兩個(gè)不同頂點(diǎn)u，v∈V（G）有s（u）≠s（v），則稱總賦權(quán)f是正常的。

（k，k′）-可選性于2011年提出。令ψ：V∪E→

瘙 綃 +，圖 G的ψ- 列表分配是一個(gè)映射 L，給每一個(gè)z∈V∪E賦予 ψ（z）個(gè)實(shí)數(shù)組成集合 L（z）［2-3］。給定一個(gè)列表分配 L，如果對(duì)于所有 z∈V∪E有 ψ（z）∈L（z）個(gè)正常的總賦權(quán)ψ，則稱為正常的 L-總賦權(quán)。如果對(duì)于任意的列表分配 L，存在 G的正常 L-總賦權(quán)，則稱 G是ψ-可選的，此時(shí)對(duì)于v∈V（G）有ψ（v）∈k并且對(duì)于e∈E（G）有 ψ（e）=k′，則稱G是（k，k′）-可選的。圖 G的指數(shù)函數(shù)是一個(gè)映射η，給 G的每一個(gè)頂點(diǎn)和邊z指定一個(gè)非負(fù)整數(shù)η（z）。如果指數(shù)函數(shù)η滿足∑z∈V（G）∪E（G）η（z）=|E（G）|，稱 η是有效的。如果存在有效的指數(shù)函數(shù)η′≤η滿足per（AG（η′））≠0，則指數(shù)函數(shù)η是非奇異的。Wong等［3］首先考慮了圖的 （k，k′）-可選性，并提出猜想1。

猜想 1［3］" 每一個(gè)圖都是 （2， 2）-可選的。

猜想 1雖然受到了廣泛的關(guān)注，但沒(méi)有被證明。目前僅證明了一些特殊的圖是（2，2）-可選的［3-4］，如，樹(shù)、完全圖、子立方圖、2-樹(shù)、哈林圖及網(wǎng)格圖等。

設(shè)A=［aij］是n×n階矩陣，其中i，j∈{1，2，…，n}，則per（A）=∑σ∏ni=1aiσ（i）為矩陣 A的積和式，求和遍及{1，2，…，n}的n！置換σ。矩陣 A的積和指數(shù)記為pind（A），即對(duì)于最小的 k使得存在一個(gè)矩陣A′，有per（A′）≠0，A′的每列都是矩陣 A中的列并且 A中的每一列在A′中至多出現(xiàn) k次。在文獻(xiàn)［3］和文獻(xiàn)［5］中已證明對(duì)于G的一個(gè)有效的指數(shù)函數(shù)η，cη≠0當(dāng)且僅當(dāng)per（AG（η））≠0。所以pind（AG）=1，則G是（2，2）-可選的。文獻(xiàn)［3］基于此修訂了猜想 1，提出猜想2。

猜想 2［3］" 對(duì)于任意一個(gè)圖G，pind（AG）=1。

針對(duì)猜想2，使用積和指數(shù)的方法，本文證明了所有的三圈圖是（2，2）-可選的。

定理 1" 令G∈gn，n+2則pind（AG）=1，即G是（2，2）-可選的。

2" 定理1相關(guān)的定義與引理

為了證明定理1，首先介紹一些定義與引理。

青島大學(xué)學(xué)報(bào)（自然科學(xué)版）第37卷

第3期""" 馬" 雙等：三圈圖的（2，2）-可選性的證明

所有三圈圖是由15類非同構(gòu)的母圖Gi（圖1）生成，即每個(gè)三圈圖必以Gi作為導(dǎo)出子圖［6］，以Gi作為導(dǎo)出子圖的所有三圈圖記為gin，n+2。因此，有g(shù)n，n+2=∪15i=1gin，n+2。

圖1" 三圈圖Gi

引理1［4］" 如果有效的指數(shù)函數(shù)η≡1是非奇異的，則pind（AG）=1，即G是（2，2）-可選的。

引理2［4］" 假設(shè)G是一個(gè)圖，η是 G的指數(shù)函數(shù)滿足對(duì)于所有的邊 e，有η（e）=1，并且X是V（G）的一個(gè)子集。令G′=G-E［X］是由G通過(guò)刪除G［X］中的邊得到的。令 D是G′的無(wú)圈定向，并且對(duì)于每一個(gè)v∈V（D）是一個(gè)接收點(diǎn)（出度為 0的點(diǎn)）。假設(shè) D′是 D的子有向圖使得對(duì)于每一個(gè)v∈V（D），有η（v）+2d-D′（v）-d-D（v）≥d+D′（v）。

令η′是一個(gè)指數(shù)函數(shù)，約定η′（e）=1，對(duì)于每條在G［X］中的邊e并且對(duì)于v∈X，η′（v）=η（v）+2d-D′（v）-d-D（v）。如果η′是圖G［X］的非奇異指數(shù)函數(shù)，則η是圖G的非奇異指數(shù)函數(shù)。

引理3［3］" 令G是由G′通過(guò)增加一個(gè)頂點(diǎn)v和一條邊e*=uv得到的，其中u是G的頂點(diǎn)。如果pind（AG′）=1，則pind（AG）=1。如果G′是（2，2）-可選的，則G是（2，2）-可選的。

3" 定理1的證明

根據(jù)引理3，通過(guò)在三圈圖的15類母圖上增加樹(shù)或星，若15類母圖是（2，2）-可選的，則三圈圖就是（2，2）-可選的。因此只需要證明定理1對(duì)于Gi（i=1，2，…，15）成立即可。分為15種情況考慮。

情況1" 為G1構(gòu)造一個(gè)無(wú)圈定向：對(duì)于包含頂點(diǎn)vt的圈，除了將邊vtv1從vt到v1定向，其他邊均逆時(shí)針定向；對(duì)于包含頂點(diǎn)vs的圈，除了將邊vsv1從vs到v1定向，其他邊均順時(shí)針定向；對(duì)于包含頂點(diǎn)v2的圈，除了將邊v2v1從v2到v1定向，其他邊均逆時(shí)針定向，由此形成了有向圖D。令D′是由邊vtv1，vsv1，v2v1所組成的D的子圖，易知v1是D中一個(gè)接收點(diǎn)。令η≡1是一個(gè)連續(xù)函數(shù)，X={v1并且η′（v1）=0是G［X］的一個(gè)指數(shù)函數(shù)，則η′是G［X］的一個(gè)非奇異指數(shù)函數(shù)。為證明pind（AG）=1，即η是 G的非奇異指數(shù)函數(shù)，根據(jù)引理2，只需證明G1中的每一個(gè)點(diǎn) v滿足：1+2d-D′（v）-d-D（v）≥d+D′（v）即可。因此，分3種子情況考慮。

子情況1：v= v1，則d-D′（v）=3，d-D（v）=6，d+D′（v）=0，因此1+2d-D′（v）-d-D（v）=1≥d+D′（v）。

子情況2：v= v2，vs，vt，則d-D′（v）=0，d-D（v）=0，d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=1≥d+D′（v）。

子情況3：v∈G＼{v1，v2，vs，vt}，則d-D′（v）=0，d-D（v）=1，d+D′（v）=0，因此1+2d-D′（v）-d-D（v）=0≥d+D′（v）。

根據(jù)引理1，pind（AG1）=1，即G1是（2，2）-可選的。

情況2" 為G2構(gòu)造一個(gè)無(wú)圈定向：對(duì)于包含頂點(diǎn)vg的圈，除了將邊vgvj從vg到vj定向，其他邊均逆時(shí)針定向；對(duì)于包含頂點(diǎn)vs的圈，除了將邊vsv1從vs到v1定向，其他邊均逆時(shí)針定向；對(duì)于包含頂點(diǎn)vn的圈，除了將邊vnv1從vn到v1定向，其他邊均逆時(shí)針定向；對(duì)于 vj，v1-路，從上到下定向，由此形成了有向圖D。令D′是由邊vsv1，vgvj，vnv1所組成的D的子圖，易知v1是D中一個(gè)接收點(diǎn)。令η≡1是一個(gè)連續(xù)函數(shù)，X={v1并且η′（v1）=0是G［X］的一個(gè)指數(shù)函數(shù)，則η′是G［X］的一個(gè)非奇異指數(shù)函數(shù)。為了證明pind（AG）=1，即η是G的非奇異指數(shù)函數(shù)，根據(jù)引理2，只需證明G2中的每一個(gè)點(diǎn) v滿足：1+2d-D′（v）-d-D（v）≥d+D′（v）即可。因此，分 4種子情況考慮。

子情況1：v= v1，則d-D′（v）=2，d-D（v）=5，d+D′（v）=0，因此1+2d-D′（v）-d-D（v）=0≥d+D′（v）。

子情況2：v= vj，則d-D′（v）=1，d-D（v）=2，d+D′（v）=0，因此1+2d-D′（v）-d-D（v）=1≥d+D′（v）。

子情況3：v= vg，vs，vn，則d-D′（v）=0，d-D（v）=0，d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=1≥d+D′（v）。

子情況4：v∈G＼{v1，vg，vs，vj，vn}，則d-D′（v）=0，d-D（v）=1，d+D′（v）=0，因此1+2d-D′（v）-d-D（v）=0≥d+D′（v）。

根據(jù)引理1，pind（AG2）=1，即G2是（2，2）-可選的。

情況3" 為G3構(gòu)造一個(gè)無(wú)圈定向：對(duì)于包含頂點(diǎn)v2的圈，除了將邊v2v1從v2到v1定向，其他邊均逆時(shí)針定向；對(duì)于包含頂點(diǎn)vj的圈，除了將邊vjv1從vj到v1定向，其他邊均順時(shí)針定向；對(duì)于包含頂點(diǎn)vt的圈，除了將邊vtvm從vt到vm定向，其他邊均順時(shí)針定向，由此形成了有向圖D。令D′是由邊v2v1，vjv1，vtvm所組成的D的子圖，易知v1是D中一個(gè)接收點(diǎn)。令η≡1是一個(gè)連續(xù)函數(shù)，X={v1并且η′（v1）=0是 G［X］的一個(gè)指數(shù)函數(shù)，則η′是G［X］的一個(gè)非奇異指數(shù)函數(shù)。為了證明pind（AG）=1，即η是G的非奇異指數(shù)函數(shù)，根據(jù)引理2，只需證明G3中的每一個(gè)點(diǎn) v滿足：1+2d-D′（v）-d-D（v）≥d+D′（v）即可。因此，分4種子情況考慮。

子情況1：v=" v1，則 d-D′（v）=2，d-D（v）=4，d+D′（v）=0，因此1+2d-D′（v）-d-D（v）=1≥d+D′（v）。

子情況2：v=" vm，則d-D′（v）=1，d-D（v）=3，d+D′（v）=0，因此1+2d-D′（v）-d-D（v）=0≥d+D′（v）。

子情況3：v=" vj，vt，v2，則d-D′（v）= d-D（v）=0，d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=1≥d+D′（v）。

子情況4：v∈G＼{v1，v2，vt，vj，vm}，則d-D′（v）=0，d-D（v）=1，d+D′（v）=0，因此1+2d-D′（v）-d-D（v）=0≥d+D′（v）。

根據(jù)引理1，pind（AG3）=1，即G3是（2，2）-可選的。

情況4" 為G4構(gòu)造一個(gè)無(wú)圈定向：對(duì)于包含頂點(diǎn)vz的圈，除了將邊vzvg從vz到vg定向，其他邊均順時(shí)針定向；對(duì)于包含頂點(diǎn)v2的圈，除了將邊v2v1從v2到v1定向，其他邊均逆時(shí)針定向；對(duì)于包含頂點(diǎn)vt的圈，除了將邊vtv1從vt到v1定向，其他邊均順時(shí)針定向；對(duì)于 vg，vm-路從上到下定向，由此形成了有向圖D。令D′是由邊vzvg，vtv1，v2v1所組成的D的子圖，易知v1是D中一個(gè)接收點(diǎn)。令η≡1是一個(gè)連續(xù)函數(shù)，X={v1并且η′（v1）=0是G［X］的一個(gè)指數(shù)函數(shù)，則η′是G［X］的一個(gè)非奇異指數(shù)函數(shù)。為了證明pind（AG）=1，即η是 G的非奇異指數(shù)函數(shù)，根據(jù)引理2，只需證明G4中的每一個(gè)點(diǎn) v滿足：1+2d-D′（v）-d-D（v）≥d+D′（v）即可。因此，分 4種子情況考慮。

子情況1：v= v1，則d-D′（v）=2，d-D（v）=4，d+D′（v）=0，因此1+2d-D′v-d-D（v）=1≥d+D′（v）。

子情況2：v= vg，則d-D′（v）=1，d-D（v）=2，d+D′（v）=0，因此1+2d-D′（v）-d-D（v）=1≥d+D′（v）。

子情況3：v= vz，vt，v2，則d-D′（v）= d-D（v）=0，d+D′（v）=1，因此1+2d-D′v-d-D（v）=1≥d+D′（v）。

子情況4：v∈G＼{v1，v2，vg，vt，vz}，則d-D′（v）=0，d-D（v）=1，d+D′（v）=0。因此1+2d-D′（v）-d-D（v）=0≥d+D′（v）。

根據(jù)引理1，pind（AG4）=1，即G4是 （2，2）-可選的。

情況5" 為G5構(gòu)造一個(gè)無(wú)圈定向：對(duì)于包含頂點(diǎn)v2的圈，除了將邊v2v1從v2到v1定向，其他邊均順時(shí)針定向；對(duì)于包含頂點(diǎn)vm+1的圈，除了將邊vm+1vm從vm+1到vm定向， 其他邊均順時(shí)針定向；對(duì)于包含頂點(diǎn)vs+1的圈，除了將邊vs+1vs從vs+1到vs定向，其他邊均順時(shí)針定向；對(duì)于 v1，vm-路從上到下定向；對(duì)于 vm，vs-路從左到右定向，由此形成了有向圖D。令D′是由邊vm+1vm，vs+1vs，v2v1所組成的D的子圖，易知vs是D中一個(gè)接收點(diǎn)。令η≡1是一個(gè)連續(xù)函數(shù)，X={vs并且η′（vs）=0是G［X］的一個(gè)指數(shù)函數(shù)，則η′是G［X］的一個(gè)非奇異指數(shù)函數(shù)。為了證明pind（AG）=1，即η是 G的非奇異指數(shù)函數(shù)，只需證明G5中的每一個(gè)點(diǎn) v滿足：1+2d-D′（v）-d-D（v）≥d+D′（v）即可。因此，分 4種子情況考慮。

子情況1：v= vs，則d-D′（v）=1，d-D（v）=3，d+D′（v）=0，因此1+2d-D′（v）-d-D（v）=0≥d+D′（v）。

子情況2：v= v1，則d-D′（v）=1，d-D（v）=2，d+D′（v）=0，因此1+2d-D′（v）-d-D（v））=1≥d+D′（v）。

子情況3：v= vs+1，vm+1，v2，則d-D′（v）= d-D（v）=0，d+D′（v）=1，因此1+2d-D′（v）-d-D（v））=1≥d+D′（v）。

子情況4：v∈G＼{v1，v2，vs，vs+1，vm+1}，則d-D′（v）=0，d-D（v）=1，d+D′（v）=0。因此1+2d-D′（v）-d-D（v）=0≥d+D′（v）。

根據(jù)引理1，pind（AG5）=1，即G5是（2，2）-可選的。

情況6" 為G6構(gòu)造一個(gè)無(wú)圈定向：對(duì)于包含頂點(diǎn)vm+1的圈，除了將邊vm+1vm從vm+1到vm定向，其他邊均逆時(shí)針定向；對(duì)于包含頂點(diǎn)vt+1的圈，除了將邊vt+1vt從vt+1到vt定向，其他邊均順時(shí)針定向；對(duì)于包含頂點(diǎn)v2的圈，除了將邊v2v1從v2到v1定向，其他邊均逆時(shí)針定向；對(duì)于 vm，vs-路從上到下定向；對(duì)于 v1，vt-路從左到右定向，由此形成了有向圖D。令D′是由邊vm+1vm，vt+1vt和包含頂點(diǎn)v1，vs的v2，vt-路所組成的D的子圖，易知vt是D中一個(gè)接收點(diǎn)。令η≡1是一個(gè)連續(xù)函數(shù)，X={vt并且η′（vt）=0是G［X］的一個(gè)指數(shù)函數(shù)，則η′是G［X］的一個(gè)非奇異指數(shù)函數(shù)。為了證明pind（AG）=1，即η是G的非奇異指數(shù)函數(shù)，根據(jù)引理2，只需證明對(duì)于G6中的每一個(gè)點(diǎn) v滿足：1+2d-D′（v）-d-D（v）≥d+D′（v）即可。因此，分 6種子情況考慮。

子情況1：v= vt，則 d-D′（v）=2，d-D（v）=3，d+D′（v）=0，因此1+2d-D′（v）-d-D（v）=2≥d+D′（v）。

子情況2：v= vm，則d-D′（v）=1，d-D（v）=2，d+D′（v）=0，因此1+2d-D′（v）-d-D（v）=1≥d+D′（v）。

子情況3：v= vt+1，vm+1，v2，則d-D′（v）= d-D（v）=0，d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=1≥d+D′（v）。

子情況4：v= v1，vs，則d-D′（v）=1，d-D（v）=2，d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=1≥d+D′（v））。

子情況5：v∈v1，vt-路＼{v1，vt，vs}，則d-D′（v）= d-D（v）= d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=2≥d+D′（v）。

子情況6：v∈G＼{vt+1，vm，vm+1和v2，vt-路}，則d-D′（v）=0，d-D（v）=1，d+D′（v）=0。因此1+2d-D′（v）-d-D（v）=0≥d+D′（v）。

根據(jù)引理1，pind（AG6）=1，即G6是（2，2）-可選的。

情況7" 為G7構(gòu)造一個(gè)無(wú)圈定向：對(duì)于包含頂點(diǎn)vg的圈，除了將不包含頂點(diǎn)vg的vm，vt-路從vm到vt定向，其他邊均逆時(shí)針定向；對(duì)于包含頂點(diǎn)v2的圈，除了將邊v2v1從v2到v1定向，其他邊均逆時(shí)針定向；對(duì)于包含頂點(diǎn)vs+1的圈，除了將邊vs+1vs從vs+1到vs定向，其他邊均順時(shí)針定向；對(duì)于 vm，v1-路從上到下定向；對(duì)于 vt，vs-路從左到右定向，由此形成了有向圖D。令D′是由邊vs+1vs，v2v1和包含頂點(diǎn)vm，vt但不包含頂點(diǎn)vg的v1，vs-路所組成的D的子圖，易知vs是D中一個(gè)接收點(diǎn)。令η≡1是一個(gè)連續(xù)函數(shù)，X={vs并且η′（vs）=0是G［X］的一個(gè)指數(shù)函數(shù)，則η′是G［X］的一個(gè)非奇異指數(shù)函數(shù)。為了證明pind（AG）=1，也就是說(shuō)，η是 G的非奇異指數(shù)函數(shù)，根據(jù)引理2，只需證明G7中的每一個(gè)點(diǎn) v滿足：1+2d-D′（v）-d-D（v）≥d+D′（v）即可。因此，分 6種子情況考慮。

子情況1：v= vs，則 d-D′（v）=2，d-D（v）=3，d+D′（v）=0，因此1+2d-D′（v）-d-D（v）=2≥d+D′（v）。

子情況2：v= vm，則d-D′（v）= d-D（v）= d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=2≥d+D′（v）。

子情況3：v= vs+1，v2，則d-D′（v）= d-D（v）=0，d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=1≥d+D′（v）。

子情況4：v= v1，vt，則d-D′（v）=1，d-D（v）=2，d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=1≥d+D′（v）。

子情況5：v∈v1，vs-路＼{v1，vt，vs，vm}，則d-D′（v）= d-D（v）= d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=2≥d+D′（v）。

子情況6：v∈G＼{vt+1，vs，vs+1和v2，vt-路}，則d-D′（v）=0，d-D（v）=1，d+D′（v）=0。因此1+2d-D′（v）-d-D（v）=0≥d+D′（v）。

根據(jù)引理1，pind（AG7）=1，即G7是（2，2）-可選的。

情況8" 為G8構(gòu)造一個(gè)無(wú)圈定向：對(duì)于包含頂點(diǎn)vm+1的圈，除了將邊vm+1vm從vm+1到vm定向，其他邊均順時(shí)針定向；對(duì)于包含頂點(diǎn)v2，vl的圈，除了將邊v2v1從v2到v1定向，邊vlvm從vl到vm定向，其他邊均順時(shí)針定向；對(duì)于包含頂點(diǎn)vt的vm，v1-路從vm到v1定向，由此形成了有向圖D。令D′是由邊vm+1vm，v2v1，vlvm和包含頂點(diǎn)vt的vm，v1-路所組成的D的子圖，易知v1是D中一個(gè)接收點(diǎn)。令η≡1是一個(gè)連續(xù)函數(shù)，X={v1并且η′（v1）=0是G［X］的一個(gè)指數(shù)函數(shù)，則η′是G［X］的一個(gè)非奇異指數(shù)函數(shù)。為了證明pind（AG）=1，也就是說(shuō)，η是G的非奇異指數(shù)函數(shù)，根據(jù)引理2，只需證明G8中的每一個(gè)點(diǎn) v滿足：1+2d-D′（v）-d-D（v）≥d+D′（v）即可。因此，分 5種子情況考慮。

子情況1：v= v1，則 d-D′（v）=2，d-D（v）=3，d+D′（v）=0，因此1+2d-D′（v）-d-D（v）=2≥d+D′（v）。

子情況2：v= vm，則d-D′（v）=2，d-D（v）=4，d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=1≥d+D′（v）。

子情況3：v= vm+1，v2，vl，則d-D′（v）= d-D（v）=0，d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=1≥d+D′（v）。

子情況4：v∈v1，vm-路＼{v1，vm}，則d-D′（v）= d-D（v）= d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=2≥d+D′（v）。

子情況5：v∈G＼{v2，vl和vm+1，v1-路}，則d-D′（v）=0，d-D（v）=1，d+D′（v）=0。因此1+2d-D′（v）-d-D（v）=0≥d+D′（v）。

根據(jù)引理1，pind（AG8）=1，即G8是（2，2）-可選的。

情況9" 為G9構(gòu)造一個(gè)無(wú)圈定向：對(duì)于包含頂點(diǎn)vs+1的圈，除了將邊vs+1vs從vs+1到vs定向，其他邊均順時(shí)針定向；對(duì)于包含頂點(diǎn)v2，vs的圈，除了將邊v2v1從v2到v1定向，vs，vh-路從vs到vh定向，其他邊均逆時(shí)針定向；對(duì)于包含頂點(diǎn)vg的vh，v1-路，從vh到v1定向，由此形成有向圖D。令D′是由邊vs+1vs，v2v1和包含頂點(diǎn)vg，vh的vs，v1-路所組成的D的子圖，則v1是D中一個(gè)接收點(diǎn)。令η≡1是一個(gè)連續(xù)函數(shù)，X={v1并且η′（v1）=0是G［X］的一個(gè)指數(shù)函數(shù)，則η′是G［X］的一個(gè)非奇異指數(shù)函數(shù)。為證明pind（AG）=1，即η是G的非奇異指數(shù)函數(shù)，根據(jù)引理2，只需證明G9中的每一個(gè)點(diǎn) v滿足：1+2d-D′（v）-d-D（v）≥d+D′（v）即可。因此，分 5種子情況考慮。

子情況1：v= v1，則d-D′（v）=2，d-D（v）=3，d+D′（v）=0，因此1+2d-D′（v）-d-D（v）=2≥d+D′（v）。

子情況2：v= vs，vh，則d-D′（v）=1，d-D（v）=2，d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=1≥d+D′（v）。

子情況3：v= vs+1，v2，則d-D′（v）= d-D（v）=0，d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=1≥d+D′（v）。

子情況4：v∈v1，vs-路＼{v1，vs，vh}，則d-D′（v）= d-D（v）= d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=2≥d+D′（v）。

子情況5：v∈G＼{v2和vs+1，v1-路}，則d-D′（v）=0，d-D（v）=1，d+D′（v）=0。因此1+2d-D′（v）-d-D（v）=0≥d+D′（v）。

根據(jù)引理1，pind（AG9）=1，即G9是 （2，2）-可選的。

情況10" 為G10構(gòu)造一個(gè)無(wú)圈定向：對(duì)于包含頂點(diǎn)vs+1的圈，除了將邊vs+1vs從vs+1到vs定向，其他邊均順時(shí)針定向；對(duì)于包含頂點(diǎn)v2，vm+1的圈，除了將邊v2v1從v2到v1定向，邊vm+1vm從vm+1到vm定向，其他邊均順時(shí)針定向；對(duì)于包含頂點(diǎn)vh的vm，v1-路從vm到v1定向；對(duì)于 vs，vm-路從vs到vm定向，由此形成了有向圖D。令D′是由邊vm+1vm，v2v1和包含頂點(diǎn)vm，vh，vs的v1，vs+1-路所組成的D的子圖，則v1是D中一個(gè)接收點(diǎn)。令η≡1是一個(gè)連續(xù)函數(shù)，X={v1并且η′（v1）=0是G［X］的一個(gè)指數(shù)函數(shù)，則η′是G［X］的一個(gè)非奇異指數(shù)函數(shù)。為證明pind（AG）=1，即η是 G的非奇異指數(shù)函數(shù)，根據(jù)引理2，只需證明G10中的每一個(gè)點(diǎn) v滿足：1+2d-D′（v）-d-D（v）≥d+D′（v）即可。因此，分 6種子情況考慮。

子情況1：v= v1，則d-D′（v）=2，d-D（v）=3，d+D′（v）=0，因此1+2d-D′（v）-d-D（v）=2≥d+D′（v）。

子情況2：v= vm，則d-D′（v）=2，d-D（v）=3，d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=2≥d+D′（v）。

子情況3：v= vs+1，vm+1，v2，則d-D′（v）= d-D（v）=0，d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=1≥d+D′（v）。

子情況4：v= vs，則d-D′（v）=1，d-D（v）=2，d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=1≥d+D′（v）。

子情況5：v∈v1，vs+1-路＼{v1，vs+1，vs，vm}，則d-D′（v）= d-D（v）= d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=2≥d+D′（v）。

子情況6：v∈G＼{vm+1，v2和vs+1，v1-路}，則d-D′（v）=0，d-D（v）=1，d+D′（v）=0。因此1+2d-D′（v）-d-D（v）=0≥d+D′（v）。

根據(jù)引理1，pind（AG10）=1，即G10是（2，2）-可選的。

情況11" 為G11構(gòu)造一個(gè)無(wú)圈定向：對(duì)于包含頂點(diǎn)vm+1的圈，除了將邊vm+1vm從vm+1到vm定向，其他邊均逆時(shí)針定向；對(duì)于包含頂點(diǎn)v2，vs的圈，除了將邊v2v1從v2到v1定向，vs，vg-路從vs到vg定向，其他邊均逆時(shí)針定向；對(duì)于包含頂點(diǎn)vt的vg，v1-路從vg到v1定向；對(duì)于vm，vs-路從vm到vs定向，由此形成了有向圖D。令D′是由邊vm+1vm，v2v1和包含頂點(diǎn)vg，vt，vs的vm，v1-路所組成的D的子圖，易知v1是D中一個(gè)接收點(diǎn)。令η≡1是一個(gè)連續(xù)函數(shù)，X={v1并且η′（v1）=0是G［X］的一個(gè)指數(shù)函數(shù)，則η′是G［X］的一個(gè)非奇異指數(shù)函數(shù)。為證明pind（AG）=1，即η是G的非奇異指數(shù)函數(shù)，根據(jù)引理2，只需證明G11中的每一個(gè)點(diǎn) v滿足：1+2d-D′（v）-d-D（v）≥d+D′（v）即可。因此，分5種子情況考慮。

子情況1：v= v1，則 d-D′（v）=2，d-D（v）=3，d+D′（v）=0，因此1+2d-D′（v）-d-D（v）=2≥d+D′（v）。

子情況2：v= vm，vg，則d-D′（v）=1，d-D（v）=2，d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=1≥d+D′（v）。

子情況3：v= vm+1，v2，則d-D′（v）= d-D（v）=0，d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=1≥d+D′（v）。

子情況4：v∈v1，vm+1-路＼{v1，vs，vg，vm，vm+1}，則d-D′（v）= d-D（v）= d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=2≥d+D′（v）。

子情況5：v∈G＼{v2和vm+1，v1-路}，則d-D′（v）=0，d-D（v）=1，d+D′（v）=0。因此1+2d-D′（v）-d-D（v）=0≥d+D′（v）。

根據(jù)引理1，pind（AG11）=1，即G11是（2，2）-可選的。

情況12" 為G12構(gòu)造一個(gè)無(wú)圈定向：對(duì)于包含頂點(diǎn)vg+1，vt-1，v2的圈，除了將邊v2v1從v2到v1定向，包含頂點(diǎn)vt-1，vg的vg+1，vt-路從vg+1到vt定向，其他邊均順時(shí)針定向；對(duì)于包含頂點(diǎn)vm的vg，vt-路，分別將邊vmvt從vm到vt定向，將vm，vg-路從vm到vg定向;對(duì)于包含頂點(diǎn)vh的vt，v1-路從vt到v1定向，由此形成了有向圖D。令D′是由邊vmvt，v2v1和包含頂點(diǎn)vt-1，vg但不包含頂點(diǎn)vm的vg+1，vt-路所組成的D的子圖，可知v1是D中一個(gè)接收點(diǎn)。令η≡1是一個(gè)連續(xù)函數(shù)，X={v1并且η′（v1）=0是G［X］的一個(gè)指數(shù)函數(shù)，則η′是G［X］的一個(gè)非奇異指數(shù)函數(shù)。為了證明pind（AG）=1，即η是G的非奇異指數(shù)函數(shù)，根據(jù)引理2，只需證明G12中的每一個(gè)點(diǎn) v滿足：1+2d-D′（v）-d-D（v）≥d+D′（v）即可。因此，分 6種子情況考慮。

子情況1：v= v1，則 d-D′（v）=1，d-D（v）=3，d+D′（v）=0，因此1+2d-D′（v）-d-D（v）=0≥d+D′（v）。

子情況2：v= vg，則d-D′（v）=1，d-D（v）=2，d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=1≥d+D′（v）。

子情況3：v= vg+1，vm，v2，則d-D′（v）= d-D（v）=0，d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=1≥d+D′（v）。

子情況4：v= vt，則d-D′（v）=2，d-D（v）=3，d+D′（v）=0，因此1+2d-D′（v）-d-D（v）=2≥d+D′（v）。

子情況5：v∈vt，vg+1-路＼{vg+1，vg，vt}，則d-D′（v）= d-D（v）= d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=2≥d+D′（v）。

子情況6：v∈G＼{v1，v2，vm和vg+1，vt-路}，則d-D′（v）=0，d-D（v）=1，d+D′（v）=0。因此1+2d-D′（v）-d-D（v）=0≥d+D′（v）。

根據(jù)引理1，pind（AG12）=1，即G12是（2，2）-可選的。

情況13" 為G13構(gòu)造一個(gè)無(wú)圈定向：對(duì)于包含頂點(diǎn)vg，vm，v1的圈，除了包含頂點(diǎn)vt的vg，v1-路從vg到v1定向，其他邊均逆時(shí)針定向；對(duì)于包含頂點(diǎn)vs+1的vs，vt-路，分別將邊vs+1vs從vs+1到vs定向，將vs+1，vt-路從vs+1到vt定向；對(duì)于包含頂點(diǎn)v2的v1，vm-路，將邊v2v1從v2到v1定向，將v2，vm-路從v2到vm定向，由此形成有向圖D。令D′是由邊vgvt，v2v1，vsvs+1和包含頂點(diǎn)vh的vs，vm-路所組成的D的子圖。很容易發(fā)現(xiàn)v1是D中一個(gè)接收點(diǎn)。令η≡1是一個(gè)連續(xù)函數(shù)，X={v1并且η′（v1）=0是G［X］的一個(gè)指數(shù)函數(shù)，則η′是G［X］的一個(gè)非奇異指數(shù)函數(shù)。為了證明pind（AG）=1，即η是 G的非奇異指數(shù)函數(shù)，根據(jù)引理2，只需證明G13中的每一個(gè)點(diǎn) v滿足：1+2d-D′（v）-d-D（v）≥d+D′（v）即可。因此，分 6種子情況考慮。

子情況1：v= v1，則 d-D′（v）=1，d-D（v）=3，d+D′（v）=0，因此1+2d-D′（v）-d-D（v）=0≥d+D′（v）。

子情況2：v= vs，則d-D′（v）=1，d-D（v）=2，d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=1≥d+D′（v）。

子情況3：v= vg，vs+1，v2，則d-D′（v）= d-D（v）=0，d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=1≥d+D′（v）。

子情況4：v= vt，vm，則d-D′（v）=1，d-D（v）=2，d+D′（v）=0，因此1+2d-D′（v）-d-D（v）=1≥d+D′（v）。

子情況5：v∈vs，vm-路＼{vs，vm}，則d-D′（v）= d-D（v）= d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=2≥d+D′（v）。

子情況6：v∈G＼{v1，v2，vg，vt，vs+1和vs，vm-路}，則d-D（v）=1，d-D′（v）= d+D′（v）=0。因此1+2d-D′（v）-d-D（v）=0≥d+D′（v）。

根據(jù)引理1，pind（AG13）=1，即G13是（2，2）-可選的。

情況14" 為G14構(gòu)造一個(gè)無(wú)圈定向：對(duì)于包含頂點(diǎn)vg，vh的圈，除了將邊vgv1從vg到v1定向，其他邊均逆時(shí)針定向；對(duì)于包含頂點(diǎn)vm+1，v2的圈，除了將邊vm+1vm從vm+1到vm定向，邊v2v1從v2到v1定向，其他邊均順時(shí)針定向，由此形成了有向圖D。令D′是由邊vm+1vm，vgv1，v2v1所組成的D的子圖。很容易發(fā)現(xiàn)v1是D中一個(gè)接收點(diǎn)。令η≡1是一個(gè)連續(xù)函數(shù)，X={v1并且η′（v1）=0是G［X］的一個(gè)指數(shù)函數(shù)，則η′是G［X］的一個(gè)非奇異指數(shù)函數(shù)。為了證明pind（AG）=1，即η是G的非奇異指數(shù)函數(shù)，根據(jù)引理2，只需證明G14中的每一個(gè)點(diǎn) v滿足：1+2d-D′（v）-d-D（v）≥d+D′（v）即可。因此，分 4種子情況考慮。

子情況1：v= v1，則 d-D′（v）=2，d-D（v）=4，d+D′（v）=0，因此1+2d-D′（v）-d-D（v）=1≥d+D′（v）。

子情況2：v= vm，則d-D′（v）=1，d-D（v）=3，d+D′（v）=0，因此1+2d-D′（v）-d-D（v）=0≥d+D′（v）。

子情況3：v= vg，vm+1，v2，則d-D′（v）= d-D（v）=0，d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=1≥d+D′（v）。

子情況4：v∈G＼{v1，v2，vg，vm，vm+1}，則d-D′（v）=0，d-D（v）=1，d+D′（v）=0。因此1+2d-D′（v）-d-D（v）=0≥d+D′（v）。

根據(jù)引理1，pind（AG14）=1，即G14是 （2，2）-可選的。

情況15" 為G15構(gòu)造一個(gè)無(wú)圈定向：對(duì)于包含頂點(diǎn)v2，vl，vs的圈，除了邊v2v1從v2到v1定向，其他邊均順時(shí)針定向；對(duì)于包含頂點(diǎn)vh的vm，v1-路從vm到v1定向；對(duì)于包含頂點(diǎn)vs+1的vs，vl-路，將邊vs+1vs從vs+1到vs定向，將vs+1，vl-路從vs+1到vl定向，由此形成了有向圖D。令D′是由邊v2v1，vsvs+1和包含頂點(diǎn)vm的vs，vl-路所組成的D的子圖，易知v1是D中一個(gè)接收點(diǎn)。令η≡1是一個(gè)連續(xù)函數(shù)，X={v1并且η′（v1）=0是G［X］的一個(gè)指數(shù)函數(shù)，則η′是G［X］的一個(gè)非奇異指數(shù)函數(shù)。為證明pind（AG）=1，即η是 G的非奇異指數(shù)函數(shù)，根據(jù)引理2，只需證明G15中的每一個(gè)點(diǎn) v滿足：1+2d-D′（v）-d-D（v）≥d+D′（v）即可。因此，分 6種子情況考慮。

子情況1：v= v1，則d-D′（v）=1，d-D（v）=3，d+D′（v）=0，因此1+2d-D′（v）-d-D（v）=0≥d+D′（v）。

子情況2：v= vl，則d-D′（v）=1，d-D（v）=2，d+D′（v）=0，因此1+2d-D′（v）-d-D（v）=1≥d+D′（v）。

子情況3：v= vs+1，v2，則d-D′v= d-D（v）=0，d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=1≥d+D′（v）。

子情況4：v= vs，則d-D′（v）=1，d-D（v）=2，d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=1≥d+D′（v）。

子情況5：v∈vs，vl-路＼{vs，vl}，則d-D′v= d-D（v）= d+D′（v）=1，因此1+2d-D′（v）-d-D（v）=2≥d+D′（v）。

子情況6：v∈G＼{v1，v2，vs+1和vs，vl-路}，則d-D（v）=1，d-D′（v）= d+D′（v）=0，因此1+2d-D′（v）-d-D（v）=0≥d+D′（v）。

根據(jù)引理1，pind（AG15）=1，即G15是（2，2）-可選的。

綜上所述，三圈圖G是（2，2）-可選的。

參考文獻(xiàn)

［1］BONDY J A， MURTY U S R. Graph theory with applications［M］. London： Macmillan Publishers Limited， 1976.

［2］PRZYBYO J， WOZ＇ NIAK M. Total weight choosability of graphs［J］. The Electronic Journal of Combinatorics， 2011， 18（1）： P112.

［3］WONG T L， ZHU X D. Total weight choosability of graphs［J］. Journal of Graph Theory， 2011， 66（3）： 198-212.

［4］WONG T L， ZHU X D. Permanent index of matrices associated with graphs［J］. The Electronic Journal of Combinatorics， 2017， 24（1）： P1.25.

［5］ALON N， TARSI M. Colorings and orientations of graphs［J］. Combinatorica， 1992， 12： 125-134.

［6］SO W， WU T， L H. Sharp bounds on the permanental sum of a graph［J］. Graphs and Combinatorics， 2021， 37（6）： 2423-2437.

Proof of （2，2）-Choosability of Tricyclic Graphs

MA Shuang， WU Ting-zeng

（School of Mathematics and Statistics， Qinghai Minzu University， Xining 810007， China）

Abstract：

The conjecture that every graph is （2，2）-choosability has so far not been solved. To push （2，2）-choosability proof， the method of permanent index was used to show that all tricyclic graphs are （2，2）-choosability.

Keywords：

list assignment; total weight choosability; permanent index; tricyclic graph