On Induced Subgraphs, Degree Sequences, and Graph Structure

Abstract

Finally, we define the A4-structure H of a graph G to be the 4-uniform hypergraph on the vertex set of G where four vertices comprise an edge in H if and only if they form the vertex set of an alternating 4-cycle in G. Our definition is a variation of the notion of the P4-structure, a hypergraph which has been shown to have important ties to the various decompositions of a graph. We show that A4-structure has many properties analogous to those of P4-structure, including connections to a special type of graph decomposition called the canonical decomposition. We also give several equivalent characterizations of the class of A4-split graphs, those having the same A4-structure as some split graph.