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.
- 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 Gannon University.
- Ellen Panofsky, PhD May 2008. `Graph Labeling Problems with Distance Conditions', Now at Cabrini College.
- James Carroll, PhD student, starting fall 2006, expected completion
spring 2008.
- Jonelle Hook, PhD student, starting fall 2007, expected completion spring 2009.
Postdoctoral visitors to Lehigh that I have worked with:
- Art Busch 2005-2006, now at University of Dayton.
- Colton Magnant, starting Fall 2008.
I have also served on the PhD thesis committees of over a dozen students
from various departments: computer science, electrical engineering, industrial
engineering and mathematics.
Here is a list of my published research papers. I have links to most of
the papers (many are prepublication versions nearly in final
form). For the others if
you want a copy please send me an email for a hard copy.
1.G. Isaak and B. Tesman, The Weighted Reversing Number of a Digraph,
Congressus Numerantium, 83 (1991) 115-124
2. H. Abeledo and G. Isaak, A Characterization of
Graphs that Ensure
the Existence of Stable Matchings, Math. Social Sciences, 22 (1991)
93-96
3. G. Isaak, S. Kim, T.A. McKee, F.R. McMorris and F.S. Roberts, 2-Competition Graphs, SIAM J. Discrete Math., 5 (1992) 524-538.
4. G. Isaak, Bounded Discrete Representations of Interval Orders,
Discrete Appl. Math., 44 (1993) 157-183.
5. G. Hurlbert and G. Isaak, On the de Bruijn
Torus Problem , J.
Combinatorial Theory A, 64 (1993) 50-62.
6. G. Hurlbert and G. Isaak, A Meshing Technique
for deBruijn Tori , Contemporary Math. 178 (1994) 153-160.
7. G. Isaak, Scheduling Rooted Forests
with
Communication Delays,
Order, 11 (1994) 309-316.
8. J.P. Barthelemy, O. Hudry, G. Isaak, F.S. Roberts and B.
Tesman, The
Reversing Number of a Digraph , Discrete Appl. Math., 60 (1995)
39-76.
9. K.P. Bogart, P.C. Fishburn, G. Isaak and L. Langley, Proper and Unit
Tolerance Graphs , Discrete Appl. Math., 60 (1995) 99-117.
10. G. Hurlbert and G. Isaak, New
Constructions for de Bruijn Tori,
Designs, Codes and Cryptography, 6 (1995) 47-56.
11. G. Isaak,
Tournaments as Feedback Arc Sets , Electronic Journal of
Combinatorics, 2 (1995) #R20, 19pp.
12. J. Driscoll, D. Healy and G. Isaak,
Scheduling Dyadic
Intervals ,
Discrete Appl. Math., 63 (1995) 101-116.
13. G. Hurlbert and G. Isaak, Equivalence Class
Universal Cycles for
Permutations , Discrete Math., 149 (1996) 123-129.
14. G. Hurlbert and G. Isaak, On Higher
Dimensional Perfect Factors ,
Ars Combinatoria, 45 (1997) 129-139.
15. K.P. Bogart and G. Isaak, Proper and Unit
Bitolerance Orders ,
Discrete Math., 181 (1998) 37-51.
16. G. Isaak, Powers of Hamilton Paths in Interval
Graphs , J. Graph
Theory 27 (1998) 31-38.
17. S. Donelley and G. Isaak, Hamiltonian Powers in
Threshold and
Arborescent Comparability Graphs, Discrete Math., 202 (1999) 33-44.
18. A.B. Evans, G. Isaak and D. Narayan,
Representations of Graphs
Modulo n, Discrete Math., 223 (2000) 109-123.
19. K.P. Bogart, G. Isaak, J. Liason and A. Trenk,
Comparability
Invariance Results for Tolerance Orders, Order, 18 (2001) 281-294.
20. G. Isaak, Constructions for Higher
Dimensional Perfect Factors ,
Aequationes Math., 64 (2002) 70-88.
21. G. Isaak,
Sum List Coloring 2 by n Arrays, Electron. J.
Combinatorics 9 (2002) Note 8, 7 pp.
22. G. Isaak, K. Nyman and A. Trenk, A Heirarchy
of Classes of Bounded
Bitolerance Orders, Ars Combinatoria, 69 (2003) 33-53.
23. D. Narayan and G.Isaak, A Complete
Classifcation of Tournaments
having a Disjoint Union of Directed Paths as a Minimum Feedback Arc
Set , J. Graph Theory, 45 (2004) 28 - 47.
24.G. Isaak Sum List Coloring Block Graphs,
Graphs and
Combinatorics 20 (2004) 499-506.
25. D. Narayan and G. Isaak, A Classification of
Tournaments having
an Acyclic Tournament as a Minimum Feedback Arc Set , Inf. Proc.
Let. 92 (2004) 107-111.
26. G. Isaak, Hamiltonicity of Digraphs for
Universal Cycles of
Permutations, European Journal of Combinatorics 27 (2006) 801-805.
27. A.H. Busch and G. Isaak, Recognizing Bipartite Unbounded Tolerance Graphs in Linear Time, Lecture Notes in Computer Science 4769 (2007) 12-20 .
28. M.J. Fisher and G. Isaak, Distinguishing Colorings of Cartesian Products of Complete Graphs, Discrete Mathematics 308 (2008) 2240-2246 .
29. G. Isaak, Interval Order representation via Shortest Paths, to appear in special volume in honor of Peter Fishburn.
Here are several unpublished papers:
- 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:
- 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'.
Scores sequences for tournaments
score sequences for tournaments
Degree sequences of edge colored graphs
This is an out of date description. The papers also are linked in
the list above.
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)