Some generator subgraphs of square tilings / Rodly Angelo S. Rull.

Undergraduate Thesis (BSAM)- Applied Mathematics. Camarines Sur Polytechnic Colleges, 2026.

Includes bibliographical references.

Analyzing the structure of graphs sometimes involves identifying specific sub- graphs that disclose important properties of the graph. One such concept is gen- erator subgraphs, which examine how certain subgraphs are capable of generat- ing the edges on a given graph. Necessary conditions are established for these square tilings to serve as generator subgraphs. All graphs considered in this pa- per are finite simple undirected graphs. Let H be a subgraph of G. Then the set EH(G) = {A ∈ E (G)|G[A] H} denotes the uniform set of H with respect to G while E (G) denotes the subspace of the edge space E (G) generated by EH(G), we adopt the symbol EH(G). The subgraph H of G is a generator subgraph if and only if, EH(G)is a generating set, that is EH(G) = E (G), then H is called a generator subgraph of G. The researcher established that the dimension of edge space of a square tiling is dim(E (□n×m)) = 2nm +n+ m, the cardinality of the uniform set of P4 with respect to □n×m is |EP4 (□n×m)| = 16nm − 6n − 6m. Moreover, this paper provides necessary and sufficient conditions for paths and disjoint union of paths to be generator subgraphs of square tilings. Specifically, this paper provides characterization for star, tadpole graph and hairy cycle, so that these classes of graphs are generator subgraphs of square tilings. The findings of this study contribute to a deeper understanding of a graph structure and its potential applications in various fields of graph theory.