A hypergraph *H* is called *connected over*
a graph *G* with the same vertex set as *H*
if every hyperedge of *H* induces a connected subgraph of
*G*. A graph *F* is *representable* in the
graph *G* if there is some hypergraph *H* which is
connected over *G* and has *F* as its intersection
graph. Generalizing the well-known problem of representability
in forests, the following problems are investigated:
Which hypergraphs are connected over some *n*-cyclomatic
graph, and which graphs are representable in some
*n*-cyclomatic graph, for any fixed integer *n*?
Several notions developed in the theory of subtree hypergraphs
and chordal graphs (i.e. in the case *n=0*) yield
necessary or sufficient conditions, and in certain special
cases even characterizations.

An NP-complete generalization of
the minimum spanning tree problem is considered:
Given are a set *V*, a cost function
*c: V V
* **R ^{+}**,
and a collection
{

*C(G)* denotes the clique graph of the graph *G*,
and *C ^{n}(G):=C(C^{n-1}(G))* is the

(1) If

(2) If

The *cycle graph* of a graph is the intersection graph
of the edge sets of all the induced cycles of *H* .
The main result of this paper is: A *(K4-e) *-free graph is a cycle graph
if and only if it is a block graph where each vertex lies in a finite number
of blocks. Some additional results are also given.

Mathematics Subject Classification 05C99, 05C38

Keywords and phrases: cycle graph, intersection graphs,

A graph *G* is called *representable*
in a tree *T*, if *G* is isomorphic to the intersection graph of a family of
subtrees of *T* . In this paper those graphs are characterized which are
representable in some subdivision of the *K _{1,n}*. In the finite case
polynomial-time recognition algorithms of these graphs are given. But this
concept can be generalized to essentially infinite graphs by using no more
trees but `tree-like' posets and representability of graphs in these posets.

For any integer *k
1* the *k-path graph* *P _{k}(G)* of a graph

Key words and phrases: line graph, path graph, infinite graphs,
graph dynamics

AMS classification: 05C99

In this paper we define a generalization of tournaments and local tournaments. This is the class of in-tournaments -- any set of predecessors of any vertex induce a tournament. We show that many of the properties of tournaments that extend to local tournaments -- a generalization of tournaments introduced by the first author can be extended even to in-tournaments. For instance any strongly connected in-tournament has a directed hamiltonian cycle. We prove that the underlying graph of any in-tournament is 1-homotopic. We investigate the problem of which graphs are orientable as in-tournaments and prove that any chordal graph and any graph representable in a unicyclic graph can be so oriented. We prove that there is a polynomial algorithm for recognizing those graphs that can be oriented as in-tournaments.

A family *((S _{v},T_{v})/
vV)*
of ordered pairs of intervals of the real line, each

Given a graph-valued function
, a graph *G* is called
-*periodic* if there is some integer *p
1* such that *G* is
isomorphic to * ^{p}(G)*.
In this paper it is shown how to construct
-periodic graphs, given essentially
an embedding of a graph

For integers
*k2* the
*k**-line graph*
*L _{k}(G)*
of a graph

The *k*-*facet graph* *F _{k}(K)* of a pure

Key words: facet graphs, hypergraphs, simplicial complexes,
neighborhoods, cliques, duality,

AMS subject classification: 05C65, 05C75

*Cliques* are maximal complete subgraphs of a graph.
A class of (finite) graphs is said to have *few cliques*,
if there is some polynomial *f(n)* such that every member
*G=(V,E)* of the class has at most *f(|V|)* cliques.
If the class is closed under induced subgraphs, then it has
few cliques if and only if some complete multipartite graph
*K _{1,1,...1,2,...2}* is no member of the class.
This follows from two more general results on graphs where
each neighborhood or each common neighborhood of two nonadjacent
vertices has some special shape. Well-known examples are the
classes of chordal graphs, line graphs, and planar graphs.
We are also able to improve the bounds

Whereas in general graphs the only connection between radius and
diameter can be expressed by the inequality *r(G)
diam(G)
2r(G)*, in this paper it is shown that much sharper inequalities
of type *2r(G)- diam(G)
a* are valid inside the classes of
cocomparability graphs and trapezoid graphs, with
constants *a = 3,2*. For
circular-arc graphs and proper circular-arc graphs we obtain
*diam(G)- r(G)
b*, with constants *b = 2,1*.

Given some multidigraph, a *state* is any distribution of some
chips on its vertices. Now
we transform this initial state step by step. Every vertex
checks whether it is able to send one chip through every outgoing
arc. If it can, it does, otherwise it does not send any chip. All
vertices check and send in parallel. Finally, at every vertex all
incoming chips are added to the remaining chips. This transformation
on the set of states is iterated.

If the digraph and the total number of chips are finite, then we finally arrive at some periodic configuration. It is investigated how these periodic configurations and the periods look, depending on the digraph and the total number of chips. There is a sharp contrast in the behavior for Eulerian digraphs (where the in-degree of each vertex equals its out-degree) and non-Eulerian digraphs.

The *intersection multigraph* of a simple hypergraph
*H=(V,{ X _{i}/i I} )
* has {

Key words: Intersection multigraph, uniform hypergraphs,
cliques, recognition algorithm

AMS classification: 05C65, 05C85

For an integer *k
1* the *k*-*rotation graph* *R _{k}(G)* of
a graph

It is very easy to see that the line graph of every connected
graph must be again connected. Since *L ^{2}(G)* is a spanning subgraph
of

*
For every k
1 the k-rotation graph of every connected graph
is again connected.
*

All graphs considered are finite. The *distance*
*d(x,y)* between two vertices *x* and *y*
in some given graph *G=(V,E)* is the
length of a shortest *x*-*y* path, if there is at
least one, and infinite otherwise. For an integer
*k1*,
the *k*th power *G ^{k}* of

A *circular-arc graph* is the intersection graph of some
family of arcs of some circle. *Proper* circular-arc
graphs are intersection graphs
of such families, where no arc contains another.
*Proper interval graphs* are
proper circular-arc graphs with some representation such that
the union of the arcs does not cover the whole circle.

We call a class
of graphs *closed (under powers) * if every power
of any member of
lies again in
.
We call it *strongly closed (under powers) *, if for
every integer *k1*
and every graph *G*,
*G ^{k}
* implies

A. Raychaudhuri showed that the class of circular-arc graphs
is closed, and asked whether it may be strongly closed.
C. Flotow investigated some aspects of this
question and showed that the class of *proper*
circular-arc graphs is closed. In this note we prove that
this class of *proper* circular-arc
graphs is *strongly* closed (under powers).

The line graph *L(G)* of a graph *G* reflects the mutual positions of the
edges (lines), i.e., the vertices of *G* are the edges of *G*,
and two such vertices are adjacent whenever the corresponding
edges have nonempty intersection. The concept of line graphs emerged rather
early in graph theory, and most classical problems on them have
been resolved in the 1960s and early 1970s. This article
briefly sketches these classical results, but primarily surveys the recent
results on line graphs and the current status of the classical
problems for various generalizations of line graphs.

Starting with any orientation of some given undirected graph *G*,
what happens if we keep reorienting all arcs starting at sources?
Dynamical questions of that system are investigated, and the connections
to the well-known chip firing process is established.

A spanning tree of a graph is a *k-additive tree spanner* whenever the
distance of every two vertices in the graph or in the tree differs by at
most *k*. In this paper we show that certain classes of graphs, as
distance-hereditary graphs, interval graphs, asteroidal-triple free graphs,
allow some constant *k* such that every member of the class has some
*k*-additive tree spanner. On the other hand, there are chordal graphs
without *k*-additive tree spanner for arbitrary large *k*.

Key words: distance, graph spanners, spanning tree, algorithm, AT-free graph,
distance-hereditary graph, chordal graph,

AMS subject classification: 05C12, 05C85, 68R10, 68Q20, 90B80,

Spanning trees are the cheapest way to maintain connectivity. However, for some applications, connectivity is not enough: Rather is it desirable that distances in the tree are not much larger than distances in the original graph, for every pair of vertices. This yields the concept of additive or multiplicative tree spanners.

In applications where it is important that every vertex can reach every
other as quickly as possible, one might look for spanning trees where the
eccentricities *ecc _{G}(x)=max_{y}
d_{G}(x,y) * and

Every additive tree *k*-spanner is eccentricity
*k*-approximating.
Therefore, eccentricity *k*-approximating spanning trees can be found in
every interval graph for *k=2* [P97,KLMPW*,MVP96]
asteroidal-triple free graph for *k=3* [KLMPW*]
strongly-chordal graphs for *k=3* [BCD98].
However, for every *k* there is a chordal graph without tree *k*-spanner
[P97,KLMPW*]. With the slightly weaker concept of eccentricity-approximation, we
are successfull even for chordal graphs:

*
Every connected chordal graph has some eccentricity 2- approximating
spanning tree.
*

Key words: chordal graph, distance, eccentricity, spanning tree,

It is shown that *k*-uniform hypergraphs with *m*
edges contain at most
*O(m^{2k choose k})* maximal sets of pairwise
intersecting hyperedges, and
*p*-intersection graphs *G=(V,E)* of *k*-uniform hypergraphs
contain *O(|V|^{2(k-p+1) choose k-p+1})* maximal cliques.
In case *p=k-2*, the result is improved to *O(|V||E|)*.
For every fixed *k*, the results imply polynomial-time algorithms
for computing maximum sets
of pairwise intersecting hyperedges in *k*-uniform hypergraphs,
respectively maximal cliques in their intersection graphs.

It is shown that every strongly connected digraph
has either at most one or infinitely many of its iterated line digraphs
eulerian.
The proof uses a canonical way of `wrapping' a digraph *D* around
a directed cycle whose length is the greatest common divisor
of all directed cycle-length of *D*, which may be interesting
for its own. A simple characterization of undirected graphs
with some of its iterated line graphs eulerian is also given.

*Bicliques* are inclusion-maximal induced complete bipartite subgraphs
in graphs.
Upper bounds on the number of bicliques in bipartite graphs and
general graphs are given. Then those
classes of graphs where the number of bicliques is polynomial
in the vertex number are characterized,
provided the class is closed under induced subgraphs.

The *k*-path graph *P _{k}(H)* of a graph

keywords: path graph, recognition algorithm.

Given are two graphs *H _{1}=(V,E_{1})* and

keywords: intersection bigraph, recognition algorithm, NP-completeness.

See here for more.

The theory of intersection graphs will soon have, together with others,
an own matematics subject classification number 05C62.
This promotion may be mainly due to the fact that intersection graphs
have nice applications---some of them even originated in such applications.
Although a large amount of work has been done for several special classes
of intersection graphs, there are still only very few basic concepts and
ideas which work for general intersection graphs,
and even these ideas are not as widely known as they maybe should.
So let me introduce 05C62, at least the intersection graph part,
in this paper to you.
Whereas most surveys concentrate on geometric intersection graphs,
my emphasis will be on so-called `discrete' models.
The discussion of geometric models and the Helly property will hopefully
also make clear why the famous models, as interval graphs, are relatively easy
to deal with, and
where the difficulties for the others lie.
A number of variants or generalizations, like *l*-intersection,
intersection multigraphs, intersection bigraphs and digraphs,
and connection graphs, will also be treated.

(This survey was partially written during a stay at Santiago de Chile,
as script for some minicourse held there in June/July 1998.
I am very grateful for the support received by FONDAP
and for the hospitality of the Universidad de Chile.)

The WWW-version can be found here.

A polynomial-time algorithm is given which succeeds in reconstructing the
simple *k*-uniform hypergraph *H* from its *l*-intersection graph,
for almost all random *k*-uniform hypergraphs *H=H _{k}(n,p)*, where

See here for more.

It is shown that the first Betti numbers of the complexes of intersection graphs of dual hypergraphs coincide.

Erich Prisner