Return to Question

###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$.

###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$.

###Definition 1###

###Question 2 (postponed)###

###Definition 2 (corrected)###

###Comment###

Distinguishing properties allow not only to distinguish between (equivalence classes of) vertices of a single graph but also to distinguish different graphs: the isomorphism class of a finite graph is fixed by a distinguishing family of properties plus the numbers of vertices for each distinguishing property $\phi_v(x)$ (my claim, maybe wrong?).

###Question 3 (edited)###

Does it seem feasible to compute a distinguishing family of properties from - let's say - the adjacency matrix? For some small and many highly symmetric graphs it can be done by hand, but what about bigger and more asymmetric graphs?

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

More examples may follow.

###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###

###Question 1 (postponed)###

###Definition 2 (third revision)###

###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 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?

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

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