5
votes
2answers
205 views

Number of unlabelled planar graphs

What are the best known bounds on the number of non-isomorphic (unlabelled) planar graphs on $n$ vertices? Is there a simple proof that this number is at most exponential in $n$?
1
vote
2answers
361 views

Enumeration of labeled connected bipartite graphs given partite sets

What would be the closed-form expression defining number of all possible labelled connected bipartite graphs given $\mid X \mid = m, \mid Y \mid = n - m $?
5
votes
0answers
124 views

How does the number of self-avoiding paths between two points scale, in a square/cubic lattice?

Consider two different infinite graphs, whose vertices are drawn from $\mathbb Z^2$ or $\mathbb Z^3$. Let $P_d : \mathbb Z^d \times \mathbb N \to \mathbb N$ for $d \in \{2,3\}$ be the function such ...
12
votes
5answers
881 views

Is the following invariant of rooted trees a complete invariant?

Recall that rooted trees may be generated by starting with a trivial rooted tree (just a vertex), along with the operations of grafting a number of trees (identify their roots) and adding a new vertex ...