兩類圖的符號全控制數

馬夢焓, 紅 霞

(洛陽師范學院數學科學學院, 河南洛陽 471022)

1 引言

本文所指定的圖均為無向簡單圖, 文中未說明的符號和術語同文獻[1].

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

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

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

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

2 基本概念

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

從符號全控制的定義, 容易看出以下結論.

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

3 主要結果

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

若n ≥1,m=1, 則

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

首先證明

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

設圖n·Fm+1中所有?1 點個數為t, 所有+1 點個數為s, 則有s+t=nm+1, 從而有

當m=1 時, 圖n·Fm+1是n+1 個頂點的星圖此時給出星圖的符號全控制函數f如下:f(w)=+1,

容易驗證, 此時函數f為最優, 從而有

當m=2 時, 圖n·Fm+1中每個頂點必標為+1, 從而有γst(n·Fm+1)=2n+1.

下面只考慮當m ≥3.為此通過分三種情況來證明圖n·Fm+1的符號全控制數的下界.

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

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

這與符號全控制函數的定義矛盾.

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

斷言3每條路P(i)上連續三個頂點中至多有兩個頂點標為?1.

斷言4每條路P(i)上連續四個頂點中至多有兩個頂點標為?1.

因為γst(n·Fm+1)=nm+1?2t.由斷言 5 可知

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

綜上所述, 有

下面給出n·Fm+1的符號全控制的上界.

情況1當m ≡0(mod4) 時, 給出n·Fm+1的一個符號全控制函數f:f(w)=+1.

當m=4 時, 令

當m>4 時, 令

容易驗證, 此時f(V)=3, 從而有

情況2當m ≡2(mod 4) 時, 對于1≤i ≤n, 給出n·Fm+1的一個符號全控制函數f:f(w)=+1,

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

情況3當m ≡1(mod 2) 時, 對于1≤i ≤n, 給出n·Fm+1的一個符號全控制函數f:f(w)=+1.

當m=3 時, 令

當m=5 時, 令

當m>5 時, 令

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

綜上所述, 有

定理1 證畢.

注定理1 中當m= 1 時, 得到了n+1 階星圖的符號全控制數的結果, 這與文[13]中的結論一致.

定理 3.2設n ≥1,m ≥3, 則

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

令f是圖n·Wm+1的一個最小符號全控制函數, 則

設n·Wm+1中所有?1 點個數為t, 所有+1 點個數為s, 則有s+t=nm+1, 從而有

首先證明

若f(w) =?1 時, 注意到, 對于每個點且從而必有故, 有

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

情況1當m ≡0(mod 4) 時, 同證明定理1 中的下界時的情況1 一樣推導出

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

斷言 7每個圈C(i)上頂點中至多有個標為?1 的點.因為同理, 有

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

考慮到當f(w)=?1 和f(w)=1 時的圖n·Wm+1的符號全控制數的下界, 容易得出

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

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

證畢.

特別地, 定理1 和定理2 中當n=1 時, 分別得到扇圖和輪圖的符號全控制數的結果.

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

若n=1,m ≥2, 則

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