# On the Domination Number for a Family of Semiregular Tiling Graphs

## Mentor 1

Pamela Harris

## Start Date

28-4-2023 12:00 AM

## Description

Let G = (V, E) be a simply connected undirected finite graph with vertex set V and edge set E. A set of vertices D ⊆ V is said to dominate G if every vertex v ∈ V is in D or adjacent to a vertex in D. We let γ(G) denote the smallest cardinality among all dominating sets of G. In 1992, Chang gave an upper bound for γ(G) when G is a large grid graph and conjectured that this bound was an equality whenever n ≥ m ≥ 16 [1]. In 2011, Gonçalves, Pinlou, Rao, and Thomassé proved Chang’s conjecture by showing that a lower bound was exactly the upper bound. In this project, we consider a tessellation of the plane using regular octagons and squares. From this tessellation, we create a graph for each n, m ∈ Z≥0 consisting of n rows, and m columns of regular octagons. We denote these graphs by Hnm and establish a formula for enumerating the vertices in Hnm, and use this result to give an upper bound for γ(Hnm).

On the Domination Number for a Family of Semiregular Tiling Graphs

Let G = (V, E) be a simply connected undirected finite graph with vertex set V and edge set E. A set of vertices D ⊆ V is said to dominate G if every vertex v ∈ V is in D or adjacent to a vertex in D. We let γ(G) denote the smallest cardinality among all dominating sets of G. In 1992, Chang gave an upper bound for γ(G) when G is a large grid graph and conjectured that this bound was an equality whenever n ≥ m ≥ 16 [1]. In 2011, Gonçalves, Pinlou, Rao, and Thomassé proved Chang’s conjecture by showing that a lower bound was exactly the upper bound. In this project, we consider a tessellation of the plane using regular octagons and squares. From this tessellation, we create a graph for each n, m ∈ Z≥0 consisting of n rows, and m columns of regular octagons. We denote these graphs by Hnm and establish a formula for enumerating the vertices in Hnm, and use this result to give an upper bound for γ(Hnm).