Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
Computable Categoricity of Graphs with Finite Components

Edit abstract data

Author(s): Barbara Csima, Bakhadyr Khoussainov and Jiamou Liu
Slot: Mon, 11:20-11:40, Vice-Rector (col. 4)


A computable graph is computably categorical if any two computable presentations of the graph are computably isomorphic. In this paper we investigate the class of computably categorical graphs. We restrict ourselves to strongly locally finite graphs; these are the graphs all of whose components are finite. We present a necessary and sufficient condition for certain classes of strongly locally finite graphs to be computably categorical. We prove that if there exists an infinite Delta-2 set of components that can be properly embedded into infinitely many components of the graph then the graph is not computably categorical. We outline the construction of a strongly locally finite computably categorical graph with an infinite chain of properly embedded components.

websites: Arnold Beckmann 2008-05-18 Valid HTML 4.01! Valid CSS!