Speaker:
Jay Bagga
Title:
Old and New Generalizations of Line Graphs
Abstract:
Line graphs have been studied for over seventy years. In 1932, H. Whitney
showed that for connected graphs, edge-isomorphism implies isomorphism
except for K3 and K1, 3.
The line graph transformation is one of the most widely studied of all
graph transformations. In its long history, the concept has been
rediscovered several times, with different names such as derived graph,
interchange graph, and edge-to-vertex dual. Line graphs can also been
considered as intersection graphs.
In this presentation we first give a short historical account of work on
line graphs. Several variations and generalizations have been proposed
and studied, such as total graphs, path graphs, k-line graphs, and (X,
Y)-intersection graphs. We describe these and some more recent
generalizations including super line graphs and triangle graphs.
|
Speaker:
Nathaniel Dean
Title: Unsolved and Incomprehensible Graph Drawing Problems
Abstract:
Graphs are often used to visualize patterns or structures in
complex systems. One way to reduce the complexity of a drawing
is to minimize the number of edge crossings over all planar
drawings of the graph. We describe a quadratic programming
formulation for the rectilinear version of this problem. Further,
we define precisely what it means for a graph to have a good
drawing and why for certain graphs it does not exist.
|
Speaker:
Herbert Fleischner
Title: Uuniquely Hamiltonian Graphs
Abstract:
In the 1970s, J.Sheehan asked whether there are 4-regular simple graphs
having precisely one hamiltonian cycle (= uniquely hamiltonian graphs).
In the early 1990s, 4-regular loopless uniquely hamiltonian multigraphs
were constructed whose underlying uniquely hamiltonian (simple) graphs
have 3- and 4-valent vertices only. C.Thomassen showed that regular
graphs of sufficiently high degree cannot be uniquely hamiltonian; and
J.A.Bondy, in his article for the Handbook of Combinatorics, asked
whether uniquely hamiltonian graphs must have a vertex of degree 2 or 3.
Starting from the examples quoted above, one can construct eulerian
uniquely hamiltonian graphs of minimum degree 4.
|
Speaker:
Frank Harary
Title:
On the Many Applications of Graph Theory: To Anthropology, Biology,
Chemistry, Physics, Psychology, Computer Sciences, etc
Abstract:
|
Speaker:
Ewa Kubicka
Title: The Chromatic Sum of a Graph; History and Recent Developments
Abstract:
The chromatic sum of a graph is the smallest sum of colors among all
proper colorings with natural numbers.
The strength of a graph is the minimum number of colors necessary to
obtain its chromatic sum.
A natural generalization of chromatic sum is optimum cost chromatic
partition (OCCP) problem, where the costs of colors can be arbitrary
positive numbers.
We present existing results about chromatic sum, strength of a graph, and
OCCP problem together with some recent developments. We focus on
polynomial algorithms for some families of graphs and NP-completeness
issues.
|
Speaker:
Melvyn Nathanson
Title: Representation functions of additive bases for the integers
Abstract:
The representation function of a set A of integers counts
the number of ways to write an integer as the sum of two elements
of A. Erdos and Turan conjectured that if A is an asymptotic basis of
order 2 for the nonnegative integers, then its representation function
must be unbounded. This is not true for representation functions of
asymptotic bases for the set of all integers. In this case, every
function is a representation function. We consider the problem of
constructing dense sets of integers with a prescribed representation
function.
|
Speaker:
Van Vu
Title: New Results and Questions on Random Graphs
Abstract:
This is a survey talks about recent developments in the theory
of random graphs, with focus on random graphs with fixed degree
sequences.
|
|