張靖宇，紅 霞

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

0 引言

本文所考慮的圖均為簡單圖，且文中沒有進行說明的圖論中術語以及符號，見參考文獻[1].

設G＝（V，E）是一個簡單圖，其頂點集為 V＝V（G）和邊集為 E＝E（G）.對任意u∈V（G），則 NG（u）為 u點在G中的鄰域，NG[u]＝NG（u）∪{u}為 u點在G中的閉鄰域，為u點在G中的度，而δ＝δ（G）和Δ＝Δ（G）分別為圖G的最小度和最大度.在不致混淆情況下，可將 NG（u），NG[u]，Δ（G）.δ（G）分別簡單記為 N（u），N[u]，Δ，δ.用Kn，W1·n，分別表示n階完全圖、n＋1階輪圖和m階完全圖的補圖.表示圖的每個頂點與H的每個頂點相連接的聯(lián)圖.

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

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

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

1 基本概念

定義1[2]設圖G＝（V，E）為一個圖，一個雙值函數(shù)f:V→{1，－1}，如果對任意的頂點v∈V，均有f（N[v]）≥1成立，則稱f為圖G的一個符號控制函數(shù).圖G的符號控制數(shù)定義為是圖G的一個符號控制函數(shù)}，并將使得γS（G）＝f（V）的符號控制函數(shù)稱f為圖G的一個最小符號控制函數(shù).

2 主要結果