All Questions
Tagged with enumerative-combinatorics graph-theory
59 questions
4
votes
1
answer
207
views
Minimum number of possible proper colorings
Properly colored graph (edge has color) means that any two adjacent edges have distinct colors.
For any graph with $2k-2$ edges such that it can be properly colored using $k$ colors. What is the ...
- 91
6
votes
3
answers
526
views
Enumerating all inequivalent planar embeddings of a planar graph
Graph $G$ can be embedded (or has an embedding) in the space if $G$ can be drawn in the space if $G$ can be drawn in such a way that no two edges cross except at an end-vertex in common. A Graph $G$ ...
- 1,851
2
votes
1
answer
482
views
Counting $n$-edge directed graphs
I would like to count the $n$-edge directed graphs. The graphs might contain self-loops (edges connecting a vertex to itself) and multiple edges (multiple edges connecting the same pair of vertices). ...
- 21
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
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
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
2
votes
2
answers
126
views
Regular pseudographs
Is there a counting known for $3$-regular (or any $n$-regular) pseudo graph of a given order $|V|$? An asymptotic result for connected (or disconnected) graphs is good enough. It would be even better ...
- 397
1
vote
1
answer
261
views
Number of maximal independent sets in a hypergraph
Are there any known upper bounds on the number of maximal independent sets in a hypergraph? I'm aware that simple graphs have an upper bound of $O(3^{n/3})$. How about on the number of independent ...
- 135
1
vote
2
answers
1k
views
Is there a formula for the number of st-dags (DAG with 1 source and 1 sink) with n vertices?
I am looking at doing some basic validation on a database of st-dags. It would be useful to have:
A formula for the number of non-isomorphic st-dags with n vertices
A formula for the same with n ...
- 21
11
votes
2
answers
1k
views
How many finitely-generated-by-elements-of-finite-order-groups are there?
I do not know where this question is on the trivial to intractable spectrum.
Consider the set of isomorphism classes of groups finitely generated by elements of finite order. What is the cardinality ...
- 1,027
3
votes
2
answers
439
views
Efficiently generating all regular/bidegreed graphs
There is a related question on how to generate all regular graphs; however, the procedure is random and repeats the generated graphs. Plus, there is no stop condition, unless recording the total ...
- 131
2
votes
1
answer
226
views
Enumeration of connected, bridgeless, trivalent graphs
Is it known how many connected, bridgeless, trivalent graphs there are on $2n$ vertices?
I am allowing the graph to have multiple edges, but no self edges (though I think the fact that the graph is ...
- 421
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
0
votes
1
answer
182
views
Relationship between cycle length, number of chords, and number of induced $P_{4}$ subgraphs of the cycle
I was wondering if there was a known relationship between the length of cycle, the number of chords of the cycle, and the number of induced $P_{4}$ subgraphs of the cycle.
Here, I am referring to ...
- 1
1
vote
1
answer
248
views
mapping integers to k-ary trees
Is there an algorithmic way to map the natural numbers to unique k-ary trees?
I am familiar with the work of Tychonievich who created a mapping from integers to binary trees. https://www.cs.virginia....
- 113
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
1
vote
1
answer
60
views
Rank and edges in a combinatorial graph?
Fix a $d\in\mathbb N$ and consider the matrix $M\in\{0,1\}^{2^d\times d}$ of all $0/1$ vectors of length $d$. Consider the matrix $G\in\{0,1\}^{n\times n}$ whose $ij$ the entry is $0$ if inner product ...
- 13.9k
0
votes
1
answer
84
views
Primage structures: induced domain partitioning by itterated inverse (reference request)
I am studying the list of inverse images (preimage sets) of some function $f$ at a given inverse depth $j$ -- for each element $x_i$ of a finite domain $X$.
For example, the j-th such preimage list ...
- 23
6
votes
3
answers
437
views
Eigenvalues of the Laplacian of the directed De Bruijn graph
We will denote by $DB(n,k)$ the directed De Bruijn graph, which is a digraph whose vertices are elements of $\{0,1,\dots,k-1\}^n$, and $\sigma_1\cdots \sigma_n$ is connected to $\tau_1\cdots \tau_{n}$ ...
4
votes
1
answer
752
views
Graph isomorphism by invariants
Graph isomorphism is known to be a difficult computational problem. The problem get even worst if we want to find non-isomorphic graphs in a large family of graphs.
Let us call a (numerical) ...
- 1,651
8
votes
2
answers
2k
views
The number of Dyck paths of length $2n$ and height exactly $k$
In A080936 gives the number of Dyck paths of length $2n$ and height exactly $k$ and has a little more information on the generating functions.
For all $n\geq 1$ and $\frac{(n+1)}{2}\leq k\leq n$ we ...
- 355
5
votes
1
answer
320
views
Applications of De-Bruijn Sequences in "Pure Mathematics"
I know of a few applications of De-Bruijn Sequences and De Bruijn Graphs in combinatorics, applied mathematics, Engineering and computer science. But I have only found one application of De Bruijn ...
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
1
answer
1k
views
An explicit formula for the number of different (non isomorphic) simple graphs with $p$ vertices and $q$ edges
I would like to know if there is an explicit formula for the number of different (non isomorphic) simple graphs with a given number of vertices $p$ and edges $q$, and if yes what is it.
Trying to ...
- 29
5
votes
2
answers
376
views
What upper bounds are known on the number of non-isomorphic cycle matroids?
For $n\in\mathbb{N}^{+}$, let $c_{n}$ denote the number of simple non-isomorphic cycle matroids of graphs on $n$ vertices. That is, let
$$A(n)=\{M(G)\;;\;G\text{ is a graph on }n\text{ vertices}\},$$
...
- 153
14
votes
2
answers
481
views
Number of matchings of even cycles
By doing some calculations on the generating function of matching polynomials of cycles I made the following interesting observation:
For all positive integers $n>1$ and $k <n $, the number of ...
- 4,484
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
3
votes
1
answer
232
views
Counting cycle vertex covers on hypercube
Let $Q_n$ be the $n$-dimensional hypercube graph. How many vertex cycle covers exist on $Q_n$? (Presumably the best we can hope for are upper and lower bounds.) To be clear, a single "vertex cycle ...
- 3,979
4
votes
1
answer
312
views
A Geometric Combinatorial/Graph Theory Question
I have a combinatorics problem that seems pretty general - I'd be surprised if the answer is not known. Unfortunately, I can't seem to solve it.
The question concerns the following situation: ...
- 439
5
votes
1
answer
246
views
Are there graphs whose matching polynomials are Legendre?
It is well-known (at least well-known enough to be on Wikipedia) that there are quite simple graphs whose matching polynomials
$$M(G;x) = \sum_{m\geq 0} (-1)^m \#\{\text{matchings with $m$ edges}\}\,...
- 205
5
votes
1
answer
286
views
Number of bipartite graphs with a neighborhood property
Consider a bipartite graph of order $2n$ with equal bipartitions $C_1$ and $C_2$, where, $$C_i = \{v_{i,1}, v_{i,2}, v_{i,3} \dots v_{i,n}\}; i = 1, 2.$$
Given two vertices $v_{i,p}$ and $v_{i,q}$, $...
- 363
3
votes
1
answer
408
views
Counting graphs according to recursion depth
Consider the set $S$ of multigraphs defined recursively as follows:
Example Graph Class
A graph $G$ is in $S$ if(f)
$G$ is a loop on a single vertex, or
$G$ may be obtained by ...
- 151
3
votes
1
answer
693
views
Size of automorphism group of random regular graph
If I pick a random regular graph on $n$-vertices and degree $d$ from uniform distribution what is the probability that its automorphism group is of size at least $m$?
--
I want to know what is the ...
- 13.9k
1
vote
1
answer
126
views
Counting bounded genus non-isomorphic graphs
What is the number of non-isomorphic $2n$ vertex balanced bipartite graphs of degree at most $d$ and genus $g$?
I am most interested in $d\leq3$ and $g=0$.
user76479
7
votes
2
answers
480
views
Are all numbers from $1$ to $n!$ the number of perfect matchings of some bipartite graph?
Let $f(G)$ give the number of perfect matchings of a graph $G$.
Consider set $\mathcal N_{2n}=\{0,1,2,\dots,n!-1,n!\}$.
Consider collection of all $2n$ vertex balanced bipartite graph to be $\...
- 13.9k
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
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 ...
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
5
votes
1
answer
171
views
Determining the number of hamiltonian paths of $K_n-C_n$
I would like to know information regarding the function $h(n)$ where $h(n)$ is the number of hamiltonian cycles the graph $K_n$ has after removing the edges that make up a hamiltonian cycle of $K_n$. ...
- 1,835
8
votes
1
answer
383
views
Number of median graphs?
What is the number of $n$-vertex median graphs? These graphs generalize hypercubes and trees, and have many applications. It seems unlikely that a closed form expression is known, so I would also be ...
- 2,350
5
votes
1
answer
650
views
Counting Problems where Labeled is Known but Unlabeled is Not
Cayley's formula states that the number of labeled trees on $n$ vertices is $n^{n-2}$. There are many nice proofs of this compact formula.
To contrast, counting unlabeled trees is considerably harder....
- 51
7
votes
2
answers
448
views
What is the number of noncrossing acyclic digraphs?
A noncrossing graph on $n$ vertices is a graph drawn on $n$ points numbered from $1$ to $n$ in counter-clockwise order on a circle such that the edges lie entirely within the circle and do not cross ...
- 195
9
votes
3
answers
1k
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$?
- 195
4
votes
2
answers
748
views
Estimate size of graph by taking random walks
Let $G$ be a connected, finite graph and let $v_0$ be a vertex of $G$. I'm interested in methods of estimating the number of vertices in $G$, based on local exploration only. What I have in mind is:
...
- 523
2
votes
2
answers
772
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 $?
- 43
6
votes
1
answer
748
views
Enumeration of graphs with a given and bounded degree sequence
What is the best known asymptotic formula for the number of graphs with a given degree sequence $(d_1, ... ,d_n)$, when the degrees are bounded by a constant and the number of vertices $n$ goes to ...
- 1,633
6
votes
2
answers
7k
views
How many perfect matchings in a regular bipartite graph?
We have a $d$-regular bipartite graph $G = (X,Y,E)$ with $|X| = |Y| = n$ and $|E| = nd$.
What is an upper bound on the number of perfect matchings of $G$?
- 61
1
vote
1
answer
592
views
Enumerating unlabeled trees with degree at most 3
Does anyone know if there is currently any research or any potential bounds on the number of trees on $n$ vertices with degree at most $3$? One can bound this above by $C_{n}$ the $n$th Catalan number,...
- 143
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
11
votes
5
answers
2k
views
Is it possible to have t triangles in some graph on n vertices?
Fix $n>4$. Is there a characterization of the set $T_n$ of all natural numbers $t$ such that there is some graph on $n$ vertices with exactly $t$ distinct triangles? For example, it's clear that {$...
- 1,068