THE TREE-DEPTH AND CRITICALITY OF UNICYCLIC GRAPHS
Lilith Wagstrom · 2023
The tree-depth of a graph G is defined as the smallest k for which there exists a proper labeling L of G such that is L(x) = L(y) then every x, y-path must contain a vertex z with L(z) > L(x). The graph G is k-critical if it has tree-depth k and every proper minor of G has tree-depth at most k-1. We investigate when unicyclic graphs are critical. Despite unicyclic graphs' relatively simple structure it is surprisingly difficult to classify when they are critical. Part of this difficulty arises from the large variance of structures in unicyclic graphs. We present several families of critical unicyclic graphs that vary greatly in structure. In addition to these results, we present patterns present in the optimal feasible tree-depth labelings of cycles and general graphs.