# Twilight graphs

Journal of Symbolic Logic 46 (3):539-571 (1981)

# Abstract

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 η as set of vertices and η as set of edges is an α-graph if it satisfies (a); it is an ω-graph if it satisfies (b). G is called r.e. (isolic) if the sets ν and η are r.e. (isolated). While every ω-graph is an α-graph, the converse is false, even if G is r.e. or isolic. Several basic properties of finite graphs do not generalize to ω-graphs. For example, an ω-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 ω-graphs, e.g., n - 1 ≤ e ≤ n(n - 1)/2. Let N and E be the recursive equivalence types of ν and η respectively. Then we have for an isolic α-tree $G = \langle\nu, \eta\rangle: N = E + 1$ iff G is an ω-tree. The theorem that every finite graph has a spanning tree has a natural, effective analogue for ω-graphs. The structural difference between isolic α-graphs and isolic ω-graphs will be illustrated by: (i) every infinite graph is isomorphic to some isolic α-graph; (ii) there is an infinite graph which is not isomorphic to any isolic ω-graph. An isolic α-graph is also called a twilight graph. There are c such graphs, c denoting the cardinality of the continuum

## PhilArchive

Upload a copy of this work     Papers currently archived: 92,907

Setup an account with your affiliations in order to access resources via your University's proxy server

# Similar books and articles

Effective coloration.Dwight R. Bean - 1976 - Journal of Symbolic Logic 41 (2):469-480.
Infinitary logics and very sparse random graphs.James F. Lynch - 1997 - Journal of Symbolic Logic 62 (2):609-623.
Canonical simplification of finite objects, well quasi-ordered by tree embedding.Thomas C. Brown - 1979 - Urbana, Ill.: Dept. of Computer Science, University of Illinois at Urbana-Champaign.
Graphical models, causal inference, and econometric models.Peter Spirtes - 2005 - Journal of Economic Methodology 12 (1):3-34.

2009-01-28

48 (#339,348)

6 months
3 (#1,037,180)