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).
