Kronecker çarpım graflarda zedelenebilirlik ölçümleri
Reliability parameters on Kronecker product graphs
Yazar: GÜLNAZ BORUZANLI EKİNCİ
Danışman: PROF. DR. ALPAY KIRLANGIÇ
Ege Üniversitesi / Fen Bilimleri Enstitüsü / Matematik Ana Bilim Dalı
Derece: Doktora, 2016
Konu: Matematik = Mathematics

Özet:
$ G_1 $ ve $ G_2 $ graflarının Kronecker çarpımı,  tepeler kümesi $ V(G_1 \times G_2)=V(G_1)\times V(G_2) $, ayrıtlar kümesi  $ E(G_1 \times G_2) = \{(u_1,v_1)(u_2,v_2):u_1u_2 \in E(G_1) \text{ ve }  v_1v_2 \in E(G_2)\} $ olmak üzere tanımlanmıştır ve $ G_1 \times G_2 $ ile gösterilir. Bir $ G $ grafının süper bağlantılılık sayısı $ \kappa'(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ı $ \lambda'(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\geq3 $, $ m\geq1$ ve $ r\geq1 $  olmak üzere $ K_{m,r} \times K_n $ grafının süper bağlantılılık sayısının $ (n-2)(m+r) $ olduğu, yani $ K_{m,r} \times K_n $ 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 \geq m \geq 2 $ ve $ n \geq 3 $ olmak üzere, $ K_m \times K_n $ grafının süper bağlantılılık sayısının $ mn-4 $ olduğu ispatlanmıştır. Elde edilen bu sonuçlar, $1\leq h \leq 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 \geq m $ iken $ n\kappa'(G)$ olduğu ispatlanmıştır. Son olarak, herhangi bir $ G $ grafı ele alındığında $ G\times K_n $ grafının süper ayrıt--bağlantılılık sayısının $ n\geq3 $ iken  $ \min\{n(n-1)\lambda'(G), \min_{xy\in E(G)}\{\deg(x)+\deg(y)\}(n-1)-2\} $ olduğu gösterilmiştir.

Abstract:
The Kronecker product of two graphs $ G_1 $ and $ G_2 $, denoted by $ G_1 \times G_2 $, has vertex set $ V(G_1 \times G_2)=V(G_1)\times V(G_2) $ and edge set $ E(G_1 \times G_2) = \{(u_1,v_1)(u_2, v_2) : u_1u_2 \in E(G_1) \text{ and }  v_1v_2 \in E(G_2)\} $. The super connectivity $ \kappa'(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 $ \lambda'(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 $ K_{m,r} \times K_n $ for $n\geq3 $ is $ (n-2)(m+r) $. That is, for $ n\geq3 $, $ m\geq1$ and $ r\geq1 $, 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 $ K_m \times K_n $ is determined as $ mn-4 $, where $ n \geq m \geq 2 $ and $ n \geq 3 $. The results are generalized by establishing the $ h$--extra connectivity of  $ K_{m,r} \times K_n $ for $ n\geq3 $, where $1\leq h \leq m+r-1 $. More precisely, we show that the smallest number of vertices that need to be removed so 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 $\kappa'(G \times K_n ) = n\kappa'(G)$, where $n\geq3 $ and $ n \geq m$. Finally, for any connected graph $ G $, the super edge--connectivity of $ G \times K_n $ for $n\geq3 $ is proved to be $ \min\{n(n-1)\lambda'(G), \min_{xy\in E(G)}\{\deg(x)+\deg(y)\}(n-1)-2\} $.