West Virginia University
Polychromatic colorings of certain subgraphs of complete graphs and maximum densities of substructures of a hypercube
Abstract
dc:description.abstractIf 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.
Degree
thesis:*- Name thesis:degree_name
- PhD
- Level thesis:degree_level
- Dissertation
- Discipline thesis:degree_discipline
- Mathematics
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Hansen, Ryan Tyler
- Contributors dc:contributor
-
- John Goldwasser
- Cun-Quan Zhang
- Jerzy Wojciechowski
- Hong-Jian Lai
- Elaine Eschen
Subjects
dc:subject × 8Identifiers
dc:identifier.*- Identifier
- https://researchrepository.wvu.edu/etd/11291