Enumeration of point-determining graphs (Q618313): Difference between revisions

A simple unoriented graph is point-determining (respectively co-point-determining) if for every pair \(\{u,v\}\) of non-adjacent (respectively adjacent) vertices there exists a third vertex \(w\) adjacent to exactly one of the two vertices \(u,v\). A graph is bi-point-determining if it is both point-determining and co-point-determining. The set of bi-point-determining (respectively point-determining, co-point-determining) graphs is exactly the set of graphs having no transpositions (respectively no transpositions involving non-adjacent, adjacent vertices) in their automorphism group. Reduction of arbitrary (connected) to (connected) point-determining, co-point-determining or bi-point-determining graphs leads the authors to equations for the series encoding enumerative properties of the corresponding species. The authors study also the case of (connected) point-determining graphs which are bicoloured (i.e., bipartite together with a choice of black vertices among \(V_+\), \(V_-\) in every connected component with vertex-bipartition \(V_+\cup V_-\)).