A Note on Triple Repetition Sequence of Domination Number in Graphs

Abstract

A set D subset of V(G) is a dominating set of a graph G if for all x ϵ V(G)\D, for some y ϵ D such that xy ϵ E(G). A dominating set D subset of V(G) is called a connected dominating set of a graph G if the subgraph <D> induced by D is connected. A connected domination number of G, denoted by γ_c(G), is the minimum cardinality of a connected dominating set D. The triple repetition sequence denoted by {S_n:n ϵ Z+} is a sequence of positive integers which is repeated thrice, i.e., {S_n}={1,1,1,2,2,2,3,3,3, ...}. In this paper, we construct a combinatorial explicit formula for the triple repetition sequence of connected domination numbers of a triangular grid graph.

Keywords: connected domination number; triangular grid graph; triple repetition sequence.

Abstrak

Suatu himpunan D subhimpunan dari V(G) adalah himpunan pendominasi graf G apabila untuk semua x ϵ V(G)\D, untuk suatu y ϵ D sehingga xy ϵ E(G). Suatu himpunan pendominasi D subhimpunan dari V(G) dikatakan himpunan pendominasi terhubung dari graf G apabila subgraf <D> yang diinduksi oleh D terhubung. Suatu bilangan pendominasi dari G, dinotasikan dengan γ_c(G), adalah kardinalitas minimum dari himpunan pendominasi terhubung D. Barisan pengulangan rangkap tiga yang dinotasikan dengan {S_n:n ϵ Z+} adalah suatu barisan bilangan bulat positif yang setiap sukunya berulang tiga kali, yakni, {S_n}={1,1,1,2,2,2,3,3,3, ...}. Dalam paper ini dikonstruksi suatu rumus eksplisit kombinatorial untuk barisan pengulangan rangkap tiga dari bilangan pendominasi terhubung graf grid triangular.

Kata Kunci: bilangan pendominasi terhubung; graf grid triangular; barisan pengulangan rangkap tiga.

2020MSC: 05C69