graph theory - Conjugate vertices and distinguishing properties

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).