广义Mycielskian图的连通度(英文)

曹香兰; 艾尔肯·吾买尔

您当前的位置：

首页 >

文章列表页 >

广义Mycielskian图的连通度(英文)

研究精粹 | 更新时间：2026-01-21

- 广义Mycielskian图的连通度(英文)
- 广义Mycielskian图的连通度(英文)
- 新疆大学学报（自然科学版中英文） 2013年30卷第2期页码：127-132
- 作者机构：
  
  新疆大学数学与系统科学学院
- 作者简介：
- 基金信息：
  
  supported by NSFC(No.11061034)and XJEDU2010I01
- DOI：
  中图分类号： O157.5
- 纸质出版：2013
- 稿件说明：
移动端阅览
[1]曹香兰,艾尔肯·吾买尔.广义Mycielskian图的连通度(英文)[J].新疆大学学报(自然科学版),2013,30(02):127-132.

曹香兰, 艾尔肯·吾买尔. 广义Mycielskian图的连通度(英文)[J]. Journal of Xinjiang University (Natural Science Edition in Chinese and English), 2013, 30(2): 127-132.
[1]曹香兰,艾尔肯·吾买尔.广义Mycielskian图的连通度(英文)[J].新疆大学学报(自然科学版),2013,30(02):127-132. DOI：

曹香兰, 艾尔肯·吾买尔. 广义Mycielskian图的连通度(英文)[J]. Journal of Xinjiang University (Natural Science Edition in Chinese and English), 2013, 30(2): 127-132. DOI：

摘要

Mycieski定义了一个图的运算即把一个图G变换为一个称为G的Mycielskian图的新图μ(G).广义Mycielskian图μm(G)(m≥0)是图的Mycielskian图的一个自然推广.本文证明对任意非平凡连通图G有κ(μm(G))=min{δ(G)+1

(m+1)κ(G)+1}

而且对于m

i≥1

λ(μm(G))=λ(G)+i当且仅当δ(G)=λ(G)+i 1

其中κ(G)

λ(G)和δ(G)分别为图G的连通度

边连通度和最小度.

Abstract

Mycielski introduced a new graph transformation that transforms a graph G into a new graph μ(G)

which is called the Mycielskian of G.The generalized Mycielskians(also known as cones over graphs) μ m(G)(m ≥ 0) are the natural generalization of the Mycielski graphs.In this paper we show that for any connected non-trivial graph G

κ(μ m(G)) = min{δ(G)+1

(m+1)κ(G)+1}

and for m

i ≥ 1

λ(μ m(G)) = λ(G)+i if and only if δ(G) = λ(G)+i 1

where κ(G)

λ(G) and δ(G) are the connectivity

the edge connectivity and the minimum degree of G

respectively.

关键词

Keywords

references

Bondy J A,Murty U S R.Graph Theory[M].Berlin:Springer,2008.

Mycielski J.Sur le colouring des graphes[J].Colloq Math,1955,3:161-162.

Chang G J,Huang L,Zhu X.Circular chromatic number of Mycielski’s graph[J].Discrete Math,1999,205:23-37.

Caramia M,Dell’Olmo P.A lower bound on the chromatic number of Mycielski graphs[J].Discrete Math,2001,235:79-86.

Fan G.Circular chromatic number and Mycielski graphs[J].Combinatoria,2004,24(1):127-135.

Hajibolhassan D,Zhu X.The circular chromatic nmuber and Mycielski construction[J].J Graph Theory,2003,44:106-115.

Lam P C B,Lin W,Gu G,et al.Circular chromatic number and a generalization of the construction of Mycielski[J].J Combin.Theory Ser B,2003,89:195-205.

Liu D.Circular chromatic number for iterated Mycielski graphs[J].Discrete Math,2004,285335-340.

Liu H.Circular chromatic number and Mycielski graphs[J].Acta Math Sci,2006,26B(2):314-320.

Balakrishnan R,Francis Raj S.Connectivity of the Mycielskian of a graph[J].Discrete Math,2008,308:2607-2610.

Guo L,Guo X.Connectivity of the Mycielskian of a digraph[J].Appl Math Lett,2009,22:1622-1625.

Guo L,Liu R,Guo X.Super Connectivity and Super Edge Connectivity of the Mycielskian of a Graph[J].Graphs Combin,DOI10.1007/s00373-011-1032-3.

Tardif C.Fractional chromatic numbers of cones over graphs[J].J Graph Theory,2001,38:87-94.

Larsen M,Propp J,Ullman D.The fractional chromatic number of Mycielski’s graphs[J].J Graph Theory,1995,19:411-416.

Lin W,Wu J,Lam P,et al.Several parameters of generalized Mycielskians[J].Discrete Appl Math,2006,154:1173-1182.

Stiebitz M.Beitra¨ge zur Theorie der fa¨rbungskritschen Graphen[M].Ilmenau:Abilitation Thesis,Thchnical University Ilmenau,1985.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

s-点连通图的路可扩性(英文)

小度数点传递图的连通度(英文)

无限图的笛卡尔积的哈密顿性和连通性

广义笛卡尔积图的连通度

有向循环图的连通度