Discrete Mathematics Group at URI
The faculty of our group is interested in a wide range of areas in discrete mathematics
both pure and applied: graph theory, network theory, extremal and probabilistic methods,
analytic methods, finite model theory, combinatorial games, combinatorial optimization,
bioinformatics applications.
Seminar
Our seminar is held Fridays 1-2pm, Lippitt 204.
Seminar archive.
Speaker | Lilith Wagstrom, URI |
Title | The tree-depth and criticality of unicyclic graphs |
Time | Friday March 28, 2025, 1pm, Lippitt 204 |
Abstract | 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 if L(x) = L(y) then every path between x and y 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. However, despite the difficulty we will go over a potential classification of critical unicyclic graphs. In addition to these results, we present patterns present in the optimal feasible tree-depth labelings of cycles and general graphs. |
News
Faculty and their research
Michael Barrus, graph theory
Nancy Eaton, graph theory
Barbara Kaskosz, analysis
and its applications to discrete mathematics
William Kinnersley,
graph theory and combinatorial games
Pengyu (Peter) Liu,
graph theory and topological combinatorics
Lubos Thoma, extremal and probabilistic combinatorics
Doctoral students
Lilith Wagstrom
John Jones
Graduate courses
MTH547 Combinatorics,
MTH548 Graph Theory,
MTH515/516 Algebra,
MTH550 Probability and Stochastic Processes,
MTH581 Optimization Methods,
MTH656 Probability on Discrete Structures,
CSC541 Advanced Topics in Algorithms,
CSC542 Mathematical Analysis of Algorithms,
CSC544 Theory of Computation,
Special topics courses in Extremal Graph Theory, Ramsey Theory, Algebraic Combinatorics.
Discrete mathematics nearby
MIT Combinatorics seminar | Brown Combinatorics seminar / applied seminars | |
MIT Probability seminar | Yale Combinatorics and probability seminar | |
ICERM | CMSA |