Conjugate vertices and distinguishing properties

Question

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:

1. Let a d-neighbour of x be a vertex d edges away from x.
2. Let $\phi_d^n$ stand for x has exactly n d-neighbours.
3. Let $C_l^n$ be the graph consisting of n cycles of lenght $l, l \geq 2$, $C_2^1 = K_2$.
4. 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).

Answer 1

If you allow equality then it is trivial that every graph has a distinguishing famil of properties. Since you are considering the property "$v$ has exactly one neighbor", I think you are including equality...

Indeed, let $G$ be a graph, let $v_1,\dots,v_n$ be its vertices, and let me construct a 'distinguishing property' $\phi$ for $v_1$: put $\phi=(\exists x_2,x_2,\dots,x_n)\Phi(v_1,x_2,\dots,x_n)$ with $\Phi(x_1,\dots,x_n)$ being the formula which says that all its arguments are distinct and that the $i$th and $j$th arguments are $\sim$-related iff the vertices $v_i$ and $v_j$ are connected in the graph $G$.

Using formulas constructed like this, I think you can answer your (main?) question.