Intersection-representation by connected subgraphs of some n-cyclomatic graph

Erich Prisner

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.

Two algorithms for the subset interconnection design problem

Erich Prisner

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 {X1,X2,...Xm} of subsets of V . A graph G with vertex set V is called feasible , if every Xi induces a connected subgraph of G. The minimum subset interconnetion design problem is to find a feasible graph with minimum cost sum. In this paper two heuristic algorithms for the problem are given and analyzed. Several classes of input data for which one of the algorithms finds optimal or at least approximative solutions are presented.

Convergence of iterated clique graphs

Erich Prisner

C(G) denotes the clique graph of the graph G, and Cn(G):=C(Cn-1(G)) is the nth iterated clique graph. A graph G clique-converges to a set M={F,C(F),C2(F),...,Cp-1(F)} of graphs if Cp(F)=F and Cm(G)=F for some integer m. The simplicial complex G^ of a graph G has the vertex sets of all complete subgraphs of G as simplices. By i we denote the ith modulo 2 Betti number of a complex. A vertex d of G is dominated by a neighbor z if every other neighbor of d is also adjacent to z. The completely pared graph P*(G) of a graph G is the graph we eventually obtain by successively deleting dominated vertices. The main results of the paper are the following:
(1) If G clique-converges to {F,C(F),...}, then 1(G^)= 1(F^) and 2(G^) 2(F^)= 2(C(F)^)=....
(2) If P*(G) is triangle-free, then G clique-converges to {P*(G)} or to {P*(G),C(P*(G))}.

On inverse problems for the cycle graph operator

Van Bang Le and Erich Prisner

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,

Representing triangulated graphs in stars

Erich Prisner

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 K1,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.

The dynamics of the line and path graph operators

Erich Prisner

For any integer k 1 the k-path graph Pk(G) of a graph G has all length-k subpaths of G as vertices, and two such vertices are adjacent whenever their union (as subgraphs of G) forms a path or cycle with k+1 edges. For k=1 we get the well-known line graph P1(G)=L(G). Iterated k-path graphs Pkt(G) are defined as usual by Pkt(G) := Pk(Pkt-1(G)) if t>1, and by Pk1(G) := Pk(G). A graph G is Pk -periodic if it is isomorphic to some iterated k-path graph of itself; it Pk -converges if some iterated k-path graph of G is Pk-periodic. A graph has infinite Pk-depth if for any positive integer t there is a graph H such that Pk t(H) = G. In this paper Pk-periodic graphs, Pk-convergent graphs, and graphs with infinite Pk-depth are characterized inside some subclasses of the class of locally finite graphs for k =1,2.

Key words and phrases: line graph, path graph, infinite graphs, graph dynamics
AMS classification: 05C99

In-tournament digraphs

Jorgen Bang-Jensen, Jing Huang, Erich Prisner

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.

Algorithms for interval catch digraphs

Erich Prisner

A family ((Sv,Tv)/ vV) of ordered pairs of intervals of the real line, each Sv containing its corresponing Tv, is called a nest representation. A directed graph D=(V,A) is an interval nest digraph if there is some nest representation with index set V such that xyA if and only if Sx and Ty have nonempty intersection. Interval catch digraphs allow next representations where each set Tv contains just one element. In this paper we show that the following problems can be solved efficiently for interval catch digraphs: (1) The RECOGNITION problem, (2) CLIQUE, CHROMATIC NUMBER, INDEPENDENT SET; PARTITION INTO CLIQUES, and (3) KERNEL---finding an independent and absorbing vertex set, and SOLUTION---finding an independent and dominating vertex set. The problems of (2) and (3) can be solved even for interval nest digraphs if a nest representation is known.

Infinite -periodic graphs

Erich Prisner

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 H as a subgraph of some iterated -graph p(H), provided obeys certain axioms. Then the results are applied to some graph-valued functions known in the literature.

Iterated k-line graphs

Van Bang Le and Erich Prisner

For integers k2 the k-line graph Lk(G) of a graph G is defined as a graph whose vertices correspond to the complete subgraphs on k vertices in G with two distinct vertices adjacent if the corresponding complete subgraphs have k-1 common vertices in G. We define iterated k-line graphs by Lkn(G):= Lk(Lkn-1(G)), where Lk0(G):=G. In this paper the iterated behavior of the k-line graph operator is investigated. It turns out that the behavior is quite different for k=2 (the well-known line graph case), k=3, and k4.

Facet Graphs

Van Bang Le and Erich Prisner

The k-facet graph Fk(K) of a pure (k-1)-dimensional simplicial complex K has all facets as vertices, and two such distinct vertices are adjacent whenever the corresponding facets of the complex have some common (k-2)-dimensional face. In this paper k-facet graphs and related concepts are investigated. Two characterizations are given and a first attempt towards a recognition algorithm is made. Some forbidden induced subgraphs for k-facet graphs are derived, and it is shown that connected k-facet graphs do not have more cliques than edges.

Key words: facet graphs, hypergraphs, simplicial complexes, neighborhoods, cliques, duality,
AMS subject classification: 05C65, 05C75

Graphs with few cliques

Erich Prisner

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 K1,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 f(n) derived in this way in most cases. Applications concern finding maximum cliques or computing the clique graphs for graphs in such classes.

