All Questions
43 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
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
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
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
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
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
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
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
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
5
votes
2
answers
564
views
Orbits of independent sets of the hypercube
How does one enumerate the distinct orbit classes of independent sets of the hypercube modulo symmetries of the hypercubes?
The counting of the number of independent sets in an $n$-dimensional ...
- 171
19
votes
3
answers
2k
views
A generalization of the triangle counting problem for simple weighted graphs
One nice identity is that $$\operatorname{tr}(A^3)/6$$ counts the number of triangles of a graph with adjacency matrix $A$. It also implies that triangle counting in a graph can be performed in sub-...
- 3,463
23
votes
3
answers
3k
views
Proofs of parity results via the Handshaking lemma
I particularly like the following strategy to prove that the number of some combinatorial objects is even: to construct a graph, in which they correspond to vertices of odd degree (=valency).
Let me ...
10
votes
1
answer
7k
views
Counting non-isomorphic graphs with prescribed number of edges and vertices
I'd love your help with this question.
Let $n\geq3$ be a fixed integer. How many non-isomorphic graphs with $p$ vertices and $q$ edges are there where $p+q=n$?
Thank you very much.
Crossposted at ...
- 101
14
votes
5
answers
4k
views
Are there more connected or disconnected graphs on $n$ vertices?
Suppose we are talking about graphs with $n$ labeled vertices. Which graphs are more common: connected or disconnected?
- 1,765
7
votes
4
answers
11k
views
Non-isomorphic graphs of given order.
It is well discussed in many graph theory texts that it is somewhat hard to distinguish non-isomorphic graphs with large order. But as to the construction of all the non-isomorphic graphs of any given ...
- 2,855