graph classifiers

[John Stell <j.g.stell@cs.keele.ac.uk>]

The classifier, \Omega, for subgraphs has two nodes and five edges.
The bi-Heyting algebra of subgraphs of a graph has two complement
like operators, $\neg$ and $\suppl$. These satisfy
$G \meet \neg G = \bot$ and $G \join \suppl G = \top$.
One of these ($\neg$) arises from 
an endomorphism of $\Omega$ but the other does not.

The operations $\neg$ and $\suppl$ are nicely dual in some ways
but only one can be described in terms of $\Omega$.
Is there some kind of explanation for this?

It is possible to find a graph $\Delta$ and to describe a given 
subgraph as a morphism to $\Delta$ and to obtain $\suppl$ as an
endomorphism of $\Delta$. But although there is a morphism
from $\Delta$ to $\Omega$, we don't get $\neg$ via any endomorphism
of $\Delta$. $\Delta$ has four nodes corresponding to a classification
of nodes as (1) out (2) in and with all incident edges in (3) in and
with all incident edges out (4) in and with some incident edges in
and some out. Of course this is analogous to the edges in 
$\Omega$. There are four kinds of edge identified by $\Omega$
(working with a version of $\Omega$ for undirected graphs)
(1) in (2) out and with all incident nodes out (3) out and
with all incident nodes in (4) out and with some incident nodes out
and some in. Is there a formal sense in which $\Delta$ and $\Omega$
are dual to each other? Is there a better way to view $\suppl$ as
coming from some kind of classifier of graphs?

Does anyone have any comments or suggestions for relevant literature?

John Stell



--------------------------------------------------------------------
Dr John Stell
Department of Computer Science         email     john@cs.keele.ac.uk
Keele University
Keele, Staffordshire,                  telephone +44 1782 584083
ST5 5BG   U. K.                        fax       +44 1782 713082
http://www.keele.ac.uk/depts/cs/Staff/Homes/John/homepage.html
--------------------------------------------------------------------