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.

Download

Share

COinS