Radius versus Diameter in Cocomparability and Intersection Graphs

Erich Prisner

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.

Parallel Chip Firing on Digraphs

Erich Prisner

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.

Intersection Multigraphs of Uniform Hypergraphs

Erich Prisner

The intersection multigraph of a simple hypergraph H=(V,{ Xi/i I} ) has {xi/i I} as vertex set. Two distinct vertices xi, xj are joined by |Xi Xj| parallel edges. It is shown how to recognize intersection multigraphs of 3-uniform, 3-conformal hypergraphs in polynomial time and reveal the (essentially unique) root hypergraph. For integers k 4, intersection multigraphs of k-uniform, k-conformal hypergraphs with one additional property can be recognized.

Key words: Intersection multigraph, uniform hypergraphs, cliques, recognition algorithm
AMS classification: 05C65, 05C85

A Note on k-Rotation Graphs

Erich Prisner

For an integer k 1 the k-rotation graph Rk(G) of a graph G=(V,E) has the set of all connected k-edge subgraphs of G as vertex set. Two such distinct vertices H1, H2 are adjacent in Rk(G) whenever there are labelings e1,...ek and d1,...dk of the edges of H1 respectively H2 such that ei and di have exactly one common vertex, for every i=1, ... k [CHJ90]. Surely the 1-rotation graph is just the ordinary line graph.

It is very easy to see that the line graph of every connected graph must be again connected. Since L2(G) is a spanning subgraph of R2(G) [CHJ90], the same is true for the 2-rotation graph. For higher k, the k'th iterated line graph Lk(G) is not necessarily a subgraph of Rk(G), so this approach ends here. However, in this note we show:

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

A Note on Powers and Proper Circular-Arc Graphs

Erich Prisner

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 kth power Gk of G has the same vertex set as G, and two distinct vertices x,y are adjacent in Gk whenever d(x,y)k.

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, Gk implies Gk+1 .

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).

Line Graphs and Generalizations --- A Survey

Erich Prisner

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.

Source Reversal and Chip Firing on Graphs

E. Goles and E. Prisner

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.

Additive Tree Spanners

Dieter Kratsch, Hoàng-Oah Le, Haiko Müller, Erich Prisner, Dorothea Wagner:

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,

Eccentricity-approximating spanning trees in chordal graphs

Erich Prisner

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 eccG(x)=maxy dG(x,y) and eccT(x)=maxy dT(x,y) do not differ too much, for every vertex x. That is, a distance dT(x,y) much higher than the original one dG(x,y) may be tolerable, provided this new distance is not much larger than the worst distances eccG(x) and eccG(y) in G. Such an application might be where locations measure their degree of centrality by means of their eccentricity and won't tolerate an increase by too much. For integers k 0, a spanning tree T is called eccentricity k-approximating if eccT(x) - eccG(x) k for every vertex x of T.

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,

Generalized Octahedra and Cliques in Intersection Graphs of uniform Hypergraphs

Erich Prisner

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.

Eulerian iterated Line Graphs and Digraphs

Erich Prisner

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 in Graphs I: Bounds on their number

Erich Prisner

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.

Recognizing k-path graphs

Erich Prisner

The k-path graph Pk(H) of a graph H has all length-k paths of H as vertices; two such vertices are adjacent in the new graph if their union forms a path or cycle of length k+1 in H, and if the common edges of both paths form a path of length k-1. In this paper we give a (nonpolynomial) recognition algorithm for k-path graphs, for every integer k greater than 1. The algorithm runs in polynomial time if we are only interested in k-path graphs of graphs of high enough minimum degree. We also present an O(|V|4)-time algorithm that decides whether for any input graph G=(V,E) there exist some integer k and some graph H of minimum degree at least k+1 with G=Pk(H). If it is, we show that k and H are unique, extending previous uniqueness results by Xueliang Li.

keywords: path graph, recognition algorithm.

The recognition problem for line bigraphs

Erich Prisner

Given are two graphs H1=(V,E1) and H2=(V,E2) on the same vertex set. The line bigraph is the bipartite graph with E1 E2 as vertex set, and an edge between e1 E1 and e2 E2 if the edges have some common vertex in G. Using the intersection multigraph of the set of all large bicliques, we show that there is an efficient recognition algorithm for line bigraphs under the additional assumption that both H1 and H2 have minimum degree at least 3. Without that degree assumption this recognition problem turns out to be NP-complete.

keywords: intersection bigraph, recognition algorithm, NP-completeness.
See here for more.

05C62: A Journey through Intersection Graph County

Erich Prisner

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.

Recognizing Random Intersection Graphs

Erich Prisner

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=Hk(n,p), where p >> n^{-1/2+}. Two related algorithms reconstruct almost every random graph G=G(n,p) from its k-line graph Lk(G) (which is the k-1-intersection graph of the set of all complete subgraphs on k vertices), and almost every random graph G from its k-1-in-k graph k-1,k(G) (which has all complete k-1-vertex subgraphs of G as vertices, two of them adjacent if they lie in some common complete k-vertex subgraph), for p >> n^{-1/k+} respectively p >> n^{-1/(2k-2)+}.
See here for more.

A note on intersection graphs of dual hypergraphs

Erich Prisner

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

Erich Prisner