Students who I have advised or am advising:
- Sam Donelley, Undergraduate honors thesis, 1997. `Powers of Hamiltonian paths and Powers of Hamiltonian Cycles in Threshold Graphs'. Now am member of the Database Research Group, University of Pennsylvania.
- Adan Yusko, Undergraduate honors thesis 2010, `Representing Split Graphs as probe Interval graphs', Master degree at Western Michigan, now in industry
- Darren Narayan , PhD May 2000. `The Reversing Number of a Digraph'. Now at Rochester Institute of Technology
- Trisha Moller, PhD August 2004. `t-split interval orders'. Initially at DeSales University. Now working part time at Moravian College and part time with family.
- Brian Heinold, PhD May 2006. `Sum List Coloring and Choosability'. Now at Mt. St. Mary's University Maryland.
- Jen Scancella Gorman, PhD August 2007, `Nested Traveling Salesperson Problems', Now at College of Southern Nevada.
- Ellen Panofsky, PhD May 2008. `Graph Labeling Problems with Distance Conditions', Now atTemple University.
-Jonelle Hook, PhD May 2010. `The Clasisfication of Critical graphs and Star-Critical Ramsey Numbers', Now at Mt. St. Mary's University Maryland.
- Breeanne Baker, PhD, May 2013, `The k-Fixed-Endpoint Path Partition Problem', Now at The Citidel.
- Kathleen Ryan, PhD, August 2013, `Degree Sequences of Edge Colored graphs in Specified Families and Related Problems', Now at DeSales University
- Matt Prudente, PhD, May 2015, `Two-Player graph Pebbling', Now at St. Vincent College
- Aydin Gerek, Starting Spring 2011
- Caitlin Owens, starting 2015
- Pam Kirkpatrick, starting 2015
- Stash Flowkowski, starting 2016
Postdoctoral visitors to Lehigh that I have worked with:
Busch 2005-2006, now at University of Dayton.
- Colton Magnant, 2008-2010, now at Georgia Southern University
Here are several unpublished papers:
- My (old, from 1990) PhD dissertation,
Odd forests, reversing numbers, and discrete representations of
- Examples of Combinatorial Duality :
an expository paper giving examples of the theorem of the
alternative for linear
inequalities is used to prove Hoffman's circulation theorem and then from this Fishburn's Interval order representation
theorem and Landau's theorem for score sequences of tournaments.
- Chain Packings and Odd Subtree Packings : an old unpublished paper building on work from my PhD thesis. It seems that part of what I did had been done before and the other part done several years later by others.
Here are slides from some talks:
Whats your Order?, Wellesley
College Martha Davenport heard lecture, October 6, 2015
Degrees and trees , Hour talk at 47th SE Conference on Combinatorics, Graphs Theorey and Computing at Flordia Atlantic University, March 8, 2016
Choose Multichoose , Hour talk at 47th SE Conference on Combinatorics, Graphs Theorey and Computing at Flordia Atlantic University, March 11, 2016
Multiset Poker, MAA EPADEL, November 12, 2016
Older talks, Probably pre 2010 but after around 2002 (prior to that I used overhead slides)
- Perfect maps and factors : My first computer based talk.
- When does x < a, x > 0 have a solution? : A talk for undergraduates based on my expository paper `Examples of combinatorial duality'.
- Score sequences for tournaments Another talk for undergraduates
- An edge Count Criterion for Degree Sequences On degree sequences for edge colored graphs
- Intervals and orders: what comes after interval orders A talk for a special session in memory of Ken Bogart
- Distinguishing number of cartersian products of complete graphs
- Structure of bipartite probe interval graphs
- Star avoiding Ramsey numbers
- Score sequences for tournaments Another talk for undergraduates
This is an out of date description. The papers also are linked in
the list above.
A research statement from my tenure file in 1998
Here are some of my current research interests and favorite problems. Well - not really; my favorite problems are the hard well known ones. I will mention problems that are less well known and closely related to my current research
Feedback Arc Digraphs: who gets upset in tournament rankings
A feedback arc set in a digraph is a set of arcs whose removal makes the digraph acyclic. A minimum size feedback arc set in a tournament is also the set of arc inconsistent with a `ranking' which minimizes inconsistencies. Every acyclic digraph is a feedback arc set of some tournament. That is, given an acyclic digraph, which we think of as the inconsistencies from a ranking, what is the smallest size of a tournament in which the ranking procedure described above gives exactly those inconsistencies. (We do allow a ranking procedure to produce several equal rankings and we search for the inconsistencies under one of these.) In particular we can look at `the' acyclic tournament as the set of inconsistencies. This provides bounds for other acyclic digraphs. So we ask: what is the smallest size of a tournament which produces a set of n people each pair of which is ranked wrong. I have a specific conjecture about this, along with partial results and related questions in Tournaments as Feedback Arc Sets (Electronic Journal Of Combinatorics Vol 2 (1995) article R20). The partial results are obtained by viewing the problem as an integer linear programming problem. More recent results have been obtained with recent Lehigh PhD Darren Narayan. See his research page for more information.
Powers of Hamiltonian Paths
Label the vertices of a graph so as to maximize the minimum distance between non-adjacent vertices. This is in a sense dual' to the bandwidth problem, which seeks to minimize the maximum distance between adjacent vertices. This problem is also a variant on Hamitonian paths, looking for powers of Hamiltonian paths instead. Some of my papers on this are: Hamiltonian Powers in Threshold and Arborescent Comparability Graphs (with Sam Donnelly, Discrete Mathematics 202 (1999) 33-44) and Powers of Hamiltonian Paths in Interval Graphs (Journal of Graph Theory 28 (1998) 31-38).
Perfect Maps: how determine your location in n dimensions
List the string 00011101 cyclically. Each triple occurs exactly once. This is known as a perfect map or de Bruijn cycle. Many questions can be asked about higher dimensional versions of this and version with an alphabet of size k (instead of 2). In particular are the `obvious' necessary conditions sufficient? Kenny Patterson in London has answered this completely in 2-dimensions for k a prime power. Many other interesting questions arise about related structures called perfect factors and perfect multi-factors which arise in the study of these objects. For more information and references to other work see these papers my recent paper (which is partially survey and partially new unifying results and notation Constructing Higher Dimensional Perfect Factors (to appear in Aequationes Mathematicae)
Some recent work on the Prague dimension (product dimension) of graphs with a suprising connection to orthogonal latin squares can be found in Representations of graphs modulo n (with Anthony Evans and Darren Narayan, Discrete Mathematics 223 (2000) 109-123)
Garth Isaak home page