两类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）