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
{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.
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))}.
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 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.
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 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 ((Sv,Tv)/
v
V)
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.
-periodic graphs
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.
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.
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
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.
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,{ 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
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.
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).
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 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,
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 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.
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.
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=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.
It is shown that the first Betti numbers of the complexes of intersection graphs of dual hypergraphs coincide.