Domination on non-Cayley vertex transitive graphs

Abstract

G çizgesinde bir dominasyon kümesi, S'de olmayan her köşenin S'de komşusunun olduğu köşeler alt kümesidir ve S dominasyon sayısı S'nin sahip olabileceği minimum kardinalitedir. G çizgesinde bir tam dominasyon kümesi V'deki her köşenin S'de komşusunun olduğu S köşeler alt kümesidir ve tam dominasyon sayısı S'nin sahip olabileceği minimum kardinalitedir. Her Cayley çizgesi Cay(G, A) köşe geçişlidir ama tersi doğru değildir. En iyi bilinen örneği Petersen çizgesidir. Bu tezde Cayley olmayan köşe geçişli çizgeler üzerinde çalışılacaktır. n ve k iki pozitif tam sayı olsun. Kneser çizgesi K(n,k), köşeleri n-elemanlı kümenin k- elemanlı alt kümelerinden oluşan ve iki köşenin ancak ve ancak ayrık kümelere karşılık gelmesi durumunda komşu olduğu çizgedir. Johnson çizgesi J(n,k), Kneser çizgesiyle aynı köşelere sahiptir ve iki köşe ancak ve ancak kesişimleri k-1 elemanlı ise komşudur. k=2 için Johnson çizgesi J(n,2), Kneser çizgesi K(n,2)'nin tümleyenidir. Bu tezde Tek Kneser çizgeleri ve Johnson çizgeleri gibi bazı Cayley olmayan köşe geçişli çizgeler üzerinde dominasyon ve tam dominasyon kümelerini inceleyeceğiz. Ayrıca Johnson çizgesinin dominasyon sayılarını veya iligi sınırları bulmaya odaklanacağız.

A dominating set in a graph G is a vertex subset S such that every vertex not in S has a neighbor in S, and domination number is the minimum cardinality of S. A total dominating set in a graph G is a vertex subset S such that every vertex in V is adjacent to some vertex in S and total domination number is the minimum cardinality of S. Every Cayley graph Cay(G, A) is vertex-transitive but the converse is not true. A well-known example is the Petersen graph. In this thesis we will focus on non-Cayley vertex transitive graphs. Let n and k be two positive integers, the Kneser graph K(n,k) is the graph whose vertices represent the k-subsets of n-element sets and where two vertices are adjacent if and only if they correspond to disjoint subsets. Johnson graph J(n,k) has same vertex set with the Kneser graph and two vertices are adjacent if and only if their intersection has k-1 elements. For k=2, The Johnson graph J(n, 2) is the complement of the Kneser graph K(n, 2). In this thesis we will study dominating sets and total dominating sets on some specific non-Cayley vertex-transitive graphs such as Odd Kneser graphs and Johnson graphs. Then we will focus on finding the domination numbers or boundaries for the Johnson graph.