10 questions linked to/from Counting multigraphs up to isomorphism
11k views

Why there are $11$ non-isomorphic graphs of order $4$?

I'm new to graph theory and I don't plan to become a serious student of graph theory either. My book suggests that there are $11$ non-isomorphic graphs of order $4$, but I can't see why. I know that ...
73 views

Find a generating function for unlabeled graphs

Let's take a graph(undirected) of $m$ edges and $3$ vertices. Now I want to derive a polynomial for which the coefficient of $x^m$ denotes the number of unlabeled graphs of $m$ edges. How to derive ...
167 views

Counting number of simple graphs with 'n' unlabelled vertices.

I am aware that the number of simple graphs possible with $n$ labelled vertices is $2^{n(n-1)/2}$. Is there any closed formula for the same problem with $n$ unlabelled vertices? In case of unlabelled ...
106 views

How many different non-isomorphic random graphs of the Erdős–Rényi model exist?

The Erdős–Rényi model $G(n,m)$ gives a random graph on n vertecies with m edges. I'm interested in the number of possible graphs, that can be generated that way. If you ignore isomorphism, there are ...
269 views

How many different graphs of order $n$ are there?

I'm interested in all four combinations: directed and undirected, cyclic and acyclic. I'm having trouble calculating how big the complexity gets as you add more nodes to a graph. Clearly, the number ...
1k views

How many 2-edge-colourings of $K_n$ are there?

I'm writing a paper on Ramsey Theory and it would be interesting and useful to know the number of essentially different 2-edge-colourings of $K_n$ there are. By that I mean the number of essentially ...
111 views

Nodes and edges with combinatorics!

Given N number of nodes how many different configurations are possible (with nodes not being labelled i.e. all nodes are identical) with the condition that there is no isolated node. That is not the ...
1k views

Number of distinct connected digraphs with 4 vertices and 6 edges

I have been looking at graphs representing how people or things can move between states (vertices). Each directional move from one vertex directly to another is an edge, and each vertex must be ...
Finding only the number of unlabeled graphs on $n$ vertices
I know that it is possible to find the number of unlabelled graphs on $n$ vertices using Polya's theorem, but you get a horrible sum. This also tells you much more: it gives you the number of ...
In number theory and combinatorics, a partition of a positive integer $n$, also called an integer partition, is a way of writing $n$ as a sum of positive integers. Partitions into distinct parts are ...