Zero forcing in graphs

Abstract

Verilen bir ?? çizgesi için, renk değiştirme kuralı, ??'nin tüm köşeleri siyah veya beyaz renkliyse ve ??'nin siyah bir köşesi olan ??'nun yalnızca bir beyaz komşusu ?? varsa, ??'nin renginin siyaha değiştirileceğini söyleyen bir çizge renklendirme kuralıdır. ??'nin sıfır zorlama sayısı, ??'nin tüm beyaz köşelerini siyaha boyamak için başlangıçta alınması gereken ??'nin minimum siyah köşe sayısıdır. Bu tezde, bazı özel çizgelerin sıfır zorlama sayıları literatürde yer alan çalışmalarla birlikte incelenmiştir. Özellikle, durum analizi ve tümevarım kullanarak bazı özel çizgelerin güçlü çarpımlarının sıfır zorlama sayılarını bulmaya odaklanıyoruz.

For given a graph ??, the color-change rule is a graph coloring rule which satisfies that if all vertices of ?? are colored black or white and a black vertex ?? of ?? has a unique white neighbor ??, then the color of ?? is changed to black. The zero forcing number of ?? is the minimum number of black vertices of ?? that must be taken initially to color all white vertices of ?? to black. In this thesis, we study the zero forcing numbers of some special graphs with together the works in the literature. In particular, we focus on finding the zero forcing numbers of the strong product of some special graphs using case analysis and induction.