IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Tiling the n-cube Graph with Copies of a Given Graph

  • Oct. 26, 2015
  • 3:30 p.m.
  • LeConte 312


We say that a graph G tiles the n-cube graph Q_n if V(Q_n) can be partitioned into blocks V_1, V_2,... so that for all i, the induced subgraph on V_i is isomorphic to G. We then propose this graph packing problem: For which graphs G does there exist an n such that G tiles Q_n? Easily, when G tiles Q_n, it tiles Q_{n’} for all n'>n, so a more precise question is to determine the minimum value of n, denote it t(G), such that G tiles Q_n. While these general questions remain open, we have several results to share, using techniques that include linear algebra, coding theory, and matching theory. This is joint work with Kevin Milans, David Offner, and David Stoner.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster