兩類(lèi)Mycielski圖的符號(hào)圈控制數(shù)

高婷，陳學(xué)剛

（華北電力大學(xué)數(shù)理學(xué)院，北京102200）

兩類(lèi)Mycielski圖的符號(hào)圈控制數(shù)

高婷，陳學(xué)剛

（華北電力大學(xué)數(shù)理學(xué)院，北京102200）

設(shè)G=（V，E）是一個(gè)圖，一個(gè)函數(shù)f∶E→{－1，1}如果對(duì)G中每一個(gè)無(wú)弦圈C均有f（E（C））≥1，則稱f為圖G的一個(gè)符號(hào)圈控制函數(shù)，圖G的符號(hào)圈控制數(shù)定義為為G的符號(hào)圈控制函數(shù)}.通過(guò)研究Mycielski圖的符號(hào)圈控制數(shù)，確定了由路和圈構(gòu)成的Mycielski圖的符號(hào)圈控制數(shù).

Mycielski圖；符號(hào)圈控制函數(shù)；符號(hào)圈控制數(shù)

0 引言

文中所指的圖均為無(wú)向簡(jiǎn)單圖，文中符號(hào)和術(shù)語(yǔ)同文獻(xiàn)[1].

設(shè)G=（V，E），在文獻(xiàn)[2]中J.Mycielski定義了圖G的Mycielski圖M（G）如下：

若C為圖G中長(zhǎng)度不小于的4一個(gè)圈，u和v為在C中兩個(gè)不相鄰的頂點(diǎn)，如果uv∈E（G），則稱uv為圈C的一條弦.圖G的一個(gè)圈C是無(wú)弦的當(dāng)且僅當(dāng)G[V（C）]=C.G的一個(gè)無(wú)弦圈也稱為G的一個(gè)導(dǎo)出圈.

對(duì)于G的一個(gè)函數(shù)f∶E→{－1，1}，任意S?E（G），令.若函數(shù)f∶E→{－1，1}對(duì)G中每一個(gè)無(wú)弦圈C均有f（E（C））≥1，則稱f為圖G的一個(gè)符號(hào)圈控制函數(shù).圖G的符號(hào)圈控制數(shù)定義為為G的符號(hào)圈控制函數(shù)}.圖G的符號(hào)圈控制函數(shù)是在圖的點(diǎn)和符號(hào)邊控制的基礎(chǔ)上（見(jiàn)文獻(xiàn)[3-4]）.由徐教授在文獻(xiàn)[5]中提出的，并在文獻(xiàn)[5-9]中得到了一些特殊圖的符號(hào)圈控制數(shù).皮曉明在文獻(xiàn)[10]中對(duì)給定符號(hào)圈控制數(shù)的圖進(jìn)行了刻畫(huà)，通過(guò)對(duì)這些文獻(xiàn)的研究，此文給出了兩類(lèi)Mycielski圖的符號(hào)圈控制數(shù).

為簡(jiǎn)單起見(jiàn)，給定f是圖G的一個(gè)函數(shù)f∶E→{－1，1}，令，若f（e）=1，則稱e為正邊；否則稱e為負(fù)邊.

1 Mycielski圖的主要結(jié)論及其證明

1.1 M（Pn）圖的符號(hào)圈控制數(shù)

另一方面，設(shè)f是M（Pn）的一個(gè)最小符號(hào)圈控制函數(shù)，因?yàn)槊總€(gè)M（P3）和M（P2）均至多有兩條負(fù)邊，所以

1.2 M（Cn）圖的符號(hào)圈控制數(shù)

設(shè)V=V（Cn）={1，2，…，n}，其中n為偶數(shù).為了給出圈Cn形成的Mycielski圖M（Cn）的符號(hào)圈控制數(shù)，首先研究M（Cn）的以下兩類(lèi)子圖的符號(hào)圈控制數(shù).

證明：由G1圖的定義可以得出.以n=12為例，G1圖如圖1所示.

圖1

定義圖G1的一個(gè)函數(shù)f∶E（G1）→{－1，1}如下：

另一方面，觀察到圖G1包含個(gè)C4，所以.當(dāng)時(shí)，則每個(gè)C4中均有一條負(fù)邊，而這些負(fù)邊一定在一個(gè)Cn中.因?yàn)閚是偶數(shù)，所以這個(gè)Cn的符號(hào)圈控制數(shù)為0與定義矛盾，故.因此.綜上可得

令G2=M（Cn）[V2]，則.

圖2

定義圖G2的一個(gè)函數(shù)f∶E（G2）→{－1，1}如下：

另一方面，設(shè)f是圖G2的一個(gè)最小符號(hào)圈控制函數(shù).下面證明，分兩種情況證明：

（1）任意負(fù)邊均不與點(diǎn)u關(guān)聯(lián).因?yàn)樨?fù)邊均包含在一個(gè)Cn中且n為偶數(shù)，所以；

（2）存在一條負(fù)邊e與點(diǎn)u關(guān)聯(lián).因?yàn)閑屬于相鄰兩個(gè)C4中，余下－2個(gè)C4，顯然.故綜上

[1]BONDY J A，MURTY V S R.Graph theory with applications[M].Amsterdam：Elsevier，1976.

[2]MYCIELSKI J.Sur le coloriage des graphes[J].Colloq Math，1955（3）：61-162.

[3]XU B G.On signed edge domination numbers ofgraphs[J].Discrete Math，2001，239：179-189.

[4]Xu B G．Two classes ofedge domination in graphs[J].Discrete Appl Math，2006，154：1541－1546．

[5]徐保根.圖的符號(hào)圈控制[J].華東交通大學(xué)學(xué)報(bào)，2005，22（5）：135-137.

[6]XU B G.On signed cycle domination numbers in graphs[J].Discrete Math，2009，309：1007-1012.

[7]徐保根，鄒妍，趙麗鑫.關(guān)于圖的符號(hào)圈控制[J].河南科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2014，35（6）：80-84.

[8]徐保根，周尚超.圖與補(bǔ)圖的符號(hào)圈控制[J].江西師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2006，30（3）：249-251.

[9]徐保根，康洪波，趙利芬，等.圖的圈符號(hào)控制數(shù)[J].中山大學(xué)學(xué)報(bào)（自然科學(xué)版），2013（6）：136-138．

[10]PI X M.On the characterization of graphs with given signed cycle domination number[J].數(shù)學(xué)進(jìn)展，2015，44（2）：219-229.

Signed Cycle Domination of Two Classes Mycielski Graph

GAO Ting,CHEN Xuegang
（Institute of Mathematics and Physics,North China of Electric Porwer University,Beijing102200,China）

Let G=（V，E）be a simple graph.Afunction f∶E→{－1，1}is said tobe a signed cycle domination function ofG≥1 for each induced cycle of G.a signed cycle domination function of G}is called the signed cycle domination number of G.Mycielski graph is studied and the signed cycle domination numbers of Mycielski graphs formed by cycle and path is determined.

Mycielski graph;signed cycle domination;signed cycle domination function

O 157.5

A

1001-4217（2017）01-0038-06

2015-12-27

高婷（1987—），女，山西呂梁人，碩士.研究方向：圖論.E-mail：gaoting0319@163.com

中央高?；究蒲袠I(yè)務(wù)費(fèi)專(zhuān)項(xiàng)資金資助（2016MS66）