Subgraphs and Similarity of Vertices

S. Ramachandran1, P. Bhanumathy2
1Noorul Islam University Kumarakovil-629180 NAGERCOIL, INDIA
2APMD/VSSC THIRUVANANTHAPURAM-22 INDIA

Abstract

When \(G\) and \(F\) are graphs, \(v \in V(G)\) and \(\varphi\) is an orbit of \(V(F)\) under the action of the automorphism group of \(F\), \(s(F,G,v,\varphi)\) 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 \leq k < n = |V(G)|\), if for each graph \(F\) with \(k\) vertices and for every orbit \(\varphi\) of \(F\), \(s(F,G,v,\varphi) = s(F,H,w,\varphi)\), 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.