關于圖的符號圈(點)控制

徐保根，丁宗鵬，湯友亮

(華東交通大學基礎科學學院，江西南昌 330013)

關于圖的符號圈(點)控制

徐保根，丁宗鵬，湯友亮

(華東交通大學基礎科學學院，江西南昌 330013)

引入了圖的符號圈(點)控制概念，給出了所有n階極大平面圖G(n≥3)的符號圈(點)控制數(shù)γsc(G)的一個下界，即γsc(G)≥(8n-16-nΔ)/Δ，并且此下界是最好可能的，獲得了滿足γsc(G)=V(G)-2的所有連通圖的一個特點.此外，還確定了幾類特珠圖的符號圈(點)控制數(shù).

圖;平面圖;函數(shù);符號圈(點)控制函數(shù);符號圈(點)控制數(shù)

0 引言

本文所指的圖均為無向簡單圖，文中未說明的符號和術語同文獻［1］.

設G=(V，E)是一個圖，若S?V(G)，則G[S]表示S在G中的導出子圖.若C為圖G的一個長度不小于4的圈，u和v為在C中兩個不相鄰的頂點，如果uv∈E(G)，則稱uv為圈C的一條弦.圖G的一個圈C是無弦的當且僅當G(V[C])=C.G的一個無弦圈也稱為G的一個導出圈.

近些年來，圖的控制理論的研究內容越來越豐富.加拿大著名圖論專家COCKAYNE E J等人先后引入了圖的許多不同類型的控制概念及其變化形式［1］.1998年美國圖論學者HAYNES W T等人出版了兩部專著［2-3］，較為系統(tǒng)地綜述了此前的一些主要研究成果.值得注意的是:幾乎所有的概念和結果都是針對圖的點控制而言，很少涉及圖的邊控制問題.為了更進一步豐富和完善圖的控制理論內容，文獻［1］已將圖的點控制概念轉向研究圖的邊控制問題，并獲得了不少的研究成果，如符號邊控制、符號星控制、符號團控制、符號圈控制等.然而，幾乎每一種符號邊控制概念都有其對應的點控制，為此引入圖的符號圈(點)控制概念［4］.

1 主要結果及其證明

如果一個平面圖G的每個面(包括外部面)的邊界均為三角形，則稱G為極大平面圖.

引理［1］設整數(shù)n≥3，則每個n階極大平面圖有2n-4個面(包括外部面).

當G=K3時，等號成立.

證明 將圖G=P2×Pn畫在平面上，使其成2行n列的格圖.選取第一行以-1，1對所有點依次交錯標號，第二行所有點定義為1.不難驗證，此定義標號滿足符號圈(點)控制的定義.于是有

另一方面，依照定義，對于每個圈C4至多有一個點標號-1，于是有

定理4當n≥3時，有γsc(P3×Pn)=n.

證明 將圖G=P3×Pn畫在平面上，使其成3行n列的格圖.選取第一行以-1，1對所有點依次交錯標號，第二行所有點定義為1.第三行以1，-1對所有點依次交錯標號.不難驗證，此定義標號滿足符號圈(點)控制的定義.于是有

另一方面，依照定義，對于圖中的圈C2n+2至多有n個點標號-1.于是有

綜上，γsc(P3×Pn)=n，n≥3.證畢.

定理5當n≥4時，有

證明 將圖G=P4×Pn畫在平面上，使其成4行n列的格圖.選取第一、第四行以-1，1對所有點依次交錯標號，第二、第三行所有點定義為1.不難驗證，此定義標號滿足符號圈(點)控制的定義.于是有

另一方面，當n為偶數(shù)時，對于圖中的圈C2n+4至多有n個點標號-1(如果圖中的C2n+4有n+1個點標號-1，則至少存在一個C4，其中必有兩個點標號-1，這不滿足符號圈(點)控制的定義，矛盾).于是有

當n為奇數(shù)時，對于圖中的圈C2n+4至多有n+1個點標號-1.于是有

2 一個問題

通過定理3、定理4和定理5，我們不難提出一個問題:如何確定圖Pm×Pn的符號圈(點)控制數(shù)呢?

［1］ 徐保根.圖的控制理論［M］.北京:科學出版社，2008.

［2］ HAYNES T W，HEDETNIEMI S T，SLATER P J.Domination in graphs［M］.New York:Marcel Dekker Inc，1998.

［3］ HAYNES T W，HEDETNIEMI S T，SLATER P J.Fundamentals of domination in graphs［M］.New York:Marcel Dekker Inc，1998.

［4］ XU Baogen.On signed cycle domination in graphs［J］.Discrete Math，2009，309(4):1007-1012.

On Signed Cycle(Vertex)Domination in Graphs

XU Bao-gen，DING Zong-peng，TANG You-liang

(School of Basic Sciences，East China Jiaotong University，Nanchang330013，China)

Introduce the concept of signed cycle(vertex)domination in graphs，and give a lower bound for signed cycle(vertex)domination number γsc(G)of every maximal planar graphGof ordern≥3，γsc(G)≥(8n-16-nΔ)/Δ，and show that this lower bound is the best possible，and gain a feature for all connected graphs of γsc(G)=-2.In addition，get the signed cycle(vertex)domination number for some special classes of graphs.

graph;planar graph;function;signed cycle(vertex)domination function;signed cycle(vertex) domination number

O157.5

A

1007-0834(2011)04-0001-03

10.3969/j.issn.1007-0834.2011.04.001

2011-09-20

國家自然科學基金(11061014);江西省教育廳科研項目(GJJ09215)

徐保根(1963—)，男，江西南昌人，華東交通大學基礎科學學院教授，研究方向:圖論與組合數(shù)學.