On Stratified Domination Numbers in Graphs

Abstract

Bir G grafının tepeleri kümesinin iki renk sınıfına parçalanışı varsa, bu G grafı 2-parçalanışlı graftır. Bu tepelerin bir sınıfı kırmızıyla diğer sınıfıda maviyle renklendirilir. F, belirli bir v mavi tepesini kök kabul eden iki parçalanışlı graf olsun. Bir G grafının F üstünlük sayısı, G nin tepelerinin bir kırmızı- mavi renklendirmesinde G nin kırmızı tepelerinin minimum sayısıdır öyle ki G nin her v mavi tepesi kökü v olan F nin bir nüshasına aittir. F={F1,?,Fk} olsun. Burada Fi , 1?i?k , belirli bir v mavi tepesini kök kabul eden iki parçalanışlı graftır. Bir G grafının F*-üstünlük sayısı, G nin tepelerinin bir kırmızı- mavi renklendirmesinde G nin kırmızı tepelerinin minimum sayısıdır öyle ki G nin her v mavi tepesi kökü v olan Fi nin en az bir nüshasına aittir. Bu çalışmada F, 2-parçalanışlı 6-çevre grafı olmak üzere prizmaların F-üstünlük sayısı incelenerek konuyla ilgili bir genelleştirme teoremi ispat edildi . Aynı zamanda F* , 2-parçalanışlı 3-yol graflarının iki tepesi kırmızı olan bir ailesi olmak üzere bir grafın F* -üstünlük sayıları ile 2-gökkuşağı üstünlük sayıları arasındaki ilişki belli graf sınıfları ve rastgele seçilmiş bazı graf sınıfları için incelenerek, herhangi bir birleştirilmiş G grafı için 2-gökkuşağı üstünlük sayısının, F* -üstünlük sayısına eşit yada F*-üstünlük sayısından bir fazla olduğu tahmininde bulunulmuştur. Bunlara ilaveten bir grafın F*-üstünlük sayıları ile bu grafın maksimum derecesi ve mertebesi arasındaki ilişki incelenmiştir.Anahtar Kelimeler: 2-Gökkuşağı üstünlük sayısı, 2-Parçalanışlı üstünlük sayısı, Prizma

A graph G is 2-stratified if its vertex set partitioned into two color classes. We color the vertices in one color class red and the other class blue. Let F be 2-stratified graph rooted at one fixed blue vertex v specified. The F-domination number of a graph G is the minimum number of red vertices of G in a red-blue coloring of the vertices of G such that every blue vertex v of G belongs to a copy of F rooted at v. Let F={F1,?,Fk}, where Fi , 1?i?k , is a 2- stratified graph rooted at some blue vertex v. The F* -domination number of G is defined as the minimum number red vertices of G in a red-blue coloring of the vertices of G such that every blue vertex v of G belongs to a copy of Fi rooted at v for at least one value of i. In this study we investigate the F-domination number of prisms when F is 2-stratified 6-cycle rooted at a blue vertex. And we proved one generalization result. Also we study the relation between 2-rainbow domination number and F* -domination number for some known graph classes and randomly chosen graphs when F* is the family of 2-stratified paths of length 3 in which two vertices are colored red. We conjectured that 2-rainbow domination number is equal or greater than F*-domination number by one for any connected graph G. In addition the relation between F*-domination number and maximum degree and order were studied.Key Words: 2-Rainbow dominaton number, 2-Stratified domination number, Prism