Graph Operators

Picture

A Java Program by Erich Prisner

Version 0.99, December 1999


  1. How to get started
  2. What the program does
  3. Adjustments at the beginning
  4. Loading and saving objects
  5. How to apply operators
  6. Getting information on the focus object
  7. Three windows
  8. Protocol of your session
  9. Description of the operators
  10. Inverse Operators
  11. Hints for beginners
  12. Basic Definitions
  13. Some Literature

1. How to get started

Please check the manual for how to run Java applications on your operating system. Under Windows 95 for instance, this Java Application can be started by typing java DFG.Haupt or jre DFG.Haupt in the MS-DOS Prompt, depending on whether you have the full Java interpreter or only the Java runtime interpreter.

2. What the program does

The program gives an environment to transform graphs, digraphs, and hypergraphs into each other. No local transformations (like adding or deleting vertices or edges) are implemented, rather we concentrate on global operators that see the graph, digraph, hypergraph as a whole and transform it into another graph, digraph, or hypergraph. The operators are divided into six groups: In any case, the resulting object may be graph, digraph, or hypergraph. Now certain of these operators can be reversed in that way that one can tell the starting object if one knows only the resulting object and the operator applied. These "inverse" operators are grouped according to the end object of the original operator. At every time, one graph, one digraph, and one hypergraph are present. One of them is on focus. Every operator you use applies to the object on focus, thus only those buttons are enabled that make sense at the moment (for instance, if we have a graph on focus, then only operators of group 3 and inverse operators of group 4 are enabled). However, you may change focus by pressing one of the buttons "Graph", "Digraph", or "Hypergraph" (which are rather huge at the beginning).

3. Adjustments at the beginning

At the beginning you may (and should) adjust the main window to your own needs by adding the operators you need frequently as buttons. For this, you go to the menu "Buttons", and mark or dismark the operators, which are grouped in four groups ( 1, 4, 2+ 5, 3+ 6) there.

Certainly you can add or delete buttons in this way anytime during your session.


4. Loading and saving objects

Although small default start graphs/digraphs/hypergraphs are present from the beginning, you have to start by loading/creating a graph/digraph/hypergraph. These options are available under the "load G", "load D", and "load H" menus. Here you may load some existing objects (as "Graph1.txt", ... "Hypergraph2.txt") or objects you have saved previously or in previous sessions by choosing "..." and typing the file name. See in the subfolder "Daten" for some graphs, digraphs and hypergraphs. You may also generate random graphs, bipartite graphs, digraphs, or uniform hypergraphs, circulants, and certain Cayley digraphs.

To save an object you have to choose the "Save" button. You may choose an existing name (as "Graph1.txt") and overwrite the existing graph stored there, or you may choose an own name (which should have the form "Name.txt"). Then the object is stored as a text file in the directory "DFG/Daten". Since the format for graphs, digraphs, and hypergraphs is different, you should choose an name which indicates the type of the object. Since you may want to transfer to other graph programs as "Graphs and Groups" or "Pajek", there is the possibilitiy to save your graph in those formats.


5. How to apply operators

Operators can be applied either by double-clicking on the corresponding name in the three lists almost in the center of the main window, (containing (inverse) operators of type 1 and 4, 2 and 5, respectively 3 and 6) or, if you have already created a button on the main window for the operator, by clicking this button.

6. Getting information on the focus object

The buttons on the bottom of the main window give you some information on the focus object, such as diameter (for graphs and digraphs; if they are not connected respectively not strongly connected, then (somewhat incorrectly) the vertex number is displayed), maximum (out-) degree (for graphs or digraphs), maximum in-degree for digraphs, number of vertices or edges/ arcs/ hyperedges, and rank (for hypergraphs only). Some additional features as minimum degree of graphs, and minimum outdegree respectively minimum indegree of digraphs are contained in the menu "more parameters". The information is displayed in the text area on the top of the main window. Note that computing the diameter may take several minutes if the graph has 1000 or more vertices. By pressing the "Show" button, the object is displayed in the (black) DOS-window as adjacency matrix or list of hyperedges. If the object on focus turns out to be a graph with no more than 280 vertices, a white window opens and displays a graphical picture of the graph. Pictures of older graphs are overwritten once another graph picture emerges.

7. Three windows

Besides the main window there are two other windows visible (under Windows9*). The white window displaying the present focus graph after pressing the "Show" button, and the "black" MS-DOS window.

