关于直积图的坚韧度和边坚韧度的注记（英文）

热西旦·湖加

doi:10.13568/j.cnki.651094.2016.04.006

您当前的位置：

首页 >

文章列表页 >

关于直积图的坚韧度和边坚韧度的注记（英文）

更新时间：2026-01-21

- 关于直积图的坚韧度和边坚韧度的注记（英文）
- Journal of Xinjiang University (Natural Science Edition in Chinese and English) Vol. 33, Issue 4, Pages: 407-410(2016)
- 作者机构：
  
  1. 福州大学离散数学研究中心
  2. 新疆财经大学应用数学学院
- 作者简介：
- 基金信息：
- DOI：10.13568/j.cnki.651094.2016.04.006
  CLC： O157.5
- Published：2016
- 稿件说明：
移动端阅览
[1]热西旦·湖加.关于直积图的坚韧度和边坚韧度的注记（英文）[J].新疆大学学报(自然科学版),2016,33(04):407-410.
[1]热西旦·湖加.关于直积图的坚韧度和边坚韧度的注记（英文）[J].新疆大学学报(自然科学版),2016,33(04):407-410. DOI： 10.13568/j.cnki.651094.2016.04.006.

DOI：10.13568/j.cnki.651094.2016.04.006.

摘要

图G的坚韧度t(G)定义为:对非完全图是t(G)=min{|S|/ω(G-S)|SV(G)

ω(G-S)≥2}

而对完全图是∞

其中ω(G-S)表示G-S的连通分支数.边坚韧度定义为t′(G)=min{|X|/ω(G-X)-1|X是G的边割集}.在本文中

我们给出了完全图和圈的直积图的坚韧度

并且提供了完全图和正则图类的直积图的边坚韧度公式.

Abstract

The toughness t(G) of a noncomplete graph G is defined as t(G) = min{|S|/ω(G-S) | S(?) V(G)

ω(G-S) > 2}and the toughness of a complete graph is ∞

where ω(G- S) is

the number of connected components of G- S.The edge-toughness t′(G) of G is defined as t'(G) = min{(|X|)/(ω(G-X)-1) X is an edge-cut set of G}.In this paper

we determine the toughness of Kronecker product of a complete graph and a cycle

and supply formulae for the edge-toughness of Kronecker product of a complete graph and regular graphs.

关键词

Keywords

references

West D B.Introduction to Graph Theory(2nd Edition)[M].NJ Upper Saddle River:Prentice Hall,2001.

Chvatal V.Tough graphs and Hamiltonian circuits[J].Discrete Math,1973,5:215-228.

Bauer D,Morgana A,Schmeichel E.On the complexity of recognizing tough graphs[J].Discrete Math,1994,124:13-17.

Pippert R E.On the toughness of a graph[J].Lecture Notes in Math,1972,303:225-233.

Goddard W D,Swart H C.On the toughness of a graph[J].Quasstiones Mathematics,1990,13:217-232.

Mamut A,Vumar E.Vertex vulnerability parameters of Kronecker product of complete graphs[J].Inform Process Lett,2008,106:258-262.

Guji R,Ali T.Toughness of Kronecker products of graphs[J].Ars Combin,2016,127:149-156.

Peng Y H,Chen C C,Koh K M.On the edge-toughness of a graph(1)[J].Southeast Asian Math Bull,1988,12:109-122.

Tutte W T.On the problem of decomposing a graph into n connected factors[J].London Math Soc,1961,36:221-230.

Nash-Williams C St J A.Edge-disjoint spanning trees of finite graphs[J].J London Math Soc,1961,36:445-450.

Gusfield D.Connectivity and edge-disjoint spanning trees[J].Inform Process Lett,1983,16:87-89.

Alon N,Lubetzky E.Independent sets in tensor graph powers[J].J Graph Theory,2007,54:73-87.

Bresar B,Imrich W,Klavzar S,et al.Hypercubes as direct products[J].SIAM J Discrete Math,2005,18:778-786.

Lammprey RH,Barnes B H.Products of graphs and applications[J].Modeling and Simulation,1974,5:1119-1123.

Ghozati S A.A finite automata approach to modeling the cross product of interconnection networks[J].Mathematical and Computer Modeling,1999,30:185-200.

Bottreou A,Mgtivier Y.Some remarks on the Kronecker product of graphs[J].Inform Process Lett,1998,68:55-61.

Peng Y H,Tay T S.On the edge-toughness of a graph(2)[J].J Graph Theory,1993,17:233-246.

Cao X L,Brglez S,S pacapan S,et al.On edge connectivity of direct products of graphs[J].Inform Process Lett,2011,111:889-902.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

一类正则图的边坚韧度(英文)

一些特殊图类乘积的离散度(英文)

Related Author

买吐肉孜·买司地克

艾山江·吾素音

吕明富

阿依古丽.马木提

艾尔肯.吾买尔

边红

Related Institution

新疆大学数学与系统科学学院,新疆师范大学数理信息学院,新疆喀什师范学院数理系新疆乌鲁木齐830046,新疆乌鲁木齐830054

新疆大学数学与系统科学学院,新疆大学数学与系统科学学院,新疆大学数学与系统科学学院新疆乌鲁木齐830046,新疆乌鲁木齐830046

⁰