關(guān)于圖的兩類符號(hào)全控制數(shù)

尚華輝,謝鳳艷

(1.永城職業(yè)學(xué)院基礎(chǔ)部，河南永城476600；2.安陽(yáng)學(xué)院建筑工程學(xué)院,河南安陽(yáng)455000)

?

關(guān)于圖的兩類符號(hào)全控制數(shù)

尚華輝1,謝鳳艷2

(1.永城職業(yè)學(xué)院基礎(chǔ)部，河南永城476600；2.安陽(yáng)學(xué)院建筑工程學(xué)院,河南安陽(yáng)455000)

鑒于圖的符號(hào)邊全控制數(shù)和符號(hào)全控制數(shù)的應(yīng)用背景，在構(gòu)造適當(dāng)集合的基礎(chǔ)上，對(duì)符號(hào)邊全控制函數(shù)和符號(hào)全控制數(shù)的下界進(jìn)行了研究，得到了兩個(gè)結(jié)論：一般圖的符號(hào)邊全控制數(shù)的 1 個(gè)下界和一般圖的符號(hào)全控制數(shù)的2個(gè)下界.

符號(hào)邊全控制函數(shù);符號(hào)邊全控制數(shù);符號(hào)全控制數(shù).

0　引言

1　引理

引理1[4]對(duì)任意邊數(shù)為m的連通圖G,則圖G符號(hào)邊控制數(shù)

其中mo為邊度為奇數(shù)的邊的條數(shù)，Δe和δe分別為圖G的最大邊度和最小邊度.

由符號(hào)邊全控制數(shù)的定義知下述的引理2顯然成立.

引理2設(shè)Eo,Ee分別表示圖G的邊度為奇數(shù)和偶數(shù)的邊的集合，函數(shù)f為圖G的符號(hào)邊全控制函數(shù)，則

下文我們將給出關(guān)于符號(hào)邊全控制數(shù)的1個(gè)下界和關(guān)于符號(hào)全控制數(shù)的2個(gè)下界.

2　主要結(jié)論及其證明

(1)

(2)

由(1)和(2)得

(3)

另一方面

(4)

(5)

由(3)和(5)得

結(jié)合(1)式有 m+me

下面給出關(guān)于符號(hào)全控制數(shù)的2個(gè)下界.

(1)

(2)

(3)

(4)

當(dāng)圖G中存在度數(shù)為偶數(shù)的頂點(diǎn)時(shí)，定理2中的下界要優(yōu)于引理3中的下界.

由定理3，可知下述的引理成立.

因此有

[1] 徐保根．圖的控制理論[M]．北京: 科學(xué)出版社, 2008：23-27．

[2] J. A. Bondy ,U. S. R.Murty.GraphTheorywithApplications[M].New York:American Elsevier,1976：237-238.

[3] 徐保根．圖的控制與染色理論[M]．武漢: 華中科技大學(xué)出版社, 2013：53-69．

[4] 趙金鳳,徐保根．關(guān)于圖的符號(hào)邊控制數(shù)的下界[J]．江西師范大學(xué)學(xué)報(bào), 2010(1)：27-29．

[責(zé)任編輯范藻]

On Two Signed Total Domination Number of Graphs

SHANG Huahui1, XIE Fengyan2

(1.Department of Basic Courses, Yongcheng Vocational College, Yongcheng 476600, China;2.School of Civil Engineering and Architecture, Anyang University, Anyang 455000, China)

In view of applying background of the signed edge total domination number and the signed total domination number of a graph, we research lower bounds of signed edge total domination number and signed total domination number based on construction of suitable sets. There are two conclusions: one lower bound of the signed edge total domination number of a general graph and two lower bounds of the signed total domination number of a general graph.

signed edge total domination function; signed edge total domination number; signed total domination number.

2016-05-10

河南省高等學(xué)校重點(diǎn)科研項(xiàng)目(15B110009)

尚華輝(1983—)，男，河南商丘人.講師,碩士，主要從事圖論及其應(yīng)用研究.

O157.5

A

1674-5248(2016)05-0017-04