The Graph Picture can be modified by pressing the mouse near the vertex you want to move, and releasing the mouse at the new site. You can also change the size of the vertices and of the numbering of the vertices. No sophisticated graph drawing algorithms are implemented---for these we refer to other existing graph programs.

The third (DOS) Window may also contain some useful information at times, for instance, if you press "show", the adjacency matrices or hyperedge lists are shown there. Also at complicated computations, intermediate objects are shown there. Although the presentation there is rather messy (and German) it may be of some use at times.


8. Protocol of your session

In the file "DFG/Daten/Protokoll.txt" there should be all displays made during the session. However this feature only works if you exit the program by the close button, not if you apply Strg-Alt-C in the MS-DOS window. The older protocol is overwritten, so if you are interested in keeping one, you should rename it just after that session. Examples of such protocols are in "DFG/Daten/Proto1.txt" and "DFG/Daten/Proto2.txt".

9. Descriptions of the operators

Graph Operators

Inverse Graph Operators

Digraph Operators

Inverse Digraph Operators

Hypergraph Operators

Inverse Hypergraph Operators


10. Inverse Operators

We can divide the inverse operators into three groups:

LG^-1, LD^-1 If the line graph and digraph operators have been applied, they can be reversed in any case [L74], [R73], and [S82]. But these are the only nontrivial operators known with that property--- all other inverse operators work only under certain circumstances (The recognition problem is NP-complete in most cases). Note also that you don't always get the original digraph after applying the line digraph operator and its inverse, since this inverse is not unique, uniqueness is only achieved if minimum in- and out-degree of the original digraph is greater than 0.

Pk^-1, UL^-1: Recognizing k-path graphs for k >= 2 seems to be difficult; recognizing underlying graphs of line digraphs is NP-complete in general. However, if the digraphs have minimum in- and out-degree at least 2, or if the original graphs have minimum degree at least k+1, these inverse operators can be efficiently applied, compare [P97] [P**]. Computation of these inverse operators may however take some time.

H(k-1,k)^-1, I(t,k)^-1, L4^-1, G(k-1-in-k)^-1: All operators in this group use the inverse operators H(k-1,k)^-1. The problem with H(k-1,k)^-1 is that the (k-1)-hypergraph of a k-uniform hypergraph can only be computed if the original hypergraph H is "dense" enough [P*]. Although almost all random hypergraph obey this denseness, small hypergraphs do not obey it. On the other hand, all inverse operators except H(2,3)^-1 and G(2,3)^-1 use I(2,3)^-1. But I(2,3)^-1 uses a check for K5-e-freeness, which is very time-consuming. Thus for most of the operators in this group we have the dilemma that large start objects are not possible by time reasons, and for small ones the algorithms do not work. See the hints on which start objects work best.


11. Hints for beginners

If you start with random graphs on about 12 vertices and p= 0.38 or p=0.72 and iterate "L3" or "L4", then you will recognize different behavior. Under L4, you eventually get disjoint unions of K5, but under L3, you either get small graphs, (that can be easily described) or they explode. Another interesting start graph for iterating L3 is the graph GE12.txt.

You may load the graph "GE11.txt" and look what happens under "PStep3".

All circulants show interesting behavior under "T2", for instance try C11(1,2,3), C15(1,2,3,4), C19(1,2,3,4,5), C23(1,2,3,4,5,6), ... .

