Subgraphs and Similarity of Vertices

Abstract

When $G$ and $F$ are graphs, $v\in V(G)$ and $\phi$ is an orbit of $V(F)$ under the action of the automorphism group of $F$, $s(F,G,v,\phi )$ denotes the number of induced subgraphs of $G$ isomorphic to $F$ such that $v$ lies in orbit $\theta$ of $F$. Vertices $v\in V(G)$ and $w\in V(H)$ are called $k$-vertex subgraph equivalent ($k$-SE), $2\le k<n=|V(G)|$, if for each graph $F$ with $k$ vertices and for every orbit $\phi$ of $F$, $s(F,G,v,\phi )=s(F,H,w,\phi )$, and they are called similar if there is an isomorphism from $G$ to $H$ taking $v$ to $w$. We prove that $k$-SE vertices are $(k-1)$-SE and several parameters of $(n-1)$-SE vertices are equal. It is also proved that in many situations, “(n-1)-SE between vertices is equivalent to their similarity'' and it is true always if and only if Ulam's Graph Reconstruction Conjecture is true.