### Motivation (added)

A finite $n$-set is uniquely described (up to isomorphism) by a single population number $n$.

A finite $n$-set with $k$ predicates is uniquely described (up to isomorphism) by $2^k$ population numbers $n_i$, corresponding to the $2^k$ combinations of predicates, $\sum_{i=1}^{2^k} n_i = n$

A finite $n$-set with 1 binary relation (a graph $G$) can be uniquely described (up to isomorphism) by $k$ population numbers $n_i$, corresponding to its $k$ $Aut(G)$-orbits, provided these are appropriately described, $\sum_{i=1}^{k} n_i = n$.

I want to clarify what an appropriate description of the orbits might be and whether there is something like a canonical description of the orbits.

### Definition 1

Let $v$, $w$ be vertices of a finite graph $G$. $v$ and $w$ are **conjugate** ($v \sim w$) iff there is a $g \in Aut(G)$ with $g(v) = w$.

*Question 1 (postponed)*

*Is there an official and more common name for this equivalence? (Comment: I formerly called it "equivalent" but already changed this to "conjugate", thanks to Pete's hint.)*

### Definition 2 (third revision)

Let $G$ be a graph, $v \in V(G)$ and $\phi_v(x)$ be a first order vertex property (formulated in the first order language of graphs) such that $(\forall w \in V(G)\ )\phi_v(w) \Leftrightarrow v \sim w$.

Let $\lbrace \phi_v(x)\rbrace_{[v] \in G/_\sim}$ be a family of such properties.

If all graphs $H$ for which there is a bijection $f:V(G)\rightarrow V(H)$ with

$\phi_v(x) \Leftrightarrow \phi_v(f(x))$ for all $[v] \in G/_\sim$

are isomorphic to $G$, we call the family of properties $\lbrace \phi_v(x)\rbrace_{[v] \in G/_\sim}$ **distinguishing with respect to $G$**.

*(Comment: I added w.r.t $G$ to make things clearer and to be more precise.)*

### Claim

Given a graph $G$ and a distinguishing family of properties w.r.t. $G$ then the population function $f: \lbrace \phi_v(x)\rbrace_{[v] \in G/_\sim} \rightarrow \mathbb{N}$ with $f(\phi_v(x)) = |[v]|$ determines the graph up to isomorphism.

### Definition 2a (added)

A distinguishing family of properties is **minimal** if its overall number of bound variables is minimal.

*(Comment: Minimal distinguishing properties might serve as a canonical form of a graph.)*

### Question 2

Is there an official and more common name for distinguishing properties?

### Question 3 (second revision)

Can a distinguishing family of properties be computed from the adjacency matrix in linear time? Or is this problem provably as hard as graph isomorphism?

*Addendum:* As pointed out in the second answer (Mariano's) it is straight forward to begin with a complete description of the graph (one existential formula, stating that there are exactly $n$ different vertices and their relations) and make successively each single variable free. In the resulting $|G|$ formulas one then has to find the orbits (= equivalent formulas) which is probably as hard as graph isomorphism.

### Question 3a (added)

Can a *minimal* distinguishing family of properties be computed from the adjacency matrix in linear time? Or is this problem provably as hard as graph isomorphism?

*Question 4 (postponed)*

*Which language $L$ is appropriate? Can it always be the language of first order logic with a graph specific signature?*

### Addendum: Example

The family of properties with the single member $\phi(x)$ = "x has exactly one neighbour" together with the number of vertices that share this property - 2 - fix $K_2$

### Addendum: More examples

Definitions:

- Let a
*d-neighbour of x*be a vertex*d*edges away from*x*. - Let $\phi_d^n$ stand for
*x has exactly n d-neighbours*. - Let $C_l^n$ be the graph consisting of
*n*cycles of lenght $l, l \geq 2$, $C_2^1 = K_2$. - Let $P_l$ be the path graph of length $l$.

### (1)

Consider the vertex transitive graphs $C_2^n$.

For each $C$ of them the one-element (vertex transitivity!) family of properties $\lbrace \phi_1^1 \rbrace$ is distinguishing w.r.t. $C$.

### (2)

Consider the vertex transitive graphs $C_l^1, l > 2$, $l$ prime or $l = 4$.

For each $C$ of them the one-element family of properties $\lbrace \phi_1^2 \rbrace$ is distinguishing w.r.t. $C$.

For $C = C_3^2$ (vertex transitive, too) $\lbrace \phi_1^2 \wedge \phi_2^0 \rbrace$ is distinguishing w.r.t. $C$.

For $C = C_6^1$ (vertex transitive, too) $\lbrace \phi_1^2 \wedge \phi_2^2 \rbrace$ is distinguishing w.r.t. $C$.

These examples seem to be easily expanded by combinatorical means.

### (3)

Consider the path graphs $P_l$ with $\lceil \frac{l}{2} \rceil$ conjugacy classes of vertices. Let $\psi_d$ stand for *x has a d-neighbour with degree 1*. Then

$\lbrace \phi_1^1 \rbrace\ \cup\ \lbrace \phi_1^2 \wedge \psi_k \rbrace_{k = 1,..,\lceil \frac{l}{2} \rceil - 1}$

is a distinguishing family of properties (not necessarily minimal).

for allgraphs: just because two vertices have exactly one neighbor does not mean they are conjugate. If you want $\phi$ to have this property only with respect to a fixed graph $G$, you need to say so. $\endgroup$ – Pete L. Clark Jan 5 '10 at 14:27