兩類聯(lián)圖的符號(hào)控制數(shù)

張靖宇，紅 霞

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

0 引言

本文所考慮的圖均為簡單圖，且文中沒有進(jìn)行說明的圖論中術(shù)語以及符號(hào)，見參考文獻(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中的鄰域，NG[u]＝NG（u）∪{u}為 u點(diǎn)在G中的閉鄰域，為u點(diǎn)在G中的度，而δ＝δ（G）和Δ＝Δ（G）分別為圖G的最小度和最大度.在不致混淆情況下，可將 NG（u），NG[u]，Δ（G）.δ（G）分別簡單記為 N（u），N[u]，Δ，δ.用Kn，W1·n，分別表示n階完全圖、n＋1階輪圖和m階完全圖的補(bǔ)圖.表示圖的每個(gè)頂點(diǎn)與H的每個(gè)頂點(diǎn)相連接的聯(lián)圖.

圖論的發(fā)展近幾十年來非常迅速，特別是圖的控制理論方向，其研究內(nèi)容以及延伸的概念越來越多，諸多學(xué)者們依次提出有不同類型的控制數(shù)和相關(guān)的概念，比如首先提出的是圖的頂點(diǎn)符號(hào)控制數(shù)[2]，是由J E Dunbar等人在1995年提出的.其次提出的是圖的邊（全）符號(hào)控制數(shù)[3]、延伸定義的概念有圖的符號(hào)全控制數(shù)[4]以及圖的圈符號(hào)（邊）控制數(shù)[5].最近比較活躍的概念是羅曼符號(hào)（邊）控制數(shù)[6-7]等.事實(shí)上，控制理論中研究符號(hào)控制數(shù)的應(yīng)用背景與我們現(xiàn)實(shí)生活有著密切關(guān)系，如選擇適合的交通崗位、選最優(yōu)的物資供應(yīng)點(diǎn)的設(shè)置等.

至今為止，很多學(xué)者也紛紛參與這項(xiàng)龐大研究領(lǐng)域并從中得到了有價(jià)值的研究成果.比如，已經(jīng)確定有關(guān)于圖的符號(hào)控制數(shù)的界[8].另外，文獻(xiàn)[9]也確定了特殊圖的符號(hào)控制數(shù)的精確值.文獻(xiàn)[10]中，給出了兩類特殊圖氣球圖和啞鈴圖的符號(hào)控制數(shù)，這里所謂的氣球圖是指路Pm的一個(gè)端點(diǎn)與圈Cm中的一個(gè)頂點(diǎn)粘合（重合）而成的圖.所謂啞鈴圖是指路Pm的兩個(gè)端點(diǎn)分別粘接一個(gè)圈Cm而成的圖.文獻(xiàn)[11]中，作者高婷等人給出了Mycielski圖（由路和圈構(gòu)成）的符號(hào)圈控制數(shù).文獻(xiàn)[12]中，作者李寧等人計(jì)算出了兩類笛卡爾乘積圖（圈和路）的符號(hào)控制數(shù).本文主要確定了兩類聯(lián)圖的符號(hào)控制數(shù)的精確值.

對(duì)于圖G＝（V，E），定義一個(gè)函數(shù)f:V→R和G的一個(gè)子集S?V（G），記f（S）＝∑v∈Sf（v）.

1 基本概念

定義1[2]設(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ù)定義為是圖G的一個(gè)符號(hào)控制函數(shù)}，并將使得γS（G）＝f（V）的符號(hào)控制函數(shù)稱f為圖G的一個(gè)最小符號(hào)控制函數(shù).

2 主要結(jié)果