Extractions: How to contact me This material comes from some notes for a University of Waterloo course taught by Herb Shank (c. 1975). I have an export of a maple worksheet, showing these operators: http://www.math.fau.edu/Locke/courses/GraphTheory/LinSpGen.htm Back to the Graph Theory Index Let G be a finite, connected, directed graph. If the vertex set of G is ,v ,...,v m and the edge set of G is ,e ,...,e n , then it is useful to consider an oriented edge to be an ordered pair of vertices (say tip first, then tail). So: e i =(v s ,v r would indicate that edge e i is directed from v r to v s If F is a field, and S is a finite set, let F denote the set of all linear combinations of elements of S with coefficients in F . If addition and scalar multiplication are "coordinatewise", then F is a vector space over F having S as one of its bases. Where unambiguous, the subscript F may be omitted. Despite this notational convention, F is important enough to have a special name, C F (G) . When it is convenient and no misinterpretation is possible, we will write
Graphs Glossary Short definitions with cross-references by Bill Cherowitzo. http://www-math.cudenver.edu/~wcherowi/courses/m4408/glossary.htm
List Of Small Graphs Information System on Graph Class Inclusions, University of Rostock. http://wwwteo.informatik.uni-rostock.de/isgci/smallgraphs.html
Extractions: Graphs ordered alphabetically Graphs ordered by number of vertices 3 vertices 4 vertices ... Special families of graphs Note that complements are usually not listed. So for e.g. co-fork, look for fork. Only individual graphs are listed, not families or configurations. ∪ K cross star X ... X 3 vertices - Graphs are ordered by increasing number of edges in the left column. back to top back to top
Extractions: This archive contains material on the course taught by Ron Shamir in the department of Computer Science of Tel-Aviv university , on 10/91-2/92 (Fall 92), 4-6/94 (Spring 94) and 4-6/97 (Spring 97). This was a one-semester graduate course open also to seniors, with one three-hour meeting each week. The course emphasized algorithmic and structural aspects of "nice" graph families, in particular perfect graphs, interval graphs, chordal graphs and comparability graphs. The Spring 94 and Spring 97 course had a similar basis, but emphasized more recent material, and made a lot of reference to applications in molecular biology. (See the webpage Algorithms for Molecular Biology for much more on these aspects.) Material available: Detailed course outline Spring 97 (HTML) Spring 94 (ASCII) Fall 92 (ASCII) Spring 1997 course material (unorganized; some links were not updated and some material is readable only to TAU browsers. Sorry.)
Gordon Royle's Cubic Graphs List of cubic graphs maintained by Gordon Royle. http://www.csse.uwa.edu.au/~gordon/remote/cubics/
Extractions: This page provides access to the ever popular listings of cubic graphs together with a variety of data relating to these graphs. Please note that these pages are being developed incrementally on an "as-needed" basis, so if you want anything, then just ask me on gordon@cs.uwa.edu.au and unless its a bad time, then I will probably oblige. Most of this work originates from my PhD thesis Constructive Enumeration of Graphs , though the techniques used there are now largely obsolete. At present the best cubic graph generation program is written by, and available from Gunnar Brinkmann. The data from the snarks section was generated by Gunnar, so thanks to him for letting me incorporate it into this database. Exact numbers of cubic graphs are known by results of Robinson and Wormald for values up to 40 vertices. The cubic graphs on up to 20 vertices, together with some smaller families of high girth cubic graphs on higher numbers of vertices are available. The larger numbers in the table, other than the Robinson/Wormald results are due to Gunnar Brinkmann. Each number in the table below is a link to a file of graphs in format. The largest file is the cubics on 22 vertices at 300Mb.
Gordon Royle's Small Graphs Gordon Royle s tables of small graphs with Maple software. http://www.csse.uwa.edu.au/~gordon/remote/graphs/
Extractions: This site is intended to collate much of the data about small graphs that I have to keep on recomputing. It is primarily designed for my own use, but anyone else is free to check out the numbers or the graphs. If you are interested in small graph data that is not here, then feel free to mail me at gordon@maths.uwa.edu.au because I may have just not got around to installing it. The exact numbers of graphs on n vertices and e edges can be computed by using Polya enumeration theory. This enables us to produce a series of tables of the following format. The tables were produced by a Maple program written with Brendan McKay (well, he wrote it after joint discussions). Graphs with 4 vertices #edges Connected graphs All graphs Total Tables of this nature are available for the graphs on 1-16 vertices. 1 vx 2 vx 3 vx 4 vx ... 16 vx The following table gives the number of connected bipartite graphs separated according to the size of the bipartition. Each row corresponds to a fixed number of vertices, while each column refers to the smaller part of the bipartition. Thus the entry 34 for 7 vertices and m=3 indicates that there are 34 conected bipartite graphs on 7 vertices with partition of size (3,4).
Some Open Problems Compiled by Jerry Spinrad. http://www.vuse.vanderbilt.edu/~spin/open.html
Some Open Problems Open problems and conjectures concerning the determination of properties of families of graphs. http://www.eecs.umich.edu/~qstout/constantques.html
Extractions: These problems and conjectures concern the determination of properties of families of graphs. For example, one property of a graph is its domination number. For a graph G , a set S of vertices is a dominating set if every vertex of G is in S or adjacent to a member of S . The domination number of G is the minimum size of a dominating set of G . Determining the domination number of a graph is an NP-complete problem, but can often be done for many graphs encountered in practice. One topic of some interest has been to determine the dominating numbers of grid graphs (meshes), which are just graphs of the form P(n) x P(m) , where P(n) is the path of n vertices. Marilynn Livingston and I showed that for any graph G , the domination number of the family G x P(n) has a closed formula (as a function of n ), which can be found computationally. This appears in M.L. Livingston and Q.F. Stout, ``Constant time computation of minimum dominating sets'', Congresses Numerantium (1994), pp. 116-128.
Extractions: Problems in Signed, Gain, and Biased Graphs Compiled by Thomas Zaslavsky This is a fairly miscellaneous and incomplete selection of problems that I happen to have taken an interest in not necessarily an active interest. Some are open and some are solved or partially solved as for example a problem may have been shown to be NP-complete but special cases could still be solved exactly or algorithmically. This list is intended to supplement the many problems in the Bibliography . There is just a small amount of duplication. For the present, the problems here all concern signed graphs. However, many of them have obvious generalizations. References are as cited in the Bibliography . All the terms employed should be defined in the Glossary . If you find any missing, or if you have suggestions for this page, please notify me! NOTE: A PostScript version is available. It is slightly more up-to-date and it is the only one that will be maintained and expanded. I. Direct Measures of Imbalance (June 8-10 1998) Imbalance of a signed graph can be measured in numerous ways. Here are problems concerning some measures that have appeared in the literature. The greatest interest has been in the edge version of frustration. (The problems in part II can be regarded as measuring imbalance in a different way.)
Perfect Graphs Conjectures and open problems, maintained at the AIM. http://www.aimath.org/WWN/perfectgraph/
Extractions: Perfect Graphs This web page highlights some of the conjectures and open problems concerning Perfect Graphs. If you would like to print a hard copy of the whole outline, you can download a dvi postscript or pdf version. Recognition of Perfect Graphs Polynomial Recognition Algorithm Found Interaction Between Skew-Partitions and 2-joins The Perfect-Graph Robust Algorithm Problem ... A Possible New Problem Skew-Partitions Extending a Skew -Partition Graphs Without Skew-Partitions Graphs Without Star Cutsets Finding Skew-Partitions in Berge Graphs ... beta-perfect graphs Partitionable Graphs Perfect, Partitionable, and Kernel-Solvable Graphs Partitionable graphs and odd holes A Property of Partitionable Graphs Small Transversals in Partitionable Graphs ... The Imperfection Ratio Integer Programming Partitionable Graphs as Cutting Planes for Packing Problems? Feasibility/Membership Problem For the Theta Body Balanced Graphs Balanced circulants ... P4-structure and Its Relatives The individual contributions may have problems because converting complicated TeX into a web page is not an exact science. The dvi, ps, or pdf versions are your best bet.
Extractions: (compiled by Maria Chudnovsky) A bibliography on perfect graphs Home pages of people interested in perfect graphs This collection is written for people with at least a basic knowledge of perfect graphs. Uninformed neophytes may look up the missing definitions on the web in Alexander Schrijver's lecture notes or in Jerry Spinrad's draft of a book on efficient graph representations etc. or in MathWorld . Books on perfect graphs include M. C. Golumbic, Algorithmic graph theory and perfect graphs.
