Extensions of domination number and their distribution for random interval catch digraph families

Abstract

Bu tezde çizge kuramsal baskınlık kavramının yeni versiyonlarını geliştiriyoruz. Bunlar, tam p-baskınlık, zayıf p-baskınlık ve güçlü p-baskınlık kavramlarıdır. Bu yeni kavramları,Küme Kapsayıcı Yakalama Yönlü Çizgeleri (KKYYÇler) ve Yakınlık Bölgesi Yakalama Yönlü Çizgeleri (YBYYÇler) olarak isimlendirdiğimiz bazı rassal geometrik çizge ailelerinde göstereceğiz. KKYYÇler ve YBYYÇlerin birbirleri ile yakın bir ilişkisi vardır ve bu rassal çizgelerin desen sınıflandırmaları ve uzaysal nokta desen analizinde uygulamaları vardır. Dahası, YBYYÇler genişleme ve merkez katsayıları ile parametrize edilmiştir. Literatürdeki baskınlık kavramı, bu yönlü çizge aileleri üzerinde çalışılmıştır. Bu yönlü çizge aileleri üzerinde çeşitli baskınlık sayısı versiyonlarının dağılımlarını araştırdık. Özellikle, KKYYÇler için, güçlü p-baskınlık sayısının asimptotik dağılımının dejenere olduğunu gösterdik ve tek boyutlu, düzgün dağılıma sahip verili YBYYÇler için çeşitli baskınlık sayılarının asimptotik dağılımını hesapladık. Teorik bulgular, Monte Carlo simülasyonları ile desteklenmiştir. Bu çalışma, çok boyutlu YBYYÇlerde çeşitli baskınlık formlarının analizine de temel oluşturacaktır.

In this thesis we provide some extensions of the concept of domination in graph theory, namely, exact p-domination, weak p-domination and strong p-domination. We illustrate these new concepts on some random families of geometric graphs called class cover catch digraphs (CCCDs) and proximity catch digraphs (PCDs). PCDs and CCCDs are closely related to each other and have applications in pattern classication and spatial point pattern analysis. Furthermore, PCDs are parameterized by an expansion parameter and a centrality parameter. Previously, usual domination has been investigated thoroughly for these digraph families. We investigate the distribution of various extensions of domination number for these digraph families. In particular, we demonstrate that the asymptotic distribution of strong p-domination number is degenerate for CCCDs. We also derive the asymptotic distribution of the various domination number concepts for PCDs based on one dimensional uniform data. We also perform Monte Carlo simulation experiments, which support our theoretical ndings. This study lays the foundation for the study of the various forms of domination on PCDs based on higher dimensional data.