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

馬夢焓, 紅 霞

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

1 引言

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

設(shè)G=(V,E) 是一個圖, 其頂點集V=V(G) 和邊集E=E(G).對任意u ∈V(G), 則NG(u)為u點在G中的領(lǐng)域,NG[u]=NG(u)∪{u}為u點在G中的閉領(lǐng)域,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個輪圖的中心點粘接而得到的圖.

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

目前很多相關(guān)學(xué)者研究了關(guān)于圖的符號全控制數(shù)的上下界[10,11]以及特殊圖的符號全控制數(shù)的精確值[12].文獻[13]中, 呂新忠等人確定了完全圖、星圖、扇圖、輪圖以及完全多部圖的……