Toughness of Kronecker product of graphs

被引：0

作者：

Guji, Raxida ^{[1
,2
]}

Ali, Tursun ^{[2
]}

机构：

[1] Fuzhou Univ, Ctr Discrete Math, Fuzhou 350002, Fujian, Peoples R China

[2] Xinjiang Univ Finance & Econ, Sch Appl Math, Urumqi 830012, Peoples R China

来源：

ARS COMBINATORIA | 2016年 / 127卷

关键词：

toughness; Kronecker product; complete graph; CONNECTIVITY;

D O I：

暂无

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The toughness t(G) of a noncomplete graph G is defined as t(G) = min{vertical bar S vertical bar/omega(G - S) vertical bar S subset of V(G), omega(G - S) >= 2} and the toughness of a complete graph is infinity, where omega(G - S) is the number of connected components of G - S. In this paper, we give the sharp upper and lower bounds for Kronecker product of a complete graph and a tree. Moreover, we determine the toughness of Kronecker product of a complete graph and a star, a path, respectively.

引用

页码：149 / 156

页数：8

共 13 条

[1] Independent sets in tensor graph powers [J].

Alon, Noga ;

Lubetzky, Eyal .

JOURNAL OF GRAPH THEORY, 2007, 54 (01) :73-87

[2] ON THE COMPLEXITY OF RECOGNIZING TOUGH GRAPHS [J].

BAUER, D ;

MORGANA, A ;

SCHMEICHEL, E .

DISCRETE MATHEMATICS, 1994, 124 (1-3) :13-17

[3] Some remarks on the Kronecker product of graphs [J].

Bottreau, A ;

Metivier, Y .

INFORMATION PROCESSING LETTERS, 1998, 68 (02) :55-61

[4] Hypercubes as direct products [J].

Bresar, B ;

Imrich, W ;

Klavzar, S ;

Zmazek, B .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2005, 18 (04) :778-786

[5]

Chvatal V., 1973, Discrete Mathematics, V5, P215, DOI 10.1016/0012-365X(73)90138-6

[6] A finite automata approach to modeling the cross product of interconnection networks [J].

Ghozati, SA .

MATHEMATICAL AND COMPUTER MODELLING, 1999, 30 (7-8) :185-200

[7]

Goddard W.D., 1990, Quaestiones Math, V13, P217

[8]

Lammprey R., 1974, Model Simul, V5, P1119

[9] Vertex vulnerability parameters of Kronecker products of complete graphs [J].

Mamut, Aygul ;

Vumar, Elkin .

INFORMATION PROCESSING LETTERS, 2008, 106 (06) :258-262

[10]

Pippert R.E., 1972, Lecture Notes in Math, V303, P225

← 1 2 →