Enumeration of point-determining graphs (Q618313): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q247078 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Roland Bacher / rank | |||
Normal rank |
Revision as of 01:50, 12 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Enumeration of point-determining graphs |
scientific article |
Statements
Enumeration of point-determining graphs (English)
0 references
14 January 2011
0 references
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_-\)).
0 references
graphical enumeration
0 references
point-determining
0 references
combinatorial species
0 references
graphs without endpoints
0 references
superimposition of graphs
0 references