笛卡爾乘積圖P3×Cn的符號(hào)邊控制數(shù)

湯青芽，李向軍

(長(zhǎng)江大學(xué) 信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023)

引言

圖的控制理論是圖論研究的重要組成部分，在系統(tǒng)工程、通信網(wǎng)絡(luò)、計(jì)算機(jī)與社會(huì)網(wǎng)絡(luò)等方面中都有廣泛的應(yīng)用[1]。 經(jīng)典的圖控制理論經(jīng)過(guò)不斷演進(jìn)和拓展，許多新的控制概念被提出和研究。 圖的符號(hào)控制概念由Dnubar[2]在1995年首次提出，近些年來(lái)，符號(hào)控制研究?jī)?nèi)容也越來(lái)越豐富。 各種類型的符號(hào)控制數(shù)得到廣泛的研究，如圖的符號(hào)控制數(shù)[3～6]、圖的符號(hào)邊控制數(shù)[7～12]、圖的符號(hào)全控制數(shù)[13]、圖的符號(hào)圈控制數(shù)[14～16]、圖的符號(hào)星控制數(shù)[17]、圖的F-控制數(shù)[18，19]、圖的符號(hào)邊全控制數(shù)[20，21]等。 關(guān)于圖的符號(hào)邊控制數(shù)，徐保根[7]提出此概念，并給出了符號(hào)邊控制數(shù)的一些特征刻畫。 由于計(jì)算任意圖的符號(hào)邊控制數(shù)是十分困難的，研究某些特殊圖的符號(hào)邊控制數(shù)是很有意義的。 趙凌琪等[10，11]研究了一般正則圖的符號(hào)邊控制數(shù)的上界與下界，李向軍等[22]確定了笛卡爾乘積圖C3×Cn符號(hào)邊控制數(shù)，徐保根等[12]給出了笛卡爾乘積圖P2×Cn的符號(hào)邊控制數(shù)，本文利用圖結(jié)構(gòu)分析方法確定笛卡爾乘積圖P3×Cn的符號(hào)邊控制數(shù)的確切值。

一、預(yù)備知識(shí)

記無(wú)向圖G(V,E),V,E分別是圖G的頂點(diǎn)集和邊集,NG(e)表示圖G中與邊相鄰邊e的集合，NG[e]:=NG(e)∪{e}為邊e的閉鄰域。Cn用表示長(zhǎng)為n的圈，P3表示頂點(diǎn)數(shù)為3的路。 笛卡爾乘積圖G×H表示圖G和圖H的笛卡爾乘積，其頂點(diǎn)集為V(G)×V(H),對(duì)x,y∈V(G),a,b∈V(H),(x,a)與(y,b)相鄰當(dāng)且僅當(dāng)x=y且ab∈E(H)或a=b且xy∈E(G)。 本文只考慮簡(jiǎn)單無(wú)向圖，文中未說(shuō)明符號(hào)和術(shù)語(yǔ)同文獻(xiàn)[23]。

定義1[7]G是一個(gè)非空?qǐng)D，如果存在一個(gè)雙值函數(shù)f:E(G)→{-1,+1}，使得對(duì)任意e∈E(G),均有∑e'∈NG[e]f(e')≥1成立，則稱f為G的一個(gè)符號(hào)邊控制函數(shù)。 圖G的符號(hào)邊控制數(shù)γ's(G)=min{∑e∈E(G)f(e):f為G的一個(gè)符號(hào)邊控制函數(shù)。}

設(shè)G=P3×Cn(n≥4)，把G的頂點(diǎn)集看作3×n點(diǎn)陣，記為{xi,j:i∈{0,1,2}}，j∈{0,1,…，n-1}}，第一坐標(biāo)相同的點(diǎn)導(dǎo)出圖為Cn，第二坐標(biāo)相同頂點(diǎn)導(dǎo)出圖為P3。 根據(jù)笛卡爾乘積圖的定義, 易知G是一個(gè)4-正則圖。 設(shè)f為圖G的一個(gè)符號(hào)邊控制函數(shù)，令E+={e∈E(G)|f(e)=+1}，E-={e∈E(G)|f(e)=-1}，顯然E+∪E-=E(G)，E+∩E-=?。令G1=(V(G),E-)為E-在G中導(dǎo)出子圖，G1中頂點(diǎn)度為dG1(xi,j)。下文論述的頂點(diǎn)度均為G1中頂點(diǎn)度，下標(biāo)運(yùn)算均為模n算法。

二、主要結(jié)論

引理1 對(duì)任意j，φj≤4；若φj=φj+1=4,則,φj+2≤3,φj-1≤3。

