Linked Questions

25
votes
3answers
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 ...
2
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
2
votes
1answer
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 ...
16
votes
2answers
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 ...
0
votes
1answer
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 ...
3
votes
3answers
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 ...
4
votes
1answer
1k views

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 ...
1
vote
1answer
476 views

Upper bound for the strict partition on K summands

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 ...