Titles are links to abstracts below. Where available, a link will provide a downloadable version of the paper.
If you have electronic access to Mathematical Reviews (MathSciNet) you can view the list of articles I have reviewed together with the reviews themselves. Or consult a compendium of the seventy-seven reviews I've written. (Current as of August 2009.)
A graph is self-complementary if it is isomorphic to its complement. A graph is vertex transitive if for each choice of vertices u and v there is an automorphism that carries the vertex u to v. The number of vertices in a self-complementary vertex-transitive graph must necessarily be congruent to 1 mod 4. However, Muzychuk has shown that if p^m is the largest power of a prime p dividing the order of a self-complementary vertex-transitive graph, then p^m must individually be congruent to 1 mod 4. This is accomplished by establishing the existence of a self-complementary vertex transitive subgraph of order p^m, a result reminiscent of the Sylow theorems. This article is a self-contained survey, culminating with a detailed proof of Muzychuk's result.
In 1976 Erdos asked about the existence of Steiner triple systems that lack collections of j blocks employing just j+2 points. This has led to the study of anti-Pasch, anti-mitre and 5-sparse Steiner triple systems. Simultaneously generating sets and bases for Steiner triple systems and t-designs have been determined. Combining these ideas, together with the observation that a regular graph is a 1-design, we arrive at a natural definition for the girth of a design. In turn, this provides a natural extension of the search for cages to the universe of all t-designs. We include the results of computational experiments that give an abundance of examples of these new definitions.
Given a t-(v, k, lambda) design, form all of the subsets of the set of blocks. Partition this collection of configurations according to isomorphism and consider the cardinalities of the resulting isomorphism classes. Generalizing previous results for regular graphs and Steiner triple systems, we give linear equations relating these cardinalities. For any fixed choice of t and k, the coefficients in these equations can be expressed as functions of v and lambda and they depend on the design itself only through the parameters t, v, k and lambda. This provides a characterization of the elements of a generating set for m-line configurations of an arbitrary design.
We show the average distance, mu,of a connected graph on n vertices, e edges and minimum degree r must satisfy
mu <= (n+1)/(r+1) - (2e)/( ( r+1) n (n-1) ).
This improves a conjecture of the computer program GRAFFITI. The bound is best possible in the sense that complete graphs yield equality.
A distance-regular graph of diameter d has 2d intersection numbers that determine many properties of the graph (e.g. its spectrum). We show that the first six coefficients of the matching polynomial of a distance-regular graph can also be determined from its intersection array, and that this is the maximum number of coefficients so determined. Also, the converse is true for distance-regular graphs of small diameter --- that is, the intersection array of a distance-regular graph of diameter 3 or less can be determined from the matching polynomial of the graph
For a regular graph, we establish linear equations involving the cardinalities of isomorphism classes of subgraphs. These equations are remarkable in that the coefficients depend on the graph only through its order and degree. By solving these linear equations, we can express all of the cardinalities in terms of the order, degree and the cardinalities of the isomorphism classes represented by subgraphs containing no vertices of degree one. These equations provide a powerful tool for analyzing the structure of a regular graph.
This paper investigates an infinite collection of graphs which possess matching polynomials that have the smallest possible coefficients.
This is written as a UMAP module, with an intended audience of first-year calculus students. The internal rate of return is a measure of an investment's performance that must be computed as the root of a very complicated equation. Exact methods are inappropriate, so this is a natural situation to apply iterative methods. Here we illustrate the application of two popular methods (bisection and Newton's) and a more novel method that is applicable to a more narrow range of investments that behave like bonds. Numerous examples with actual historical data are analyzed with these methods.
The matching polynomial of a graph has coefficients that give the number of matchings in the graph. For a regular graph, we show it is possible to recover the order, degree, girth and number of minimal cycles from the matching polynomial. If a graph is characterized by its matching polynomial, then it is called matching unique. Here we establish the matching uniqueness of many specific regular graphs; each of these graphs is either a cage, or a graph whose components are isomorphic to Moore graphs. Our main tool in establishing the matching uniqueness of these graphs is the ability to count certain subgraphs of a regular graph.
We are interested here in the cardinalities of the isomorphism classes of edge-induced subgraphs of a regular graph. Specifically, we will describe a method for determining linear equations relating these cardinalities. These equations are remarkable in that the coefficients depend on the specific regular graph only through its order and degree. By solving systems of these linear equations, we can express all of the cardinalities in terms of just the order and degree of the graph, together with the cardinalities of the isomorphism classes represented by subgraphs containing no vertices of degree one.
Exhaustive catalogs of regular graphs can be an indispensable tool for computerized investigations in graph-theoretical research. We describe an algorithm for the creation of catalogs of regular graphs. Using this algorithm, all of the regular graphs on thirteen or fewer vertices have been created. (A longer version of this paper is available as a technical report, Generating catalogs of regular graphs. It contains program listings and more implementation details.)
The Combinatorial Object Library (COL) is a documented listing of C++ objects designed to assist with computer investigations in graph theory. This is intended to be an evolving collection of integrated routines, so this is simply a snapshot of the state of the library after a concerted summer's worth of work. The documentation is the output of the literate programming tool FWEB after being processed by TeX.
This is an expanded version of the paper Catalogs of regular graphs that contains program listings and more details on the implementation.
This report contains documented code for procedures used to compute graph polynomials. The principal feature of this package is that the fundamental algorithm has been written in an abstract fashion, so that new graph polynomials (with different covers, or different weighting schemes) can be added with just a few new lines of code. The programs are written in Turbo Pascal using the literate programming tool WEB - this report is simply the documentation produced by WEB and processed by TeX. These programs were critical in discovering the results found in the papers: The matching polynomial of a distance-regular graph, Counting subgraphs of a regular graph, The number of subgraphs of a regular graph, and The matching polynomial of a regular graph.
Given a graph G, the i-th distance graph G_i has the same vertex set as that of G, and two vertices of G_i are adjacent if they are a distance i apart in the original graph G. Distance-regular and distance-transitive graphs have the property that the adjacency matrix of each distance graph can be expressed as a polynomial in the adjacency matrix of the original graph. A distance polynomial graph is defined by stipulating that it possesses this property. Here we start by exploring the basic properties of distance polynomial graphs. There is then a description of a large class of distance polynomial graphs, which are known as orbit polynomial graphs. After exploring some connections between association schemes and orbit polynomial graphs, we turn to the classification of these graphs. A characterization is given for the vertex-transitive case, and a portion of this result is generalized to the non-vertex-transitive case.
The number of distinct eigenvalues of the adjacency matrix of a graph is bounded below by the diameter of the graph plus one. Many graphs that achieve this lower bound exhibit much symmetry, for example, distance-transitive and distance-regular graphs. Here we provide a recursive construction that will create trees with the fewest possible eigenvalues. This construction is best at creating trees, but it will also create cyclic graphs meeting the lower bound. Unlike the graphs mentioned above, many of the graphs constructed do not exhibit large anounts of symmetry. A corollary allows us to determine the values and multiplicities of all of the nonsimple eigenvalues of the constructed graphs.
Given a graph and a polynomial, a matrix can be constructed by evaluating the polynomial with the adjacency matrix of the graph. When will the resulting matrix be the adjacency matrix of another graph? We answer this question for orbit polynomial graphs. We then investigate a conjecture of Weichsel relating the automorphism groups and eigenvalues of a graph G, and another graph generated from G by a polynomial. For vertex-transitive graphs with a prime number of vertices the conjecture is true, but we also provide examples where it is false.
This report contains the activities and results of the University of Puget Sound Mathematics and Computer Science Department Research Seminar, better known by its pseudonym, Peter Puget. The problems discussed here are all conjectures in graph theory which have been created by a computer program, Graffiti. Graffiti was developed by Siemion Fajtlowicz at the University of Houston. We have found counterexamples to most of the conjectures investigated, and have found a proof of one exceptional conjecture (See Using minimum degree to bound average distance). Besides counterexamples, and partial results on average distance, we also include results about the residue of a regular graph, which are used to disprove one conjecture.
We begin with a discussion of orbit polynomial graphs and their relationship with distance-transitive, distance-regular, and distance polynomial graphs. After finding a simple classification of the orbit polynomial graphs with a prime number of vertices, we use this result to provide short proofs of the classification of symmetric and distance-transitive graphs of prime order.
We introduce orbit polynomial graphs, and discuss their connections with distance-transitive, distance-regular, and distance polynomial graphs. After some general results, we classify all of the nonsymmetric trivalent orbit polynomial graphs.
This thesis examines the question of what happens when a polynomial is evaluated with the adjacency matrix of graph. Specifically, when is the resulting matrix the adjacency matrix of another graph? Which polynomials do this? What are the resulting graphs? The more significant results can be found in the papers: On the polynomial of a path, Orbit polynomial graphs of prime order and Trivalent orbit polynomial graphs.
Let A(P_n) be the adjacency matrix of the path on n vertices. Suppose that r(x) is a polynomial of degree less than n, and consider the matrix M = r(A(P_n)). We determine all polynomials for which M is the adjacency matrix of a graph. It happens that r(x) must be the characteristic polynomial of a path on m vertices, where m is odd and less than n.