English

运筹学学报 ›› 2012, Vol. 16 ›› Issue (1): 31-40.

• 运筹学 • 上一篇    下一篇

完全多部图与完全图Kronercker积的点参数研究

唐丹1,王鹤朝1, 单而芳1   

  1. 1.  上海大学数学系, 上海, 200444
  • 收稿日期:2011-01-12 修回日期:2011-10-10 出版日期:2012-03-15 发布日期:2012-03-15
  • 通讯作者: 唐丹 E-mail:tangdan@shu.edu.cn

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

1107

摘要： 若G1和G2是两个图，G1和G2的Kronecker图定义为V (G1×G2)= V (G1) × V (G2 E(G1 × G2)= {(u1,v1)(u2,v2)。在本文中，我们计算了p-部完全图 m1,m2,...,mp 和完全图Kn 的Kronecker积的顶点参数，m1 ≤ m2 ≤ ... ≤ mp,2 ≤ p ≤ n, and n ≥ 3 ，扩展了Mamut和Vumar的相关结论[Inform. Process. Lett. 106(2008)258-262].

关键词: Kronecker积,  , 点脆弱性参数, 割集, 完全$p$-部图, 完全图

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