Lattanzio and Zheng Publish on Generalized Matrix Graphs and Completely Independent Critical Cliques

Posted on 6/28/2012 11:28:30 AM

John Lattanzio and Quan Zheng (M.S. ’10) published “Generalized Matrix Graphs and Completely Independent Critical Cliques in any Dimension” in Discussiones Mathematicae Graph Theory 32(3) (2012) 583-602.

The article stems from work Lattanzio did with Quan while Quan was a graduate student in the Mathematics Department.


For natural numbers k and n, where 2 ≤ k ≤ n, the vertices of a graph are labeled using the elements of the k-fold Cartesian product In×In× …×In.

Two particular graph constructions will be given and the graphs so constructed are called generalized matrix graphs. Properties of generalized matrix graphs are determined and their application to completely independent critical cliques is investigated. It is shown that there exists a vertex critical graph which admits a family of k completely independent critical cliques for any k, where k ≥ 2. Some attention is given to this application and its relationship with the double-critical conjecture that the only vertex double-critical graph is the complete graph.