Dalhousie University Graphs
and Games Group
Faculty
Members
Interests
Graph Theory, Combinatorics (Hypergraph Theory, Matroids, Simplicial
Complexes,
Partial Orders) and Combinatorial Games and associated Algorithms and
Applications.
Techniques applied are from a variety of mathematical fields, including
linear and commutative algebra, matrix theory, algebraic topology,
analysis
and probability. Curent active areas of research include: include
analysis
of large scale information networks (e.g. web graph); chromatic and
independence
polynomials; combinatorial games; combinatorial optimization; frequency
planning in cellular networks; independence parameters and coverings of
products of graphs; list colourings; network reliability; partial
orders;
vertex-to-vertex (Searching and Cops & Robber) pursuit
games;
well
covered graphs; and applications of graph theory to music.
On-Going Projects
List Colourings
Leader: J. C. M. Janssen
Recent
and Current Students
Recent papers
- J. C. M. Janssen, A
Partial Solution of a Partial List Colouring
Problem, Congressus
Numerantium 152 (2001), pp.
75--79.
- J. C. M. Janssen, K.
Kilakos, Adaptive Multicolouring, Combinatorica
20(2000) pp.87-102.
Channel Assignment
Leader: J. C. M. Janssen
Recent
and Current Students
- Mark MacIsaac, M.Sc. 2002,
Supervisor: J. C. M. Janssen
- Kyle Schmeisser, M.Sc.,
2000, Supervisor: J. C. M. Janssen
- Megan Dewar, M.Sc., 2000,
Supervisor: J. C. M. Janssen
- Tania Wentzell , M.Sc.,
1999, Supervisor: J. C. M. Janssen
Recent papers
- S. L. Fitzpatrick, J. C.
M. Janssen, , R. J. Nowakowski, Channel
assignment
algorithms for cellular networks with constraints, Submitted.
- J. C. M. Janssen, L.
Narayanan, Approximation Algorithms for the
Channel
Assignment Problem, Theoretical
Computer Science A 262/1-2
(2001),
pp.~649--667.
- J. C. M. Janssen, D.
Krizanc, L. Narayanan and S. Shende, Distributed
Online
Frequency Assignment in Cellular Networks, J.
Algorithms
36(2000),
pp.119-151.
- J. C. M. Janssen, K.
Kilakos, An optimal solution to the Philadelphia
channel
assignment problem, IEEE
Trans. Veh. Techn. 48 (1999) pp.
1012-1014.
- J. C. M. Janssen, K.
Kilakos and O. Marcotte, Fixed Preference
Frequency
Allocation for Cellular Telephone Systems, IEEE
Trans. Veh. Techn.
48 (1999) pp.533- 541.
Cops-and-Robber and Searching
(Structures in Graphs)
Leader: R. J. Nowakowski
Recent
and Current Students
- Alan Hill,
Ph.D, Supervisor: R. J. Nowakowski
- Sable McKeil, MSc
Supervisor: R. J. Nowakowski
- Margaret-Ellen Messinger,
Ph.D, Supervisor: R. J.
Nowakowski
- Nancy Clarke,
Ph.D. 2002, Supervisor: R. J.
Nowakowski
- Nancy Clarke, M.Sc., 1999,
Supervisor: R. J. Nowakowski
- Stephen Finbow, M.Sc.,
1999, Supervisor: R. J. Nowakowski
- Shannon Fitzpatrick,
Ph.D.,1997, Supervisor: R. J. Nowakowski
Recent papers
- S. L. Fitzpatrick, R. J.
Nowakowski, D. A. Holton, I. Caines, Covering
hypercubes with isometric paths, Discrete
Math. 240(2001),
253-260
- N. E. Clarke, R. J.
Nowakowski, Cops, Robber and Traps, Utilitas
Math.
60(2001), 91-98
- S. L. Fitzpatrick R. J.
Nowakowski, Cop number of graphs with strong
isometric
dimension two, Ars Combin.5
9 (2001), 65-73.
- S. L. Fitzpatrick R. J.
Nowakowski, The strong isometric dimension of
finite
reflexive graphs, Discussiones
Math. Graph Theory 20(2000)
pp.23--38.
- N. E. Clarke, R. J.
Nowakowski, Cops, Robber and Photoradar, Ars
Combinatoria
LVI(2000),pp. 97-103.
Combinatorial Games
Of special interest are the breaking-and-taking games, such as
subtraction,
octal, hexadecimal and variants; misere games; and all-small games.
Leader: R. J. Nowakowski
Recent
and Current Students
- Meghan Allen, PhD.,
Supervisor: R. J. Nowakowski
- Paul Ottaway, PhD.,
Supervisor: R. J. Nowakowski
- Angela Siegel: Ph.D,
Supervisor: R. J. Nowakowski
- Neil McKay, M.Sc.,
Supervisor: R. J. Nowakowski
- Meghan Allen, M.Sc. 2006,
Supervisor: R. J. Nowakowski
- Fraser Stewart, MSc. 2006,
Supervisor: R. J. Nowakowski
- Angela Siegel: M.Sc. 2005,
Supervisor: R. J. Nowakowski
- Paul Ottaway, M.Sc. 2003,
Supervisor: R. J. Nowakowski
- Sarah McCurdy, M.Sc.,
2003,
Supervisor: R. J. Nowakowski
- Todd Grimm, M.Sc., 1998,
Supervisor: R. J. Nowakowski
Recent papers
- D. Horrocks, R. J.
Nowakowski, Regularities in Octal games with a pass,
submited.
- J. P. Grossman, R. J.
Nowakowski (2001) One-dimensional Phutball, to
appear
in More Games of No Chance,
R.J. Nowakowski Ed., Mathematical
Sciences
Research Institute Publications.
- S. Howse, R. J.
Nowakowski, Hexadecimal Games, J.
Theoretical
Comp. Sci.313(2004)
463-472.
- R. J. Nowakowski, ed,
(2003) More Games of No Chance,
Mathematical
Sciences Research Institute Publications 42,
Cambridge
University
Press.
- M. H. Albert, R. J.
Nowakowski, End-Nim, Electronic
Journal of
Combinatorics
8(2) R1 (2001).
- I. Caines, C. Gates, R. K.
Guy, R. J. Nowakowski (1999) Periods in
Taking
and Splitting Games, Amer.
Math. Monthly 106,
359-361.
- R. J. Nowakowski, ed,
(1996) Games of No Chance,
Mathematical
Sciences
Research Institute Publications 29,
Cambridge University Press.
Books
- Lessons In Play, AK
Peters, 2007.
Ramsey Theory
Leader: J. I. Brown
Recent
and Current Students
- Richard Hoshino, Ph.D.,
Supervisor: J. I. Brown
- Richard Hoshino, M.Sc.,
2002, Supervisor: J. I. Brown
Graph Polynomials
Leader: J. I. Brown
Recent
and Current Students
- Carl A. Hickman, Ph.D.
2001, Supervisor: J. I. Brown
Recent papers
- J. I. Brown, Carl A.
Hickman and R. J. Nowakowski, Independence
Fractals
of Graphs, J. Comb. Th. B.,
accepted for publication (2002).
- J. I. Brown and Carl A.
Hickman, The Existence of Infinitely Many
Chromatic
Roots With Negative Real Part, Ars
Combinatoria 63(2002),
211-221.
- J. I. Brown and Carl A.
Hickman, On Chromatic Roots of Large
Subdivisions
of Graphs, Discrete Mathematics
242(2002), 17-30.
- J. I. Brown, R. J.
Nowakowski, Bounding the roots of independence
polynomial, Ars
Combinatorica 58(2001) pp.
113-120.
- J. I. Brown, Carl A.
Hickman, Alan D. Sokal and David G. Wagner,
Chromatic
Roots of Generalized Theta Graphs, J.
Comb. Th. B 83(2001),
272-297.
- J. I. Brown, K. Dilcher
and R. J. Nowakowski,(2000) Roots of
Independence
Polynomials of Well Covered Graphs, Journal
of Algebraic Combinatorics
11(2000) pp. 197-210.
Large Scale Networks
Leader: J. C. M. Janssen
External funding (MITACS)
available for graduate students working
on
this project.
Recent
and Current students
- Changping Wang, Ph.D.,
Supervisor J. C. M. Janssen
- Hongyu Liu, Ph.D.,
Supervisor J. C. M. Janssen, E. Milios
- Adam Nickerson , M.CS.,
Supervisor J. C. M. Janssen, E. Milios
- Jinghu Liu, M.CS.,
Supervisor J. C. M. Janssen, E. Milios
- Biao Chen , M.CS., 2002,
Supervisor J. C. M. Janssen, E. Milios
- Yuan An , M.CS. 2001,
Supervisor J. C. M. Janssen, E. Milios
Well-covered graphs and
well-covered weightings
Leader: R. J. Nowakowski
Recent
papers
- J. I. Brown, R. J.
Nowakowski, Well covered weightings of Graphs,
accepted SIAM Journal
of Discrete Math
- J. I. Brown, R. J.
Nowakowski, The structure of well covered graphs
that
contain no 4-cycle, to appear, Discrete
Mathematics.
- A. Finbow, B. Hartnell, R.
J. Nowakowski, M. D. Plummer (2002), On
well-covered
triangulations: 1, Discrete
Appl. Math.
132
(2003), 97--108.
- S. Gascoigne, B. Hartnell,
R. J. Nowakowski & C. A. Whitehead
(1995),
Techniques for constructing well-covered graphs with no 4-cycles, Journal
of Combinatorial Mathematics and Combinatorial Computing
17,
65-87.
- A. Finbow, B. Hartnell, R.
J. Nowakowski (1993), A Characterization of
Wellcovered Graphs of Girth 5 or Greater, J.
Combinatorial Theory,
Ser B, 57,
44-68.
Seminars
and Courses:
2005-2006
Courses:
MATH4116/5116/CSCI4116:
Cryptography---Fall
MATH4330/5330/CSCI4115:Graph
Theory---Fall
MATH4900/5900:
Combinatorial and Classical Game Theory---Fall.
Graph
Graph Theory Seminar Series:
Organizer ---M. E. Messinger
Game Theory Seminar Series:
Organizer --- Richard Nowakowski
East Coast Combinatorics Group.
There is an active community in the Atlantic region.
List of members
and
schedule of events.
Last update: November, 2006.