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 almost invariably fall into 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. N. Kahl and K. Luttrell. On Maximum Graphs in Tutte Polynomial Posets. Discrete Applied Mathematics 339 (2023), 78-88.
  2. 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.
  3. N. Kahl. Extremal Graphs for the Tutte Polynomial. Journal of Combinatorial Theory Series B 152 (2022), 121-152.
  4. N. Kahl. Graph Vulnerability Parameters, Compression, and Threshold Graphs. Discrete Applied Mathematics 292 (2021), 108-116.
  5. N. Kahl. Graph Vulnerability Parameters, Compression, and Quasi-Threshold Graphs. Discrete Applied Mathematics 259 (2019), 119-126.
  6. N. Kahl, On constructing spanning tree edge densities, Discrete Applied Mathematics 213 (2016), 224-232.
  7. J. Cutler and N. Kahl, A note on the values of independence polynomials at -1, Discrete Mathematics 339 (2016), 2723-2726.
  8. N. Kahl, H. Quense* and T. Wager*, On a conjecture of Levit and Mandrescu, Congressus Numerantium 227 (2016), 177-185.
  9. 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.
  10. D. Bauer, N. Kahl, E. Schmeichel, D. Woodall, and M. Yatauro, Toughness and Binding Number, Discrete Applied Mathematics 165 (2014), 60-68.
  11. D. Bauer, N. Kahl, E. Schmeichel, D.R. Woodall, M. Yatauro. Improving Theorems in a Best Monotone Sense, Congressus Numerantium 216 (2013), 87-95.
  12. 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.
  13. 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.
  14. D. Bauer, N. Kahl, E. Schmeichel, and M. Yatauro, Best Monotone Degree Conditions for Binding Number,  Discrete Mathematics 311 (2011), 2037-2043.
  15. D. Gross, N. Kahl, and J.T. Saccoman, Graphs with the Maximum or Minimum Number of 1-Factors, Discrete Mathematics 310 (2010), 687-691.
  16. 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.
  17. D. Bauer, S.L. Hakimi, N. Kahl, and E. Schmeichel, Best Monotone Degree Bounds for Various Graph Parameters, Congressus Numerantium 192 (2008), 75-83.
  18. D. Bauer, N. Kahl, L. McGuire, and E. Schmeichel, Long Cycles in Two-Connected Triangle-Free Graphs, Ars Combinatoria 86 (2008), 295-304.
  19. A. Busch, M. Ferrara, and N. Kahl, Generalizing D-Graphs, Discrete Applied Mathematics 155 (2007), 2487-2495.
  20. 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.
  21. 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.