Fast recognition of some parametric graph families

Nina Klobas

Understanding the cycle (or anticycle) structure in a given graph is fundamentally related to graph families such as trees, perfect graphs, bipartite graphs, (weakly) chordal graphs, pancyclic graphs, and many others. A particularly strong cycle-related property is the notion of cycle-regularity, introduced by Mollard, which has been used to better understand the structure of graph families such as hypercubes or generalized Petersen graphs. In this talk we present three graph families, namely I-graphs, double generalized Petersen graphs and folded cubes and show how their cyclic structure helped us devise linear time recognition algorithms for them.

 Overview  Program