徐保根,鄒　妍,趙麗鑫

(華東交通大學(xué) 理學(xué)院，江西 南昌 330013)

?

兩類圖的邊控制集劃分

徐保根,鄒妍,趙麗鑫

(華東交通大學(xué) 理學(xué)院，江西 南昌 330013)

摘要:通過分類歸納的方法，對(duì)圖的邊控制集劃分問題進(jìn)行了探討，研究了兩類特殊圖的邊控制集劃分問題，獲得了一些相關(guān)結(jié)論：得到了扇形圖Fn的集邊控制數(shù)和全集邊控制數(shù)，并確定了乘積圖P2×Pn的全集邊控制數(shù).

關(guān)鍵詞:集邊控制數(shù)；全集邊控制數(shù)；扇形圖；乘積圖

近些年來,圖的控制理論研究的內(nèi)容越來越深入，且研究成果不斷豐富.Haynes等[1-2]綜述了圖的控制理論研究方面的主要研究成果，提出了多種控制概念.但大多數(shù)成果均是關(guān)于控制參數(shù)的估計(jì)[3-6]，關(guān)于控制集劃分問題的研究成果較少.Cockayne等[7]引入圖的控制劃分?jǐn)?shù)概念，Zelinka[8-11]研究圖的集邊控制數(shù).筆者所指的圖均為無向簡單圖，文中未說明的符號(hào)和術(shù)語同文獻(xiàn)[12-14].

論文確定了扇形圖Fn的集邊控制數(shù)，并確定了扇形圖Fn和乘積圖P2×Pn的全集邊控制數(shù).如圖2所示.

圖1　扇形圖Fn　　　　　　　　　　　　　　　圖2　乘積圖P2×Pn　　　Fig.1　Fan graph Fn　　　　　　　　　　　　Fig.2　Cartesian product graph P2×Pn

1集邊控制數(shù)

下面將確定扇形圖Fn的邊集控制數(shù).

2全集邊控制數(shù)

下面確定兩類圖的全集邊控制數(shù).

定理2證畢.

證明記

G=P2×Pn,

，

參考文獻(xiàn)：

[1]HAYNES T W, HEDETNIEMI S T, HENNING M A, et al. Domination in graphs[M]. New York: Marcel Dekker Inc, 1998.

[2]HAYNES T W, HEDETNIEMI S T, HENNING M A, et al. Fundamentals of domination in graphs[M]. New York: Marcel Dekker Inc, 1998.

[3]ORE O. Theory of graphs[C]// American Mathematical Society Colloquium, RI, 1962.

[4]DOMKE G S, HEDETNIEMI S T, LASKAR R C. Fractional packings ,coverings and irredundance in graphs[J].Congr Numer, 1988, 66: 227-238.

[5]ZHANG Z F, XU B G. A note on the lower bounds of signed domination number of a graph[J]. Discrete Math, 1999, 195: 295-298.

[6]XU B G. On signed edge domination numbers of graphs[J].Discrete Math, 2001, 239: 179-189.

[7]COCKAYNE E J, HEDETNIEMI S T. Towards a theory of domination in graphs[J].Networks, 1977, 7: 247-261.

[8]ZELINKA B. Edge-domatic number of graph[J]. Czech Math, 1983, 33: 107-110.

[9]ZELINKA B. Total edge-domatic number of graph[J]. Math Bohe, 1989, 116: 96-100.

[10]ZELINKA B. Some remarks on domatic numbers of graphs[J]. Casop Pest Mat, 1982, 106: 373-375.

[11]ZELINKA B. Adomatic and idiomatic numbers of graphs[J]. Math Slovaca, 1983, 33: 99-103.

[12]BONDY J A, MURTY V S R. Graph theory with applications[M]. New York: Elsevier, 1976.

[13]DUBAR J E, HEDETNIEMI S T, HENNING M A, et al. Signed domination in graphs[M]. New York: John Wiley Inc, 1995.

[14]徐保根.圖的控制理與染色理論[M].武漢：華中科技大學(xué)出版社， 2013.

(責(zé)任編輯朱夜明)

doi:10.3969/j.issn.1000-2162.2016.04.001

收稿日期：2015-03-16

基金項(xiàng)目:國家自然科學(xué)基金資助項(xiàng)目(11361024)；江西省高?？萍悸涞赜?jì)劃資金資助項(xiàng)目(KJLD12067)

作者簡介：徐保根(1963-)，男，江西南昌人，華東交通大學(xué)教授，碩士生導(dǎo)師.

中圖分類號(hào)：O157.5

文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1000-2162(2016)04-0001-05

The edge-domatic number for two classes of graphs

XU Baogen, ZOU Yan, ZHAO Lixin

(School of Natural Science, East China Jiaotong University, Nanchang 330013, China)

Abstract:The problem of edge domatic number was discussed by using the method of the partition and induction. In this paper ,we studied the problems of two classes of the special graphs and drew some related conclusions. We obtained the edge domatic number and the total edge domatic number of the fan graph Fn, determined the total edge domatic numbers of the product graph P2×Pn.

Keywords:edge domatic number; total edge domatic number; fan graph; product graph