中文

Operations Research Transactions ›› 2012, Vol. 16 ›› Issue (1): 31-40.

• Original Articles • Previous Articles     Next Articles

Vertex vulnerability parameters of Kronecker products of complete multipartite graphs and complete graphs

 TANG  Dan1, WANG  He-Chao1, DAN  Er-Fang1   

  1. 1. Department of Mathematics, Shanghai University, Shanghai 200444,  China
  • Received:2011-01-12 Revised:2011-10-10 Online:2012-03-15 Published:2012-03-15
  • Contact: Dan Tang E-mail:tangdan@shu.edu.cn
  • Supported by:

    This Research was partially supported by PuJiang Project of Shanghai (No. 09PJ1405000), The National Nature Science Foundation of China (No. 11171207) and Shanghai Leading Academic Discipline Project (No. S30104).

PDF

1100

Abstract: Let G_1 and G_2 be two graphs. The Kronecker product G_1\times G_2 is defined as V(G_1\times G_2)=V(G_1)\times V(G_2) and E(G_1\times G_2)=\{(u_1,v_1)(u_2,v_2):u_1u_2\in E(G_1) and v_1v_2\in E(G_2)\}. In this paper we compute several vertex vulnerability parameters of Kronecker product of a complete p-partite graph K_{m_{1},m_{2},\ldots,m_{p}} and a complete graph K_n on n vertices, where m_{1}\leq m_{2}\leq \ldots \leq m_{p}, 2\leq p\leq n, and n\geq3. This result generalizes the previous result by Mamut and Vumar.

Key words: Kronecker product, vertex vulnerability parameter, cut set, complete $p$-partite graph, complete graph