Twilight Graphs
Dekker, J. C. E.
J. Symbolic Logic, Tome 46 (1981) no. 1, p. 539-571 / Harvested from Project Euclid
This paper deals primarily with countable, simple, connected graphs and the following two conditions which are trivially satisfied if the graphs are finite: (a) there is an edge-recognition algorithm, i.e., an effective procedure which enables us, given two distinct vertices, to decide whether they are adjacent, (b) there is a shortest path algorithm, i.e., an effective procedure which enables us, given two distinct vertices, to find a minimal path joining them. A graph $G = \langle\eta, \eta\rangle$ with $\eta$ as set of vertices and $\eta$ as set of edges is an $\alpha$-graph if it satisfies (a); it is an $\omega$-graph if it satisfies (b). $G$ is called r.e. (isolic) if the sets $\nu$ and $\eta$ are r.e. (isolated). While every $\omega$-graph is an $\alpha$-graph, the converse is false, even if $G$ is r.e. or isolic. Several basic properties of finite graphs do not generalize to $\omega$-graphs. For example, an $\omega$-tree with more than one vertex need not have two pendant vertices, but may have only one or none, since it may be a 1-way or 2-way infinite path. Nevertheless, some elementary propositions for finite graphs $G = \langle\nu, \eta\rangle$ with $n = \operatorname{card}(\nu), e = \operatorname{card}(\eta)$, do generalize to isolic $\omega$-graphs, e.g., $n - 1 \leq e \leq n(n - 1)/2$. Let $N$ and $E$ be the recursive equivalence types of $\nu$ and $\eta$ respectively. Then we have for an isolic $\alpha$-tree $G = \langle\nu, \eta\rangle: N = E + 1$ iff $G$ is an $\omega$-tree. The theorem that every finite graph has a spanning tree has a natural, effective analogue for $\omega$-graphs. The structural difference between isolic $\alpha$-graphs and isolic $\omega$-graphs will be illustrated by: (i) every infinite graph is isomorphic to some isolic $\alpha$-graph; (ii) there is an infinite graph which is not isomorphic to any isolic $\omega$-graph. An isolic $\alpha$-graph is also called a twilight graph. There are $c$ such graphs, $c$ denoting the cardinality of the continuum.
Publié le : 1981-09-14
Classification: 
@article{1183740830,
     author = {Dekker, J. C. E.},
     title = {Twilight Graphs},
     journal = {J. Symbolic Logic},
     volume = {46},
     number = {1},
     year = {1981},
     pages = { 539-571},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183740830}
}
Dekker, J. C. E. Twilight Graphs. J. Symbolic Logic, Tome 46 (1981) no. 1, pp.  539-571. http://gdmltest.u-ga.fr/item/1183740830/