Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-29T12:11:56.831Z Has data issue: false hasContentIssue false
  • English
  • Français

Twilight graphs

Published online by Cambridge University Press:  12 March 2014

J. C. E. Dekker
J. C. E. Dekker*
Affiliation:
Institute for Advanced Study, Princeton, New Jersey 08540
Get access Rights & Permissions [Opens in a new window]

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 = ‹ν, η› 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 = ‹ν, η› with n = card(ν), e = card(η), 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 = ‹ν, η›: 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.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 46 , Issue 3 , September 1981 , pp. 539 - 571
Copyright
Copyright © Association for Symbolic Logic 1981

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Behzad, M. and Chartrand, G., Introduction to the theory of graphs, Allyn and Bacon, Boston, 1971.Google Scholar
[2]Dekker, J.C.E., Good choice sets, Annali della Scuola Normale Superiore de Pisa, Serie III, vol. 20(1966), pp. 367–393.Google Scholar
[3]Dekker, J.C.E., Regressive isols, Sets, models and recursion theory (Crossley, J.N., Editor), North-Holland, Amsterdam, 1967, pp. 272–296.CrossRefGoogle Scholar
[4]Dekker, J.C.E., Countable vector spaces with recurisive operations. Part I, this Journal, vol. 34 (1969), pp. 363–387.Google Scholar
[5]Dekker, J.C.E., Countable vector spaces with recursive operations. Part II, this Journal, vol. 36 (1971), pp. 477–493.Google Scholar
[6]Dekker, J.C.E., Projective bigraphs with recursive operations, Notre Dame Journal of Formal Logic, vol. 19 (1978), 193–199.CrossRefGoogle Scholar
[7]Dekker, J.C.E. and Myhill, J., Recursive equivalence types, University of California Publications in Mathematics (N.S.), vol. 3 (1960), pp. 67–214.Google Scholar
[8]Dekker, J.C.E. and Ellentuck, E., Recursion relative to regressive functions, Annals of Logic, vol. 6 (1974), pp. 231–257.CrossRefGoogle Scholar
[9]Harary, F., Graph theory, Addison-Wesley, Reading, Massachusetts, 1969.CrossRefGoogle Scholar
[10]König, D., Theorie der endlichen und unendlichen Graphen, Akademische Verlagsgesellschaft, Leipzig, 1936. Reprinted by Chelsea, New York, 1950.Google Scholar
[11]McLaughlin, T., Trees and isols. Part I, Rocky Mountain Journal of Mathematics, vol. 5 (1975), pp. 401–418.CrossRefGoogle Scholar
[12]McLaughlin, T., Trees and isols. Part II, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 22 (1976), pp. 45–78.CrossRefGoogle Scholar
[13]Nerode, A., Extensions to isols, Annals of Mathematics, vol. 73 (1961), pp. 362–403.CrossRefGoogle Scholar
[14]Nerode, A., Extensions to isolic integers, Annals of Mathematics, vol. 75 (1962), pp. 419–448.CrossRefGoogle Scholar