2015/02/18 by Michael D. Barrus, Barrus, Michael D., John Sinkovic +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Graph Labeling and Dimension Problems #math.CO
paper · pdf · doi:10.48550/arxiv.1502.05277
8 pages, 2 figures; this note is a supplement to arXiv:1310.1116v2
arxiv created 2015/02/18 · openalex publication_date 2015/02/18 · arxiv updated 2015/02/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A k-ranking of a graph G is a labeling of the vertices of G with values from 1,...,k such that any path joining two vertices with the same label contains a vertex having a higher label. The tree-depth of G is the smallest value of k for which a k-ranking of G exists. The graph G is k-critical if it has tree-depth k and any proper minor of G has smaller tree-depth, and it is 1-unique if for every vertex v in G, there exists an optimal ranking of G in which v is the unique vertex with label 1. We present several classes of graphs that are both k-critical and 1-unique, providing examples that satisfy conjectures on critical graphs discussed in [M.D. Barrus and J. Sinkovic, Uniqueness and minimal obstructions for tree-depth, submitted].