下面假設(shè)φj=φj+1,往證φj+2≤3,φj-1≤3 。 因?yàn)閐G1(xi,j)≤2，所以要使φj=4，至少存在某xi,j滿足dG1(xi,j)=2。

若dG1(xi,j)=2，由對(duì)稱性令在E中且與x1,j的關(guān)聯(lián)邊為{x1,j-1xi,j，x1,jx1,j+1}或{x0,jx1,j,x1,jx2,j}或{x0,jx1,j,x,jx2,j}。 由∑e'∈NG[e]f(e')≥1易得當(dāng)與x1,j關(guān)聯(lián)邊為{x0,jx1,j,x,jx2,j}時(shí)φj=4，其余情形φj≥3。此時(shí)dG1(x0,j)=1,dG1(x1,j)=2，dG1(x1,j)=1，所以dG1(x0,j+1)≤1，dG1(x1,j+1)≤1，dG1(x2,j+1)≤1，所以第j+1列所有點(diǎn)的頂點(diǎn)度和為至多為3，即φj+1≤3,與φj+1=4矛盾。

下面假設(shè)dG1(x0,j)=2或dG1(x2,j)=2，由其對(duì)稱性不妨設(shè)為前者，令E-中與x0,j關(guān)聯(lián)的邊為{x0,j-1x0,j，x0,jx0,j+1}、{x0,jx0,j+1，x0,jx1,j}或{x0,j-1x0,j，x0,jx1,j}。因?yàn)椤芿'∈NG[e]f(e')≥1，φj=4，在前兩種情形下有φj+1≤3。 所以E-中與x0,j關(guān)聯(lián)的邊為{x0,j-1x0,j+1，x0,jx1,j}，因?yàn)閐G1(x1,j=1)，所以dG1(x2,j)=1。若φj=4，對(duì)j+1列點(diǎn)頂點(diǎn)度進(jìn)行探究，由已知有dG1(x0,j+1)=1，所以dG1(x1,j+1)≤1。要使φj+1=4，則dG1(x1,j+1)=1，dG1(x2,j+1)=2，又因?yàn)閐G1(x1,j)=1，所以第j列與第j+1列邊集為{x1,jx0,jx0,j+1}∪{x2,jx2,j+1x1,j+1}，此時(shí)φj=φj+1=4。 觀察圖G1的結(jié)構(gòu)(見(jiàn)圖1)，因?yàn)閐G1(x0,j)=2，dG1(x2,j+1)=2,所以dG1(x0,j-1)=0，dG1(x2,j+2)=0,從而有φj-1≤3，φj+2≤3，引理得證。

注：粗線邊、細(xì)線邊分別代表和，下同。

圖1φj=φj+1時(shí)圖G1的局部結(jié)構(gòu)

引理2 若φj=φj+1=4。且φj+2≥3，φj+3≥3,則φj+2=φj+3=3。

證明：由引理1，當(dāng)φj=φj+1=4時(shí)，第j列、j+1列邊集構(gòu)造為{x1,jx0,jx0,j+1}∪{x2,jx2,j+1x1,j+1}。 因?yàn)棣誮=φj+1=4，所以由引理1得φj+3≤3，結(jié)合引理2條件得φj+2=3，所以dG1(x0,j+1)=1，dG1(x1,j+2)=2，dG1(x2,j+2)=0，且x0,j+2的關(guān)聯(lián)邊為{x0,j+2,x1,j+2}，x1,j+2的關(guān)聯(lián)邊為{x0,j+2x1,j+2,x1,j+2x1,j+3}，此時(shí)容易驗(yàn)證φj+3≤3，所以φj+2=φj+3=3。

引理3 對(duì)任意j,φj+φj+1+φj+2+φj+3≤14。

證明：由引理1知φj≤4。 若φj+φj+1+φj+2+φj+3中存在某元素取值至多為2，則φj+φj+1+φj+2+φj+3≤2+4×3=14；若φj+φj+1+φj+2+φj+3中所有元素取值至少為3，又由引理1、引理2得到，φj+φj+1+φj+2+φj+3中至多有兩個(gè)元素取值為4，所以φj+φj+1+φj+2+φj+3≤4+4+3+3=14。

引理4 對(duì)于任意的正整數(shù)n(n≥4)，k(k≥1)當(dāng)n=4k時(shí)，|E-|≤7k;當(dāng)n=4k+1時(shí)，|E-|≤7k+1;當(dāng)n=4k+2時(shí)，|E-|≤7k+3;當(dāng)n=4k+3時(shí)，|E-|≤7k+5。

