GraphDiameter

GraphDiameter[g]

gives the greatest distance between any pair of vertices in the graph g.

GraphDiameter[{vw,}]

uses rules vw to specify the graph g.

Details and Options

  • The following options can be given:
  • EdgeWeightAutomaticweight for each edge
    MethodAutomaticmethod to use
  • With the default setting EdgeWeight->Automatic, the edge weight of an edge is taken to be the EdgeWeight of the graph g if available; otherwise, it is 1.
  • Possible Method settings include "Dijkstra", "FloydWarshall", "Johnson", and "PseudoDiameter".

Examples

open allclose all

Basic Examples  (1)

Give the graph diameter for a complete graph:

Scope  (7)

GraphDiameter works with undirected graphs:

Directed graphs:

Weighted graphs:

Multigraphs:

Mixed graphs:

Use rules to specify the graph:

GraphDiameter works with large graphs:

Applications  (2)

Illustrate the diameter in two Petersen graphs:

For a CompleteGraph, the diameter is 1:

For a PathGraph of size , the diameter is :

For a CycleGraph of size , the diameter is TemplateBox[{{n, /, 2}}, Floor]:

For a WheelGraph of size 5 or more, the diameter is 2:

A WheelGraph of size 4 is a complete graph, so the diameter is 1:

For a GridGraph of size {m,n}, the diameter is :

For a CompleteKaryTree tree of depth , the diameter is :

Find the largest number of steps separating two people at a family gathering network:

Properties & Relations  (3)

For a connected graph, the diameter can be computed by VertexEccentricity:

If a simple graph has diameter greater than 3, then its complement has diameter less than 3:

The graph diameter is unchanged when reversing every edge:

Introduced in 2010
 (8.0)
 |
Updated in 2015
 (10.3)