All Questions
Tagged with enumerative-combinatorics graph-theory
11 questions with no upvoted or accepted answers
12
votes
0
answers
330
views
The number of labeled pairs of edge disjoint trees and related questions
I wonder what is known on the following:
1) What is the number $T_k(n)$ of $k$-tuples of (pairwise) edge-disjoint trees $(T_1,T_2,\dots, T_k)$ with $n$ labelled vertices?
2) (harder, it seems) What ...
- 24.7k
9
votes
0
answers
188
views
Cycles of length $2^n - 2$ in the De Bruijn graph
It is well known that the number of (cyclic) De Bruijn sequences is $2^{2^{n-1}-n}$. This number may also be interpreted as the number of cycles of length $2^n$ in the De Bruijn graph of order $n$.
...
- 82.6k
8
votes
0
answers
155
views
Partial order on graphs induced by homomorphism counts
For graphs $F$ and $G$, let $\hom(F,G)$ denote the number of homomorphisms (adjacency preserving maps) from $F$ to $G$. Define a relation $\le_{\hom}$ on (isomorphism classes of) graphs as $G \le_{\...
- 2,339
7
votes
0
answers
355
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 ...
- 1,414
4
votes
0
answers
69
views
An atlas for the enumeration of planar maps
The theory of planar map enumeration was started by Tutte and iniciated the theory of map enumeration when trying to solve the 4-colour theorem by enumerative arguments. Nowadays a wide diversity of ...
- 1,561
3
votes
0
answers
98
views
Number of planar bipartite graphs
How many planar bipartite graphs are there with $m$ vertices of one color and $n$ vertices of the other color?
How many non-isomorphic classes exist?
- 13.9k
2
votes
0
answers
92
views
Counting labelled graphs according to sets of size 3
In this question we are counting labelled simple graphs. No concept of isomorphism is involved.
Let $G(n,e,t)$ be the number of labelled simple graphs with $n$ vertices, $e$ edges, and $t$ sets of ...
- 37.7k
1
vote
0
answers
134
views
Counting unions of unlabelled connected graphs
My question can be stated as follows: let $X$ be a hereditary family of unlabelled graphs closed under disjoint unions. Suppose we know, for each $n$, the number $c_n$ of connected graphs in X on $n$ ...
- 183
1
vote
0
answers
681
views
Generate all connected non-isomorphic graphs of n vertices modulo local complementation?
I'd like to generate a list of all simple, connected, undirected graphs of $n$ vertices, modulo standard graph isomorphism, and modulo local complementation, which is the following operation: for a ...
- 91
1
vote
0
answers
164
views
What's the complexity of the one sink directed subgraph isomorphism problem?
I am considering trying a new approach for the subgraph isomorphism problem in my PhD, but it just seems to work well for digraphs of one sink. By working well I mean some promise of not having to ...
0
votes
0
answers
195
views
Paths in graphs as a vector space or matroid
If I have a simple graph $G$, and what to count the number of simple paths between two distinct vertices, can the paths be seen as independent sets of a vector space, or even somehow, a matroid? I ...
- 640