Graph Theory Day 42

November 10, 2001
DIMACS Center, Rutgers University, Piscataway, New Jersey

Organizers:

Michael Gargano, Pace University, mgargano@pace.edu

John W. Kennedy, Queens College, CUNY, jkennedy@nyas.org

Louis V. Quintas, Pace University, lquintas@pace.edu

Fred Roberts, Rutgers University, froberts@dimacs.rutgers.edu

Mel Janowitz, Rutgers University, melj@dimacs.rutgers.edu

Abstracts:

1.

POSING, VERIFYING AND DISPROVING CONJECTURES: EXPERIENCES IN USING
A PROGRAMMING PACKAGE FOR GRAPH THEORY
Dragos Cvetkovic, University of Belgrade

An interactive programming package, called GRAPH, an expert system for
graph theory, was developed at the University of Belgrade, Faculty of
Electrical Engineering, during the period 1980-1984. GRAPH was designed
to support research in graph theory, among other things by helping to
pose, verify and disprove conjectures. We report on the twenty years long
experience in using GRAPH. The results obtained by some help of GRAPH
have been published in about 70 papers written by about 20 authors. Most
of the results belong to the theory of graph spectra.



2.

Toward Fully Automated Fragments of Graph Theory.
Siemion Fajtlowicz, University of Houston.


Some versions  of Graffiti, starting with the Dalmatian one, developed
jointly with Ermelinda DeLaVina, are  fully automated apart from the
invention of invariants and counterexamples. Every conjecture of this
version is made with purpose and in some runs, for example in those in
which the goal is discovery of new easily-computable bounds for NP-hard
invariants, every one of them has a motivation.

The collection of these bounds can be viewed as a  hypothetical theory
in which the main  issue is significance, as opposed to the truth of
the formulas. Examples of such theories of the independence number,
include some runs of  Minuteman - the fullerene  version of Graffiti and
among its by-products are  hypotheses concerning stability of
these new carbon forms. I will also discuss modification of these
hypotheses suggested by nanotubes and other materials. Another by-product
of a conjecture about the independence number of stable fullerenes is   a
new representation  of buckminsterfullerene - the icosahedral C60. The
most automated example, to be discussed, are conjectures of Red Burton -
the educational version of the program designed to teach graph theory,
Texas-style, eventually without any  help of  instructors.

The  discovery of new bounds makes it all but  necessary sometimes to
address the issue  of concept formation and this problem  naturally
leads to questions (and one solution)  related to 17th and 18t century
interpolation problems.


3.

COMPUTERS IN GRAPH THEORY

Pierre Hansen, GERAD and Ecole des HEC,Montreal

Computer aids to Graph Theory, i.e. finding proofs, conjectures and 
refutations are reviewed. After discussing the four-color theorem and other 
computer aided proofs, ways to get conjectures and refutations are examined:
(i) graph enumeration; (ii) interactive computing, (iii) formula 
manipulation, (iv) a priori generation and filtering, (v) heuristic 
optimization. Open questions and areas for development are emphasized.

Previous: Participation

Next: Registration

Workshop Index

DIMACS Homepage