Twilight graphs

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


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



    Upload a copy of this work     Papers currently archived: 94,749

External links

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

Through your library

Similar books and articles


Added to PP

49 (#322,374)

6 months
4 (#1,051,886)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Recursion relative to regressive functions.J. C. E. Dekker & E. Ellentuck - 1974 - Annals of Mathematical Logic 6 (3-4):231-257.
Trees and Isols II.T. G. McLaughlin - 1976 - Mathematical Logic Quarterly 22 (1):45-78.
Trees and Isols II.T. G. McLaughlin - 1976 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 22 (1):45-78.
Projective bigraphs with recursive operations.J. C. E. Dekker - 1978 - Notre Dame Journal of Formal Logic 19 (2):193-199.

Add more references