On Induced Subgraphs, Degree Sequences, and Graph Structure

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2015

Author dc:creator

• Barrus, Michael David

Contributors dc:contributor

• West, Douglas B.

• Mathematics

Language dc:language

eng

Identifier

(MiAaPQ)AAI3362726

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/86921