兩類圖的符號(hào)全控制數(shù)

馬夢(mèng)焓, 紅 霞

(洛陽師范學(xué)院數(shù)學(xué)科學(xué)學(xué)院, 河南洛陽 471022)

1 引言

本文所指定的圖均為無向簡單圖, 文中未說明的符號(hào)和術(shù)語同文獻(xiàn)[1].

設(shè)G=(V,E) 是一個(gè)圖, 其頂點(diǎn)集V=V(G) 和邊集E=E(G).對(duì)任意u ∈V(G), 則NG(u)為u點(diǎn)在G中的領(lǐng)域,NG[u]=NG(u)∪{u}為u點(diǎn)在G中的閉領(lǐng)域,dG(u)=|NG(v)|為u點(diǎn)在G中的度, 而δ=δ(G) 和?=?(G) 分別為圖G的最小度和最大度.在不致混淆情況下, 可將NG(v),NG[v],?(G),δ(G) 分別簡單記為N(v),N[v],?,δ.用Cn,Pn,Fn,Wn分別表示n階圈、路、扇圖和輪圖, 其中扇圖Fm+1是指m+1 個(gè)頂點(diǎn)的圖, 即由一個(gè)中心頂點(diǎn)w連接m個(gè)頂點(diǎn)路Pm的所有頂點(diǎn)的圖.輪圖Wm+1是指m+1 個(gè)頂點(diǎn)的圖, 即由一個(gè)中心頂點(diǎn)w連接m個(gè)頂點(diǎn)圈Cm的所有頂點(diǎn)的圖.圖n·Fm+1表示把n個(gè)扇圖的中心點(diǎn)粘接而得到的圖, 圖n·Wm+1表示把n個(gè)輪圖的中心點(diǎn)粘接而得到的圖.

近幾十年來, 圖的控制理論的研究內(nèi)容越來越豐富, 各種類型的符號(hào)控制數(shù)以及其變化的形式依次被提出, 如圖的符號(hào)控制數(shù)[2?4]、圖的邊符號(hào)控制數(shù)[5]、圖的邊全符號(hào)控制數(shù)[5]、圖的符號(hào)全控制數(shù)[6]、圖的星符號(hào)控制數(shù)[5]、圖的圈符號(hào)(邊) 控制數(shù)[7]、圖的團(tuán)符號(hào)(邊)控制數(shù)[5]、圖的逆符號(hào)(邊) 控制數(shù)[5]、圖的反符號(hào)(邊) 控制數(shù)[5]、羅曼符號(hào)(邊) 控制數(shù)[8,9]等.其中首次被提出的是圖的符號(hào)控制概念, 由Dunbar 等人在1995 年提出.圖的符號(hào)控制數(shù)的研究有著廣泛的應(yīng)用背景, 如交通崗位、物資供應(yīng)點(diǎn)的設(shè)置等, 但是符號(hào)控制數(shù)的計(jì)算是NP 完全問題.

目前很多相關(guān)學(xué)者研究了關(guān)于圖的符號(hào)全控制數(shù)的上下界[10,11]以及特殊圖的符號(hào)全控制數(shù)的精確值[12].文獻(xiàn)[13]中, 呂新忠等人確定了完全圖、星圖、扇圖、輪圖以及完全多部圖的符號(hào)全控制數(shù).本文中主要得到了兩類特殊圖n·Fm+1和n·Wm+1的符號(hào)全控制數(shù)的精確值.特別地, 當(dāng)n=1 時(shí), 得到了扇圖和輪圖的符號(hào)全控制數(shù), 從而改正了文獻(xiàn)[13]中的兩個(gè)關(guān)于扇圖和輪圖的符號(hào)全控制數(shù)的結(jié)果.

對(duì)于圖G= (V,E), 定義一個(gè)函數(shù)f:VR和G的一個(gè)子集S ?V(G), 記為簡單起見, 下文中適合f(u)=+1 的頂點(diǎn)稱為+1 點(diǎn), 適合f(u)=?1 的頂點(diǎn)稱為?1 點(diǎn).

2 基本概念

定義 2.1(文獻(xiàn)[6]) 設(shè)圖G= (V,E) 為一個(gè)圖, 一個(gè)雙值函數(shù)f:V{1,?1}, 如果對(duì)任意的頂點(diǎn)v ∈V, 均有f(N(v))≥1 成立, 則稱f為圖G的一個(gè)符號(hào)全控制函數(shù), 圖G的符號(hào)全控制數(shù)定義為γst(G) = min{f(V)|f是圖G的一個(gè)符號(hào)全控制函數(shù)}, 并將使得γst(G)=f(V) 的符號(hào)全控制函數(shù)稱f為圖G的一個(gè)最小符號(hào)全控制函數(shù).

從符號(hào)全控制的定義, 容易看出以下結(jié)論.

引理2.2設(shè)函數(shù)f是圖G的符號(hào)全控制函數(shù).對(duì)于u ∈V(G), 若d(u)≡0(mod 2), 則f(N(u)) 為偶數(shù).若d(u)≡1(mod 2), 則f(N(u)) 為奇數(shù).

3 主要結(jié)果

定理 3.1若n ≥1,m>1, 則

若n ≥1,m=1, 則

證令圖n·Fm+1是由n個(gè)扇圖Fm+1的中心點(diǎn)粘接而得到的圖, 記為

首先證明

令f是圖n·Fm+1的一個(gè)最小符號(hào)全控制函數(shù), 則f(V(G))=γst(n·Fm+1).

設(shè)圖n·Fm+1中所有?1 點(diǎn)個(gè)數(shù)為t, 所有+1 點(diǎn)個(gè)數(shù)為s, 則有s+t=nm+1, 從而有

