Title:
Alternating 4-Cycles in Graphs
Abstract:
An alternating 4-cycle in a graph is a configuration of four vertices cyclically ordered so that consecutive pairs are alternately adjacent and non-adjacent. Alternating 4-cycles play a key role in linking graphs with the same degree sequence. They are also fundamental to characterizations of such graph classes as the threshold and matrogenic graphs. Until recently attention has focused primarily on the existence or absence of alternating 4-cycles in a graph;
less was known about how the locations of these configurations affects the global structure and degree sequence of a graph.
We introduce the A4-structure of a graph G as the 4-uniform hypergraph on the vertex set of G whose edges are the vertex sets of alternating 4-cycles in G. We show that certain graph properties, such as perfection and the sizes and locations of matchings, may be determined by the A4-structure. By comparing the A4-structure with a similar path structure, we make a surprising connection with decompositions of graphs and degree sequences defined by Tyshkevich (2000), placing these decompositions in context and providing solid new motivation for them. With our new understanding of alternating 4-cycles, we suggest potentially interesting classes of graphs that generalize the threshold and matrogenic graphs and examine one of them, the A4-split graphs, in detail. This is joint work with Douglas B. West.