Super connectivity of Kronecker product of complete bipartite graphs and complete graphs
Küçük Resim Yok
Tarih
2016
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Elsevier Science Bv
Erişim Hakkı
info:eu-repo/semantics/closedAccess
Özet
Let G(1) and G(2) be two graphs. The Kronecker product G(1) x G(2) has vertex set V(G(1) x G(2)) = V(G(1)) x V(G(2)) and edge set E(G(1) x G(2)) = {(u(1), v(1))(u(2), v(2)) : u(1)u(2) epsilon E(G(1)) and v(1)v(2) epsilon E(G(2))}. In this paper we determine that the super-connectivity of K-m,K-r x K-n for n >= 3 is (n = 2)(m + r). That is, for n >= 3, m >= 1 and r >= 1, at least (n - 2)(m + r) vertices need to be removed to get a disconnected graph that contains no isolated vertices. We also determine that the super-connectivity of K-m x K-n is mn - 4, where n >= m >= 2 and n >= 3. We generalize our result by establishing the h-extra-connectivity of K-m,K-r x K-n, for n >= 3, where 1 <= h <= m + r - 1. More precisely we show that the smallest number of vertices that need to be removed from K-m,K-r x K-n so that the resulting graph is disconnected and each component has more than h vertices is (n - 2)(m + r). (C) 2015 Elsevier B.V. All rights reserved.
Açıklama
7th Cracow Conference on Graph Theory -- SEP 14-19, 2014 -- Rytro, POLAND
Anahtar Kelimeler
Connectivity, Super connectivity, h-extra connectivity, Kronecker product, Fault tolerance
Kaynak
Discrete Mathematics
WoS Q Değeri
Q3
Scopus Q Değeri
Q1
Cilt
339
Sayı
7
