but
it is allowed that two vertices x,y lying in exactly
t of them, where
t < k, lie in exactly the same.
We could add the onevertex complete graphs
{x} and {y} to the list in that case.
To
be more precise, the deletions were crossed with point mutations.
A deletion which overlaps a point mutation cannot recombine with it.
Thus deletions and point mutations should form the hyperedges and points
of some interval hypergraph, if the hypothesis of linearity is true.
There
are few exceptions for line graphs:
Coloring, for instance, is still NPcomplete
for line graphs (since it is equivalent to edge coloring
arbitrary graphs).
The Hamiltonian cycle problems is also NPcomplete for line graphs.
An example of a hard problem even for interval graphs
is ACHROMATIC NUMBER
(Bodlaender, IPL (1989) 135138).
Me too
wrote this in one of my publications,
and somehow seem to believe in it stillyou wouldn't
spend so much time
on a topic you believe intractable.
if
every pair of vertices
in a kelement set S is covered
by some hyperedge, then this set must be a hyperedge
If
WV and
G = ((A,
(S_{x}/x V))),
then G[W]=(
(A,(S_{x}/x W))).
Note
that U is simply the intersection graph of the
hypergraph (_{
S
P} S, P).
It is here that P being a countable set is required.
This
could also expressed as:
If N[x]=N[y] and if G  x lies in G(P),
then G also.
For the proof, note that you simply have to add
S_{x} := S_{y}
to the hypergraph.
For
instance, we might choose all
S_{x(i)} as subsets of
NN such that
S_{x(i)} =
{(i,j)/jN}
{(j,i)/ j < i, x(i)x(j)
E}.
This
is not true for infinite graphs, compare R. Halin,
On the representation of triangulated graphs in trees,
Europ. J. Comb. 5 (1984) 2328.
where a neighbor of an edge is adjacent
to at least one of its vertices
One way of attacking the
dancing club example consists
in searching for asteroidal triples of edges.
which
can be done in this special
case rather easily, since each
K_{3,3} lies in a unique biclique
If B contains bicliques containing
K_{3,4}, we choose this as B_{0}.
There are, however, some technical details:
We have to check whether every vertex lies in at most one head of a
biclique and at most one tail of a biclique.
If some vertex does not lie in some head, then we have to add a
artificial pair (,{v})
which gets a source in D,
and the same for sinks. We may also sample some or all vertices
v_{1},v_{2},..., v_{s}
which lie in no head of a diclique,
and instead of adding all these separate new pairs, we add
(,
{v_{1},v_{2},...,v_{s}})
they use
completely different terminology.
The theorem has been rediscovered several times, compare
Y. Shibata, On the tree representation of chordal graphs,
J. Graph Th. 12 (1988) 421428,
but also some unpublished papers by F.V. Jensen, C.E. Carraher,
and myself.
the multigraph
is considered as a weighted graphevery edge has its
multiplicity as weight.
There are,
however, results in this direction which do not use
the weightedcliquegraphTheorem, see E. Prisner,
Representing triangulated graphs in stars,
Abh. Math. Sem. Univ. Hamburg 62 (1992) 2941,
for subdivisions of K_{1,n}, and see KoWei Lih,
Ranks of chordal graphs,
Bull. Inst. Math. Acad. Sci. 16 (1988) 357364,
for trees where there is some subpath such that every vertex
of the tree
has distance at most k to these path.
we also have
S_{x}^{t} :=
_{{y/ d(x,y)
t1} S_{y}.
as the union of S_{x}^{t1} and those S_z
intersecting S_{x}^{t1}.
intersection graphs
of trapezoids between two fixed parallel lines.
This is true
for proper circulararc graphs, compare E. Prisner,
A note on powers and proper circulararc graphs, JCMCC 1997 .
Choose a maximum matching
M (see J. Edmonds, R.M. Karp,
Theoretical improvements in algorithmic efficiency for
network flow problems,
J. ACM 19 (1972) 248264),
take all vertices not covered by M into S.
Then it is possible to add for every edge of M
one of its vertices
into S and still maintain independence.
There follows
that there is some
algorithm for the following problem to find H
for intersection graphs
(H) of
large
random
linear 3uniform simple hypergraphs H.
The algorithm succeeds in finding some such H in almost
every case in polynomial time.
In the few cases where
(H)
7,
either we need superpolynomial time, or we don`t compute H.
Two different
symmetrical vertexhyperedge incidence matrices for
the same selfdual hypergraph:
The second matrix is obtained from the first one by permuting
the columns as (13651)(24).
1  1  0  1  0  1 
1  1  1  0  1  1 
0  1  1  1  1  0 
1  0  1  1  1  1 
0  1  1  1  1  0 
1  1  0  1  0  1 

0  1  1  1  1  0 
1  0  1  1  1  1 
1  1  0  1  0  1 
1  1  1  0  1  1 
1  1  0  1  0  1 
0  1  1  1  1  0 

Since the first matrix has all main diagonal elements `1´, and
the second `0´ on the main diagonal, this hypergraph
can be expressed as the closedneighborhood hypergraph of some graph
(those whose adjacency matrix is the first matrix, with all entries of
the main diagonal replaced by ´0´),
and also as the neighborhood hypergraph of some graph
(those with the second matrix as adjacency matrix).
Let
G = _{t}(H)
for the hypergraph
H=(A,S_{x},xV).
Then the sets a*,
aA,
do no longer induce complete subgraphs in G.
Rather every intersection of p of these sets must be complete,
and all these intersections (which are just our star graphs)
cover the edge set of G. Concentrating on these sets
a* has the advantage that properties of H
more easily translate into properties of these sets a*
than into properties of our star graphs.
It has the disadvantage that we have no clue how these sets
a* may look like in G.
There are numeruous examples:
There are characterizations of graphs whose line graphs are
perfect, interval, planar, and so on, see
[P96].
Another question that has received some attention is the question of
which digraphs have interval (or chordal)
competition graphs, compare
[MM99]
...
...
Erich Prisner
made on January 12, 1999,
last changed on February 3, 1999.