What is the diameter of a graph with just one node?

Question

I'm trying to find an answer to a problem in my Distributed Algorithms course, and to do so I want to get something clarified.

1. What is the diameter of a graph with one node, with an edge to itself? Is it 1 or 0?

If you are interested, the question to which I'm trying to find an answer is this:

In terms of n (# nodes), the number of messages (= diam * |E|) used in the FloodMax algorithm is easily seen to be O(n^3). Produce a class of digraphs in which the product (diam * |E|) really is Omega(n^3).

The digraph I came up with is a graph with just one node, which has a directed edge to itself. That way |E| would be 1 which is n^2, and if the diam is 1, it satisfies the second condition where diam = 1 = n as well. So it gives me a class of digraphs with message complexity being Omega(n^3).

So am I correct in my thinking, that in such a graph the diameter is 1?

Answer 1

Two things:

1. It seems to be 0 according to this, which says:

   In other words, a graph's diameter is the largest number of vertices which must be traversed in order to travel from one vertex to another when paths which backtrack, detour, or loop are excluded from consideration.

2. Your solution to the given problem should describe how to build a graph (or rather say what type of known graph has that property, since it says "produce a class") with n nodes, not a graph with however many nodes you manually figured out a solution for. I can do the same for 2 nodes:

   1 -- 2
   
   |E| = 1 = (1/4)*2^2 = (1/4)*n^2 = O(n^2)
   diam = 1 = 2 - 1 = n - 1 = O(n)
   tada!
   

   Or here's how we can make your solution work even if the diameter is 0: 0 = 1 - 1 = n - 1 = O(n) => your solution still works!

   So even if you considered paths with loops as well, I would still deem your solution incorrect.

Answer 2

O(n^3) and Omega(n^3) do not mean cn^3, and there is no problem with a function that is 0 at finitely many nonzero values of n being in O(n^3) and Omega(n^3). For example, n^3-100 is in both, as is n^3-100n^2. For the purposes of asymptotics, it is unimportant what the diameter is for a single example. You are asked to find an infinite family of graphs with large enough diameters, and a single example of a graph doesn't affect the asymptotics of the infinite family.

That said, the diameter of a graph (or strongly connected digraph) can be defined in a few ways. One possibility is the greatest value of half of the minimum of the length of a round trip from v to w and back over all pairs v and w, and that is 0 when v and w coincide. So, the diameter of a graph with one vertex is 0.

Again, this doesn't help at all with the exercise that you have, to construct an infinite family. A family with one node and lots of edges back to itself isn't going to cut it. Think of how you might add many edges to graphs with large diameter, such as an n-cycle or path, without decreasing the diameter that much.