兩類Mycielski圖的符號圈控制數

高婷，陳學剛

（華北電力大學數理學院，北京102200）

兩類Mycielski圖的符號圈控制數

高婷，陳學剛

（華北電力大學數理學院，北京102200）

設G=（V，E）是一個圖，一個函數f∶E→{－1，1}如果對G中每一個無弦圈C均有f（E（C））≥1，則稱f為圖G的一個符號圈控制函數，圖G的符號圈控制數定義為為G的符號圈控制函數}.通過研究Mycielski圖的符號圈控制數，確定了由路和圈構成的Mycielski圖的符號圈控制數.

Mycielski圖；符號圈控制函數；符號圈控制數

0 引言

文中所指的圖均為無向簡單圖，文中符號和術語同文獻[1].

設G=（V，E），在文獻[2]中J.Mycielski定義了圖G的Mycielski圖M（G）如下：

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

對于G的一個函數f∶E→{－1，1}，任意S?E（G），令.若函數f∶E→{－1，1}對G中每一個無弦圈C均有f（E（C））≥1，則稱f為圖G的一個符號圈控制函數.圖G的符號圈控制數定義為為G的符號圈控制函數}.圖G的符號圈控制函數是在圖的點和符號邊控制的基礎上（見文獻[3-4]）.由徐教授在文獻[5]中提出的，并在文獻[5-9]中得到了一些特殊圖的符號圈控制數.皮曉明在文獻[10]中對給定符號圈控制數的圖進行了刻畫，通過對這些文獻的研究，此文給出了兩類Mycielski圖的符號圈控制數.

為簡單起見，給定f是圖G的一個函數f∶E→{－1，1}，令，若f（e）=1，則稱e為正邊；否則稱e為負邊.

1 Mycielski圖的主要結論及其證明

1.1 M（Pn）圖的符號圈控制數

另一方面，設f是M（Pn）的一個最小符號圈控制函數，因為每個M（P3）和M（P2）均至多有兩條負邊，所以

1.2 M（Cn）圖的符號圈控制數

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

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

圖1

定義圖G1的一個函數f∶E（G1）→{－1，1}如下：

另一方面，觀察到圖G1包含個C4，所以.當時，則每個C4中均有一條負邊，而這些負邊一定在一個Cn中.因為n是偶數，所以這個Cn的符號圈控制數為0與定義矛盾，故.因此.綜上可得

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

圖2

定義圖G2的一個函數f∶E（G2）→{－1，1}如下：

另一方面，設f是圖G2的一個最小符號圈控制函數.下面證明，分兩種情況證明：

（1）任意負邊均不與點u關聯.因為負邊均包含在一個Cn中且n為偶數，所以；

（2）存在一條負邊e與點u關聯.因為e屬于相鄰兩個C4中，余下－2個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]徐保根.圖的符號圈控制[J].華東交通大學學報，2005，22（5）：135-137.

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

[7]徐保根，鄒妍，趙麗鑫.關于圖的符號圈控制[J].河南科技大學學報（自然科學版），2014，35（6）：80-84.

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

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

[10]PI X M.On the characterization of graphs with given signed cycle domination number[J].數學進展，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

中央高校基本科研業務費專項資金資助（2016MS66）