Nathan Kahl


My area of research is graph theory. Most recently I've been exploring the consequences of a graph transformation called "compression." I've been able to show compression has a uniform effect on a number of graph parameters, and have used these effects to find extremal graphs for the parameters. Interestingly, these extremal graphs all invariably fall in a well-known class of graphs called threshold graphs.

Much of my early work focused on degree sequences of graphs. In particular, I'd been exploring what conditions on a graphical degree sequence guarantee that a graph with that degree sequence has certain graphical properties. A good review of this work and other similar types of results can be found in the survey found below.

Publications

  1. J. Cutler, N. Kahl, and P. Zielonka. A note on the alternating number of independent sets in a graph. Discrete Mathematics 349 (2026), P115147.
  2. N. Kahl and K. Luttrell. On Maximum Graphs in Tutte Polynomial Posets. Discrete Applied Mathematics 339 (2023), 78-88.
  3. D. Gross, N. Kahl, K. Luttrell, and J.T. Saccoman. Dr. Charles L. Suffel: Scholar, Teacher, Mentor, Friend. Networks 80 (2022), no. 4, 431-439.
  4. N. Kahl. Extremal Graphs for the Tutte Polynomial. Journal of Combinatorial Theory Series B 152 (2022), 121-152.
  5. N. Kahl. Graph Vulnerability Parameters, Compression, and Threshold Graphs. Discrete Applied Mathematics 292 (2021), 108-116.
  6. N. Kahl. Graph Vulnerability Parameters, Compression, and Quasi-Threshold Graphs. Discrete Applied Mathematics 259 (2019), 119-126.
  7. N. Kahl, On constructing spanning tree edge densities, Discrete Applied Mathematics 213 (2016), 224-232.
  8. J. Cutler and N. Kahl, A note on the values of independence polynomials at -1, Discrete Mathematics 339 (2016), 2723-2726.
  9. N. Kahl, H. Quense* and T. Wager*, On a conjecture of Levit and Mandrescu, Congressus Numerantium 227 (2016), 177-185.
  10. D. Bauer, H.J. Broersma, J. van den Heuvel, N. Kahl, A. Nevo, E. Schmeichel, D.R. Woodall, M. Yatauro. Best Monotone Degree Conditions for Graph Properties: A Survey, Graphs and Combinatorics, 31 (2015), 1-22.
  11. D. Bauer, N. Kahl, E. Schmeichel, D. Woodall, and M. Yatauro, Toughness and Binding Number, Discrete Applied Mathematics 165 (2014), 60-68.
  12. D. Bauer, N. Kahl, E. Schmeichel, D.R. Woodall, M. Yatauro. Improving Theorems in a Best Monotone Sense, Congressus Numerantium 216 (2013), 87-95.
  13. D. Bauer, H. Broersma, N. Kahl, E. Schmeichel, and J. van den Heuvel, Toughness and Vertex Degrees, Journal of Graph Theory 72 (2013), 209-219.
  14. D. Bauer, H. Broersma, N. Kahl, E. Schmeichel, and J. van den Heuvel, Degree Sequences and the Existence of k-Factors, Graphs and Combinatorics 28 (2012), 149-166.
  15. D. Bauer, N. Kahl, E. Schmeichel, and M. Yatauro, Best Monotone Degree Conditions for Binding Number,  Discrete Mathematics 311 (2011), 2037-2043.
  16. D. Gross, N. Kahl, and J.T. Saccoman, Graphs with the Maximum or Minimum Number of 1-Factors, Discrete Mathematics 310 (2010), 687-691.
  17. D. Bauer, S.L. Hakimi, N. Kahl, and E. Schmeichel, Sufficient Degree Conditions for k-Edge-Connectedness of a Graph, Networks 54 (2009), 95-98.
  18. D. Bauer, S.L. Hakimi, N. Kahl, and E. Schmeichel, Best Monotone Degree Bounds for Various Graph Parameters, Congressus Numerantium 192 (2008), 75-83.
  19. D. Bauer, N. Kahl, L. McGuire, and E. Schmeichel, Long Cycles in Two-Connected Triangle-Free Graphs, Ars Combinatoria 86 (2008), 295-304.
  20. A. Busch, M. Ferrara, and N. Kahl, Generalizing D-Graphs, Discrete Applied Mathematics 155 (2007), 2487-2495.
  21. D. Bauer, H. Broersma, N. Kahl, A. Morgana, E. Schmeichel, and T. Surowiec, Tutte Sets in Graphs II: The Complexity of Finding Maximum Tutte Sets, Discrete Applied Mathematics 155 (2007), 1336-1343.
  22. N. Kahl, Reliability, T-Optimal Graphs, and the Multigraph Conjecture, Congressus Numerantium 163 (2003), 161-175.

An asterisk (*) indicates the work was done with an undergraduate co-author.