图的生成可圈性（英文）

齐豪; 艾尔肯·吾买尔

doi:10.13568/j.cnki.651094.2015.03.008

您当前的位置：

首页 >

文章列表页 >

图的生成可圈性（英文）

更新时间：2026-01-21

- 图的生成可圈性（英文）
- Journal of Xinjiang University (Natural Science Edition in Chinese and English) Vol. 32, Issue 3, Pages: 292-296(2015)
- 作者机构：
  
  新疆大学数学与系统科学学院
- 作者简介：
- 基金信息：
- DOI：10.13568/j.cnki.651094.2015.03.008
  CLC： O157.5
- Published：2015
- 稿件说明：
移动端阅览
[1]齐豪,艾尔肯·吾买尔.图的生成可圈性（英文）[J].新疆大学学报(自然科学版),2015,32(03):292-296.
[1]齐豪,艾尔肯·吾买尔.图的生成可圈性（英文）[J].新疆大学学报(自然科学版),2015,32(03):292-296. DOI： 10.13568/j.cnki.651094.2015.03.008.

DOI：10.13568/j.cnki.651094.2015.03.008.

摘要

给定一个图G=(V

E)及其顶点集V的互不相交的非空子集A1

···

如果存在互不相交的圈C1

···

Cr满足Ai?V(Ci)(i=1

···

r)并且C1∪C2∪···∪Cr生成G

则称G是关于子集A1

···

Ar生成可圈的.如果G关于V的任意r个互不相交的子集A1

···

Ar都是生成可圈的

则称G是r-生成可圈的.进一步

如果G对于任意满足|A1∪A2∪···∪Ar|≤t的互不相交的点子集A1

···

Ar是r-生成可圈的

则称G是阶数为t的r-生成可圈图.本文中

我们证明了:如果G是顶点数n≥3r+1

边数m≥(n-1)(n-2)2+k+r-2(r≥1

3≤k≤n-r+1)的图

则G是阶数为k+r-3的r-生成可圈图.本文将文献[1]中r=2的结果推广到了一般的情形.

Abstract

Given a graph G =(V

E) and mutually disjoint nonempty subsets A1

...

Arof V

we say that G is spanning cyclable with respect to A1

· · ·

Arif there exist mutually disjoint cycles C1

· · ·

Crsuch that AiV(Ci)for i = 1

· · ·

r and C1∪ C2∪ · · · ∪ Crspans G. And G is r-spanning-cyclable if G is spanning cyclable with respect to A1

...

Arfor every such mutually disjoint nonempty subsets of V. Moreover

we say that G is r-spanning-cyclable of order t if G is spanning cyclable with respect to A1

· · ·

Arfor any r nonempty mutually disjoint subsets A1

· · ·

Ar of V such that |A1∪ A2∪ · · · ∪ Ar| ≤ t. In this paper we prove if G is a graph of order n ≥ 3r + 1(r ≥ 1) and has at least(n-1)(n-2)2+ k + r-2edges for 3 ≤ k ≤ n- r + 1

then G is r-spanning-cyclabe of order k + r- 3. Our result extends the resultobtained by Cheng et al. in [1] for r = 2.

关键词

Keywords

references

Cheng E,Hsu L-H,Lin C-K,L′aszl′o L.On the cyclability of graphs[J].J Combinatorial Mathematics and Combinatorial Computing,to appear(2014).

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

Albert M,Aldred R E L,Holton D.On 3*-connected graphs[J].Austral J Comb,2001,24:193-208.

Hsu L-H,Lin C-K.Graph Theory and Interconnection Networks[M].CRC Press,Taylor&Francis Group,2009.

Faudree R J.Survey of results on k-ordered graphs[J].Discrete Math,2001,229:73-87.

Faudree R J,Gould R,Kostochka A V,Lesniak L,Schiermeyer I,Saito A.Degree conditions for k-ordered hamiltonian graphs[J].J Graph Theory,2003,42:199-210.

Ng L,Schultz M.k-Ordered hamiltonian graphs[J].J Graph Theory,1997,24:45-57.

Lin C-K,Tan J J M,Hsu L-H,Tzu L-K.Disjoint cycles in hypercubes with prescribed vertices in each cycle[J].Discrete Appl Math,2013,161:2992-3004.

Ore O.Arc coverings of graphs[J].Annali di Matematica Pura ed Applicata,1961,55:315-321.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

拟无爪哈密尔顿图的邻集条件(英文)

Related Author

马小玲

Related Institution

No data

⁰