# 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
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2307/2273756
Options
 Save to my reading list Follow the author(s) My bibliography Export citation Find it on Scholar Edit this record Mark as duplicate Revision history Request removal from index

 PhilPapers Archive Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 23,664 External links Setup an account with your affiliations in order to access resources via your University's proxy server Configure custom proxy (use this if your affiliation does not provide a proxy) Through your library Sign in / register to customize your OpenURL resolver.Configure custom resolver
References found in this work BETA
T. G. McLaughlin (1976). Trees and Isols II. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 22 (1):45-78.
J. C. E. Dekker (1978). Projective Bigraphs with Recursive Operations. Notre Dame Journal of Formal Logic 19 (2):193-199.
T. G. McLaughlin (1976). Trees and Isols II. Mathematical Logic Quarterly 22 (1):45-78.
Citations of this work BETA

No citations found.

Similar books and articles
Thomas C. Brown (1979). Canonical Simplification of Finite Objects, Well Quasi-Ordered by Tree Embedding. Dept. Of Computer Science, University of Illinois at Urbana-Champaign.
Dwight R. Bean (1976). Effective Coloration. Journal of Symbolic Logic 41 (2):469-480.

### Added to index

2009-01-28

7 ( #499,539 of 1,902,892 )