Computability of graphs

We consider topological pairs $(A,B)$, $B\subseteq A$, which have computable type, which means that they have the following property: if X is a computable topological space and $f:A\to X$ a topological imbedding such that $f(A)$ and $f(B)$ are semicomputable sets in X, then $f(A)$ is a computable set in X. It is known, e.g., that $(M,\partial M)$ has computable type if M is a compact manifold with boundary. In this paper we examine topological spaces called graphs and we show that we can in a natural way associate to each graph G a discrete subspace E so that $(G,E)$ has computable type. Furthermore, we use this result to conclude that certain noncompact semicomputable graphs in computable metric spaces are computable.     

The optimal general upper bound for the distinguishing index of infinite graphs

The distinguishing index $D\prime \left(G\right)$ of a graph $G$ is the least cardinal number $d$ such that $G$ has an edge-coloring with $d$ colors, which is preserved only by the trivial automorphism. We prove a general upper bound $D\prime \text{◂≤▸}\left(G\right)\le \mathrm{\Delta }-1$ for any connected infinite graph $G$ with finite maximum degree $\mathrm{\Delta }\ge 3$. This is in contrast with finite graphs since for every $\mathrm{\Delta }\ge 3$ there exist infinitely many connected, finite graphs $G$ with $\text{◂,▸}D\prime \left(G\right)=\mathrm{\Delta }$. We also give examples showing that this bound is sharp for any maximum degree $\mathrm{\Delta }$.