Cataloguing General Graphs by Point and Line Spectra
by S. A. Fulling, I. Borosh, and A. da Conturbia
This World Wide Web page elaborates on the paper of the same title,
Computer Physics Communications 115 (1998), 93-112,
Thematic Issue on "Computer Algebra in Physics Research".
Certain perturbative expansions in physics are sums over all
multigraphs with loops -- i.e., graph-like structures in which
each point can be connected to any other point, including itself,
by an arbitrary number of lines.
We treat the problem of exhibiting, or at least counting, all such
objects for all reasonably small numbers of points and lines,
as well as the associated problem of determining the number of
labeled graphs corresponding to a given unlabeled one.
Symbolic computation (specifically, Mathematica) has proven
very useful here.
It is helpful to classify the graphs further according to the
distribution of the lines among the pairs of points (line
spectrum) and simultaneously the distribution of the ends of the
lines among the points (point spectrum).
The basic tool is a generating function in which each coefficient
is the number of general graphs with a given line spectrum and
Here are archived:
- The preprint (minus the tables given separately below) as a
.dvi file in landscape mode
(for ease of on-screen viewing)
and as a
PostScript file in portrait mode.
- Figure 3, in .dvi and
Figure 3 presents a table of the total numbers of graphs
of type (p,q), classified according to connectedness and
simplicity to the extent that such statistics are known.
Statistics for connected graphs appear at the top of each box,
those for disconnected graphs at the bottom.
Statistics for simple graphs appear at the left, those for others
at the right.
Totals of adjacent statistics appear between them in larger type.
Thus, for (p,q)=(4,4), the table means that
there are 2 connected simple graphs, 7 connected nonsimple graphs
(having either loops or multiple links),
and 44 disconnected graphs (none of them simple);
therefore, there are 2 simple graphs, 51 nonsimple graphs, 9
connected graphs, 44 disconnected graphs;
a total of 53 graphs in all.
- The catalog of general graphs, in .dvi and
- The Mathematica programs for
enumerating unlabeled and labeled graphs.
Go to home pages:
Mathematics Department ._._.
Texas A&M University
Last updated Wed 10 Feb 99