Complete graphs or digraphs are easily obtained as random graphs and digraphs with edge or arc-probability 1. You get k-uniform hypergraphs from random k-uniform hyperedges with many hyperedges (say 1000, for 10 vertices) by using the operator "Simple". Another convenient way for k=3,4 is to start with the empty hypergraph (a k-uniform hypergraph with 0 hyperedges, and going to the complement by pressing "Compl(3)" or "Compl(4)".

Cycles are also easy to generate, since they are circulants.

Recognizing underlying graphs of line digraphs L(D) is possible for all D with minimum in-and out-degree at least 2 (at least in version 1.0). Recognizing k-path graphs Pk(G) is possible if the minimum degree of G is at least k+1. The greatest challenge for the program is to try underlying graphs of line digraphs of digraphs with all in- and out-degrees equal to 2, or k-path graphs of (k+1)-regular graphs. Such graphs can be generated for instance as Cayley digraphs (for instance Cayley(S5,32451,34152) or Cayley(S5,54321,42153)) respectively circulants---one has to check however whether the resulting graph and digraph is connected respectively strongly connected (i.e. has diameter smaller than vertex number).

One can test whether a graph is the underlying graph of some iterated line digraph by pressing "UL^-1" and after that several times "L^-1". Try this for underlying graphs of iterated line digraphs of the digraphs "DE6.txt" or "DE7.txt".

Here are some sets of hypergraphs and graphs on which you can test the validity of the inverse operators of group 3 without having to wait too long for the computer to finish. In any case, you start with some very sparse (random) graph or hypergraph, go to the complement to obtain a dense one, and take this dense object as start of the operation. After that you apply the inverse operator, take again the complement, and you should arrive at the sparse object you had at the very beginning. The reason for starting with sparse objects is that it is much easier to check whether two sparse objects are isomorphic than to do the same for two dense objects.

You get nice (?) pictures of so-called "de Bruijn and Kautz graphs" as follows: Start with complete digraphs or irreflexive digraphs with 2 to 6 vertices (by creating a random digraph with 2 to 6 vertices and arc probability 1 and by pressing (or not) the button "Irreflexiv"). Then press "LineD" a couple of times, taking care that the resulting digraph has not more than 270 vertices. Press "Unter(D)" to obtain the underlying graph. Then "Show".

A hypergraph is linear if no two different hyperedges have two vertices in common. You get kind-of-random linear 3-uniform (4-uniform) hypergraphs by generating random 3-uniform hypergraphs and pressing "H(2,3)" ("H(3,4)").

Create designs from difference sets (as Diff9.txt or Diff41.txt) by applying "Translate". Take the dual and compute k-intersection graphs for various k. What do you observe?


Basic Definitions

A graph consists of a vertex set V, together with the edge set E, which is a subset of the set of all 2-element subsets of V. Two vertices x and y are adjacent if {x,y} E. We say a vertex x is incident with an edge {y,z} if x = y or x = z. The degree of a vertex is the number of incident edges. The maximum degree respectively minimum degree of a graph is the maximum respectively minimum degree of its vertices. A path of length k is a graph with x0,x1, ,xk as vertices and edges {x0,x1},{x1,x2} {xk-1, xk}, whereas a cycle of length k has vertices x0,x1,,xk and edges {x0,x1},{x1,x2} {xk-1, xk}, {xk,x0}. The distance between two distinct vertices in G is the shortest length of a path in G with the two vertices at the ends if there is such a path, otherwise it is . The diameter of the graph is the largest distance occuring. The complete graph Kk has k vertices and all possible edges between different vertices. A subset W of the vertex set of a graph G induces some induced subgraph G[W]: Its vertex set is W, and two distinct vertices are adjacent in G[W] if and only if they are adjacent in G.

A digraph D has a vertex set V and an arc set A, which is a subset of V ×V. If (x,y) A, then vertex y is called an out-neighbor of x, whereas x is an in-neighbor of y. The out-degree respectively in-degree of a vertex is the number of our-neighbors, respectively in-neighbors, and the minimum/maximum out-/in-degree of a digraph is simply the minimum respectively maximum out- respectively in-degree occuring in the digraph. A directed path of length k has vertices x0,x1, ,xk and arcs (x0,x1),(x1,x2), ,(xk-1,xk). The distance from vertex x to vertex y in D is the smallest length of a subpath from x to y in D, provided there is such a path, otherwise it is . The diameter of D is the largest occuring distance.

A hypergraph consists of a set together with some hyperedges, i.e. subsets of that set. The elements of the set are called vertices again. The rank of a hypergraph is the maximum cardinality of a hyperedge, and a hypergraph is called uniform if all hyperedges have the same cardinality. It is simple if all hyperedges are distinct, and linear if every two hyperedges have at most one common element.

Let a group G and a subset A of elements be given. The Cayley digraph has the elements of the group as vertices. There is an arc from x towards y if there is some element a in A with y = xa. A circulant digraph Cn(a1,a2,...ak) has n vertices labeled by 0,1,2, ... n-1 and there is an arc from vertex i to vertex j if |i-j| = ai (mod n) for some i. Circulant graphs are just underlying graphs of circulant digraphs.


Some Literature

If you are interested in the details of the algorithms for the inverse operators, you may find detailed descriptions in the following papers: Much information on the operators used are contained in the book