Premium
The A 4 ‐structure of a graph
Author(s) -
Barrus Michael D.,
West Douglas B.
Publication year - 2012
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20639
Subject(s) - combinatorics , mathematics , vertex (graph theory) , graph , discrete mathematics , indecomposable module , complement graph , distance regular graph , voltage graph , null graph , symmetric graph , hypergraph , line graph , butterfly graph
We define the A 4 ‐ structure of a graph G to be the 4‐uniform hypergraph on the vertex set of G whose edges are the vertex subsets inducing 2 K 2 , C 4 , or P 4 . We show that perfection of a graph is determined by its A 4 ‐structure. We relate the A 4 ‐structure to the canonical decomposition of a graph as defined by Tyshkevich [Discrete Math 220 (2000) 201–238]; for example, a graph is indecomposable if and only if its A 4 ‐structure is connected. We also characterize the graphs having the same A 4 ‐structure as a split graph.