Kronecker çarpım graflarda zedelenebilirlik ölçümleri
Yükleniyor...
Tarih
2016
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Ege Üniversitesi, Fen Bilimleri Enstitüsü
Erişim Hakkı
info:eu-repo/semantics/openAccess
Özet
G1 ve G2 graflarının Kronecker çarpımı, tepeler kümesi V(G1 x G_2)=V(G1) x V(G2), ayrıtlar kümesi E(G1 x G2) = {(u1,v1)(u2,v2):u1u2 Є E(G1) ve v1v2 Є E(G2)} olmak üzere tanımlanmıştır ve G1 x G2 ile gösterilir. Bir G grafının süper bağlantılılık sayısı K'(G) , graftan atıldığında geriye izole tepe içermeyen bağlantısız bir graf bırakan minimum elemanlı tepeler kümesinin eleman sayısıdır. Benzer şekilde, G grafının süper ayrıt-bağlantılılık sayısı λ'(G), graftan atıldığında geriye izole tepe içermeyen bağlantısız bir graf bırakan minimum elemanlı ayrıtlar kümesinin eleman sayısıdır. Bu çalışmada, n≥3, m≥1 ve r≥1 olmak üzere Km,r x Kn grafının süper bağlantılılık sayısının (n-2)(m+r) olduğu, yani Km,r x Kn grafını izole tepe içermeyen bağlantısız bir graf haline getirmek için atılması gereken minimum tepe sayısının (n-2)(m+r) olduğu ispatlanmıştır. Ayrıca, n≥m≥2 ve n ≥ 3 olmak üzere, Km x Kn grafının süper bağlantılılık mn-4 olduğu ispatlanmıştır. Elde edilen bu sonuçlar, 1≤h≤m+r-1 olmak üzere h-ekstra bağlantılılık sayısı için genişletilmiştir. Yani, graftan atıldığında geriye her bir bileşeni h+1 veya daha fazla tepe içeren bağlantısız bir graf bırakan minimum tepe sayısı belirlenmiştir. Ayrıca, verilen bazı koşulları sağlayan m tepeli bir G grafı ile n tepeli bir tam grafın Kronecker çarpımının süper bağlantılılık sayısının n ≥ m iken nK'(G) olduğu ispatlanmıştır. Son olarak, herhangi bir G grafı ele alındığında G X Kn grafının süper ayrıt-bağlantılılık sayısının n≥3 iken min{n(n-1)\λ'(G), minxyЄ(G){deg(x)+\deg(y)}(n-1)-2} olduğu gösterilmiştir.
The Kronecker product of two graphs G1 and G2, denoted by G1 x G2, has vertex set V (G1 X G2) = V (G1)_x V (G2) and edge set E(G1 X G2) = {(u1, v1)(u2, v2) : u1u2 Є E(G1) and v1v2 Є E(G2)}. The super connectivity K’(G) of a graph G is the minimum number of vertices whose deletion results in a disconnected graph without isolated vertices. Analogously, the super edge- connectivity λ’(G) of a graph G is the minimum number of vertices whose deletion results in a disconnected graph without isolated vertices. In this study, it is determined that that the super connectivity of Km,r X_ Kn for n ≥ 3 is (n - 2)(m + r). That is, for n ≥ 3, m ≥ 1 and r ≥ 1, the minimum number of vertices that need to be deleted from G in order to obtain a disconnected graph without isolated vertices is (n-2)(m+r). Moreover, the super connectivity of Km X Kn is determined as mn-4, where n ≥ m ≥ 2 and n ≥ 3. The results are generalized by establishing the h-extra connectivity of Km,r_Kn for n ≥ 3, where 1 ≤ h ≤ m+r-1. More precisely, we determine the smallest number of vertices that need to be removed such that the resulting graph is disconnected and each component has more than h vertices. It is also showed that if G is a maximally connected graph satisfying some given conditions, then k’(G x Kn) = Nk’(G), where n ≥ 3 and n ≥ m. Finally, for any connected graph G, the super edge-connectivity of G x Kn for n ≥ 3 is proved to be min{n(n - 1)λ’(G), minxyЄE(G){deg(x) + deg(y)}(n - 1) – 2}.
The Kronecker product of two graphs G1 and G2, denoted by G1 x G2, has vertex set V (G1 X G2) = V (G1)_x V (G2) and edge set E(G1 X G2) = {(u1, v1)(u2, v2) : u1u2 Є E(G1) and v1v2 Є E(G2)}. The super connectivity K’(G) of a graph G is the minimum number of vertices whose deletion results in a disconnected graph without isolated vertices. Analogously, the super edge- connectivity λ’(G) of a graph G is the minimum number of vertices whose deletion results in a disconnected graph without isolated vertices. In this study, it is determined that that the super connectivity of Km,r X_ Kn for n ≥ 3 is (n - 2)(m + r). That is, for n ≥ 3, m ≥ 1 and r ≥ 1, the minimum number of vertices that need to be deleted from G in order to obtain a disconnected graph without isolated vertices is (n-2)(m+r). Moreover, the super connectivity of Km X Kn is determined as mn-4, where n ≥ m ≥ 2 and n ≥ 3. The results are generalized by establishing the h-extra connectivity of Km,r_Kn for n ≥ 3, where 1 ≤ h ≤ m+r-1. More precisely, we determine the smallest number of vertices that need to be removed such that the resulting graph is disconnected and each component has more than h vertices. It is also showed that if G is a maximally connected graph satisfying some given conditions, then k’(G x Kn) = Nk’(G), where n ≥ 3 and n ≥ m. Finally, for any connected graph G, the super edge-connectivity of G x Kn for n ≥ 3 is proved to be min{n(n - 1)λ’(G), minxyЄE(G){deg(x) + deg(y)}(n - 1) – 2}.
Açıklama
Anahtar Kelimeler
Zedelenebilirlik, Bağlantılılık Sayısı, Süper Bağlantılılık Sayısı, Süper Ayrıt-Bağlantılılık Sayısı, h-Ekstra Bağlantılılık Sayısı, Kronecker Çarpım, Vulnerability, Connectivity, Super Connectivity, Super Edge Connectivity, h-Extra Connectivity, Kronecker Product