當(dāng)m=1 時(shí), 圖n·Fm+1是n+1 個(gè)頂點(diǎn)的星圖此時(shí)給出星圖的符號(hào)全控制函數(shù)f如下:f(w)=+1,

容易驗(yàn)證, 此時(shí)函數(shù)f為最優(yōu), 從而有

當(dāng)m=2 時(shí), 圖n·Fm+1中每個(gè)頂點(diǎn)必標(biāo)為+1, 從而有γst(n·Fm+1)=2n+1.

下面只考慮當(dāng)m ≥3.為此通過分三種情況來證明圖n·Fm+1的符號(hào)全控制數(shù)的下界.

情況1當(dāng)m ≡0(mod 4) 時(shí), 因d(w)≡0(mod 2), 由引理知,f(N(w)) 為偶數(shù), 從而有

情況2當(dāng)m ≡2(mod 4) 時(shí), 先證明以下五個(gè)斷言(這里1≤i ≤n).

這與符號(hào)全控制函數(shù)的定義矛盾.

結(jié)合斷言1 和斷言2, 推出下面的斷言3 和斷言4.

斷言3每條路P(i)上連續(xù)三個(gè)頂點(diǎn)中至多有兩個(gè)頂點(diǎn)標(biāo)為?1.

斷言4每條路P(i)上連續(xù)四個(gè)頂點(diǎn)中至多有兩個(gè)頂點(diǎn)標(biāo)為?1.

因?yàn)棣胹t(n·Fm+1)=nm+1?2t.由斷言 5 可知

情況 3當(dāng)m ≡1(mod 2) 時(shí), 情況 2 中的斷言 1、2、3、4 依然成立.

綜上所述, 有

下面給出n·Fm+1的符號(hào)全控制的上界.

情況1當(dāng)m ≡0(mod4) 時(shí), 給出n·Fm+1的一個(gè)符號(hào)全控制函數(shù)f:f(w)=+1.

當(dāng)m=4 時(shí), 令

當(dāng)m>4 時(shí), 令

容易驗(yàn)證, 此時(shí)f(V)=3, 從而有

情況2當(dāng)m ≡2(mod 4) 時(shí), 對(duì)于1≤i ≤n, 給出n·Fm+1的一個(gè)符號(hào)全控制函數(shù)f:f(w)=+1,

容易驗(yàn)證, 此時(shí)f(V)=2n+1, 從而有γst(n·Fm+1)≤2n+1.

情況3當(dāng)m ≡1(mod 2) 時(shí), 對(duì)于1≤i ≤n, 給出n·Fm+1的一個(gè)符號(hào)全控制函數(shù)f:f(w)=+1.

當(dāng)m=3 時(shí), 令

當(dāng)m=5 時(shí), 令

當(dāng)m>5 時(shí), 令

容易驗(yàn)證, 此時(shí)f(V)=n+1, 從而有

綜上所述, 有

定理1 證畢.

注定理1 中當(dāng)m= 1 時(shí), 得到了n+1 階星圖的符號(hào)全控制數(shù)的結(jié)果, 這與文[13]中的結(jié)論一致.

定理 3.2設(shè)n ≥1,m ≥3, 則

證令圖n·Wm+1是由n個(gè)輪圖Wm+1的中心點(diǎn)粘接而得到的圖, 記為

令f是圖n·Wm+1的一個(gè)最小符號(hào)全控制函數(shù), 則

設(shè)n·Wm+1中所有?1 點(diǎn)個(gè)數(shù)為t, 所有+1 點(diǎn)個(gè)數(shù)為s, 則有s+t=nm+1, 從而有

首先證明

若f(w) =?1 時(shí), 注意到, 對(duì)于每個(gè)點(diǎn)且從而必有故, 有

若f(w)=1 時(shí), 分情況討論圖n·Wm+1的符號(hào)全控制數(shù)的下界.

情況1當(dāng)m ≡0(mod 4) 時(shí), 同證明定理1 中的下界時(shí)的情況1 一樣推導(dǎo)出

情況 2當(dāng)m ≡2(mod 4) 時(shí), 定理 1 中的斷言 1、2、3、4 仍然成立.

斷言 7每個(gè)圈C(i)上頂點(diǎn)中至多有個(gè)標(biāo)為?1 的點(diǎn).因?yàn)橥? 有

情況 3當(dāng)m ≡1(mod 2) 時(shí), 定理 1 中的斷言 1、2、3、4 仍然成立.

考慮到當(dāng)f(w)=?1 和f(w)=1 時(shí)的圖n·Wm+1的符號(hào)全控制數(shù)的下界, 容易得出

下面再考慮圖n·Wm+1的符號(hào)全控制的上界.同定理1 的證明, 現(xiàn)只需定義一個(gè)符號(hào)全控制數(shù)函數(shù)g使得g=f(這里f是指定理1 情況3 中給出的函數(shù)f).

因圖n·Wm+1比圖n·Fm+1多了邊增加此邊時(shí)只有對(duì)兩個(gè)端點(diǎn)的符號(hào)全控制數(shù)有變化.事實(shí)上, 在符號(hào)全控制數(shù)函數(shù)g下, 有對(duì)于頂點(diǎn)有g(shù)(N(u))=f(N(u)).容易驗(yàn)證, 得出

證畢.

特別地, 定理1 和定理2 中當(dāng)n=1 時(shí), 分別得到扇圖和輪圖的符號(hào)全控制數(shù)的結(jié)果.

推論 3.3若n=1,m ≥1, 則

若n=1,m ≥2, 則

注事實(shí)上, 定理1 證明過程中的斷言3 否定了文[13]中的證明過程, 從而得出扇圖和輪圖的符號(hào)全控制數(shù)的精確值.