Semester
Spring
Date of Graduation
2022
Document Type
Dissertation
Degree Type
PhD
College
Eberly College of Arts and Sciences
Department
Mathematics
Committee Chair
John Goldwasser
Committee Co-Chair
Cun-Quan Zhang
Committee Member
Cun-Quan Zhang
Committee Member
Jerzy Wojciechowski
Committee Member
Hong-Jian Lai
Committee Member
Elaine Eschen
Abstract
If G is a graph and H is a set of subgraphs of G, an edge-coloring of G is H-polychromatic if every graph from H gets all colors present in G on its edges. The H-polychromatic number of G, polyHG, is the largest number of colors in an H-polychromatic coloring. We determine polyHG exactly when G is a complete graph on n vertices, q a fixed nonnegative integer, and H is the family of one of: all matchings spanning n-q vertices, all 2-regular graphs spanning at least n-q vertices, or all cycles of length precisely n-q.
For H, K, subsets of the vertex set V(Qd) of the d-cube Qd, K is an exact copy of H if there is an automorphism of Qd sending H to K. For a positive integer, d, and a configuration in Qd, H, we define λ(H,d) as the limit as n goes to infinity of the maximum fraction, over all subsets S of V(Qn), of sub-d-cubes of Qn whose intersection with S is an exact copy of H.
We determine λ(C8,4) and λ(P4,3) where C8 is a “perfect” 8-cycle in Q4 and P4 is a “perfect” path with 4 vertices in Q3, λ(H,d) for several configurations in Q2, Q3, and Q4, and an infinite family of configurations.
Strong connections exist with extensions Ramsey numbers for cycles in a graph, counting sequences with certain properties, inducibility of graphs, and we determine the inducibility of two vertex disjoint edges in the family of bipartite graphs.
Recommended Citation
Hansen, Ryan Tyler, "Polychromatic colorings of certain subgraphs of complete graphs and maximum densities of substructures of a hypercube" (2022). Graduate Theses, Dissertations, and Problem Reports. 11291.
https://researchrepository.wvu.edu/etd/11291