定理1對(duì)于任意的正整數(shù)n(n≥4)，整數(shù)k(k≥1)，當(dāng)n=4k時(shí)，γ's(G)=6k;當(dāng)n=4k+1時(shí)，γ's(G)=6k+3; 當(dāng)n=4k+2時(shí)，γ's(G)=6k+4; 當(dāng)n=4k+3時(shí)γ's(G)=6k+5。

證明：因?yàn)棣?s(G)=|E+|-|E-|=|E(G)|-2|E-| ,所以當(dāng)|E-|取上界時(shí)，γ's(G)取下界，下面給出|E-|取上界時(shí)E-的邊集構(gòu)造。

當(dāng)n=4k時(shí)，由引理4，|E-|≤7k。 構(gòu)造函數(shù)f為e∈W0∪W1∪…∪Wk-1時(shí)，f(e)=-1，否則f(e)=1(見(jiàn)圖2)。 容易驗(yàn)證f為P3×Cn的一個(gè)符號(hào)邊控制函數(shù)且|E-|=7k，結(jié)合引理4有γ's(G)=|E(G)|-2|E-|=20k-2×7k=6k。

圖2 n=4k時(shí)的符號(hào)邊控制函數(shù)f示意圖

當(dāng)n=4k+1時(shí)，構(gòu)造函數(shù)f為e∈W0∪W1∪…∪Wk-1∪{x1,n-1x2,n-1}時(shí)f(e)=-1，否則f(e)=1(見(jiàn)圖3)。 容易驗(yàn)證f為P3×Cn的一個(gè)符號(hào)邊控制函數(shù)且|E-|=7k+1，結(jié)合引理4有γ's(G)=6k+3。

圖3 n=4k+1時(shí)符號(hào)邊控制函數(shù)f示意圖

當(dāng)n=4k+2時(shí)，令L1={x1,n-6x0,n-6x0,n-5}∪{x2,n-6x2,n-5}∪{x1,n-5x1,n-4x0,n-4}∪{x0,n-3x0,n-2x1,n-2}∪{x1,n-3x2,n-3x2,n-2}∪{x1,n-1x2,n-1}。

如果k=1，構(gòu)造f為當(dāng)e∈L1時(shí)，f(e)=-1，否則f(e)=1。 如果k≥2，構(gòu)造f為當(dāng)e∈L1∪W0∪W1∪W2∪…∪Wk-2時(shí)，f(e)=-1，否則f(e)=1(見(jiàn)圖4)。 容易驗(yàn)證f為P3×Cn的一個(gè)符號(hào)邊控制函數(shù)且|E-|=7k+3，結(jié)合引理4有γ's(G)=6k+4。

圖4 n=4k+2時(shí)符號(hào)邊控制函數(shù)f示意圖

當(dāng)n=4k+3時(shí)，令L2={x1,n-7x0,n-7x0,n-6}∪{x2,n-7x2,n-6x1,n-6}∪{x0,n-5x1,n-5x1,n-4}∪{x0,n-4x0,n-3}∪{x2,n-4x2,n-3x1,n-3}∪{x0,n-2x1,n-2x1,n-1x2,n-1}。

如果k=1，構(gòu)造f為當(dāng)e∈L2時(shí)，f(e)=-1，否則f(e)=1。 如果k≥2，構(gòu)造f為當(dāng)e∈L2∪W0∪W1∪W2∪…∪Wk-2時(shí)，f(e)=-1，否則f(e)=1(見(jiàn)圖5)。 容易驗(yàn)證f為P3×Cn的一個(gè)符號(hào)邊控制函數(shù)且|E-|=7k+5，結(jié)合引理4有γ's(G)=6k+5。

圖5 n=4k+3時(shí)符號(hào)邊控制函數(shù)f示意圖

由此定理得證。

三、結(jié)語(yǔ)

對(duì)于笛卡爾乘積圖P3×Cn, 本文通過(guò)圖結(jié)構(gòu)分析方式研究確定了它的符號(hào)邊控制數(shù)。 對(duì)一般的m≥4，確定笛卡爾乘積圖Pm×Cn的符號(hào)邊控制數(shù)是值得進(jìn)一步研究的問(wèn)題。如果將路P3替換為一般的路Pm, 本文的提出的方法可為這類笛卡爾乘積圖的符號(hào)邊控制數(shù)研究提供借鑒。 對(duì)一般的笛卡爾乘積圖G×H, 其符號(hào)邊控制數(shù)與圖G和圖H的符號(hào)邊控制數(shù)之間的關(guān)系也是值得進(jìn)一步探討的。