Return to Revisions

The answer is "yes": there is such a family of $F$ functions. In fact, a single computable function, acting on a single integer argument, suffices. We may do this by storing essentially complete information about the graph, and about the process of "constructing" the graph $G$ (that is, the process of computing suitable integers $n_j$ representing vertices $v_j \in V(G)$), in the integers $n_j$ themselves.

Edit: My original answer contained an error in which the correct adjacency relations were not properly produced. I correct this below, and have taken the opportunity to make other minor revisions.

We may specify a graph on $n$ vertices using a single integer by a number of different methods, such as using binary representation to use an $n^2$ bit integer to give the adjacency matrix of the graph. (The leading 1 represents an entry in the diagonal, which may serve to define the size of the graph without denoting any edges if we consider only simple graphs.) Denote this binary representation of the graph $G$ by $g \in \mathbb N$. We compute the integers $n_j$ by carrying $g$ as the exponents of different primes, and using other prime factors to "induce" adjacency between the integers representing different integers.

Let $p_j$ denote the $j^{\textrm{th}}$ prime, with $p_1 = 2$, $p_2 = 3$, etc. We define $$ N_j = p_j^g $$ which will act as a "label" of sorts for our vertices; each vertex $v_j \in V(G)$ (for an arbitrary ordering of the vertices) will be represented by an integer which is divisible by the prime $p_j$, but not by any other prime $p_k$ for $1 \le k \le n$. At the same time, this labelling carries with it an entire description of the graph, as well as the vertex ordering (in this case, given by the ordering of the rows/columns of the adjacency matrix of $G$). The smallest prime factor of the integer $n_j$ corresponding to the vertex $v_j$ will indicate which vertex it is in the order, and carry a complete description of the graph $G$.

We may induce adjacency among the vertices by giving them appropriate common prime factors. A simple way to do this is to associate a prime to each edge, and give any two vertices belonging to a common edge the corresponding prime factor. (Vertices which do not share an edge in common will have no common prime factors, and thus be coprime.) We order the possible edges by considering the lexicographic ordering on all ordered pairs $(v_j, v_k)$ such that $v_j < v_k$: thus the possible edge $v_j v_k$ (for $j < k$) will be edge number $\varepsilon(j,k) = \binom{k-1}{2} + j$ in the enumeration. More generally, we may define $$ \varepsilon(j,k) = \binom{\max \{j,k\} - 1}{2} + \min \{j,k\} .$$ We may represent the adjacency of two vertices $v_j, v_k$ by giving their corresponding integers $n_j, n_k$ a common prime factor, namely the prime $p_{\varepsilon(j,k)}$. The exponents of the primes $p_{n+1}$ through $p_{n+\binom{n}{2}}$ in the integers $n_j$ as forming an incidence matrix of edges to vertices.

Thus, we may let $F(x)$ be the function which computes the following:

1. Determine the smallest prime $p_{j-1} \mid x$, and the corresponding index $j$.
2. Determine the exponent, $g$, of the largest power of $p_{j-1}$ which divides $x$.
3. Extract from $g$ complete information about the graph $G$, including its size $n$.
4. Determine the next largest prime $p_j > p_{j-1}$.
5. Compute $N_j = p_j^g$.
6. Compute $M_j = p_{n+j}$.
7. For each $1 \le k \le n$, $k \ne j$:
   • Compute $\varepsilon(j,k)$.
   • If $v_j$ is adjacent to $v_k$ in $G$, set $M_j \leftarrow M_j p_{n+\varepsilon(j,k)}$.
8. Return $y = N_j M_j$.

To produce an appropriate $F$-sequence which represents $G$, it then suffices to compute $n_1$, which is $$ n_1 = p_1^g \prod_{k \ne j} {p_{\varepsilon(j,k)}}^{A_{j,k}} , $$ where $A$ is the adjacency matrix of $G$; this suffices to iteratively produce the other integers $n_k$ using $F$.

The above can be readily extended to accommodate hypergraphs (allow more than one vertex per 'edge'), digraphs (use primes to represent ordered pairs instead of unordered pairs), and other generalizations; one only needs to choose a suitable representation, and store it in an integer in some way which can be extracted. These are standard tricks in computability theory; we are just adapting Godel numbering for a special purpose in this case.

If you want an "interesting" way of representing graphs by models in integer sequences, which does not just amount to packing and unpacking of data structures in the integers, you're going to have to impose some non-trivial bounds --- on the integer sizes, on the computational efficiency of the procedure, etc. --- and then, you will almost certainly have to be satisfied with obtaining only some special class of graphs. But that special class may still be an interesting one, if your computational constraints are well-chosen.