GraphDiameter

✖

GraphDiameter[g]

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

✖

GraphDiameter[{vw,…}]

uses rules vw to specify the graph g.

Details and Options

The following options can be given:
EdgeWeight Automatic weight for each edge

Method Automatic method 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".
GraphDiameter works with undirected graphs, directed graphs, weighted graphs, multigraphs, and mixed graphs.

Examples

open allclose all

Basic Examples (1)Summary of the most common use cases

Give the graph diameter for a complete graph:

In[1]:=1

✖

https://wolfram.com/xid/05fvxus4fq-kl8j05

Out[1]=1

Scope (7)Survey of the scope of standard use cases

GraphDiameter works with undirected graphs:

In[1]:=1

✖

https://wolfram.com/xid/05fvxus4fq-dy6dt4

Out[1]=1

Directed graphs:

In[1]:=1

✖

https://wolfram.com/xid/05fvxus4fq-c4jban

Out[1]=1

Weighted graphs:

In[1]:=1

✖

https://wolfram.com/xid/05fvxus4fq-dc7o48

Out[1]=1

Multigraphs:

In[1]:=1

✖

https://wolfram.com/xid/05fvxus4fq-uvnf7h

Out[1]=1

Mixed graphs:

In[1]:=1

✖

https://wolfram.com/xid/05fvxus4fq-5geyu

Out[1]=1

Use rules to specify the graph:

In[1]:=1

✖

https://wolfram.com/xid/05fvxus4fq-bndh30

Out[1]=1

GraphDiameter works with large graphs:

In[1]:=1

✖

https://wolfram.com/xid/05fvxus4fq-cddhqp

In[2]:=2

✖

https://wolfram.com/xid/05fvxus4fq-l2vea2

Out[2]=2

Applications (2)Sample problems that can be solved with this function

Illustrate the diameter in two Petersen graphs:

In[3]:=3

✖

https://wolfram.com/xid/05fvxus4fq-hf6au8

In[4]:=4

✖

https://wolfram.com/xid/05fvxus4fq-begywe

Out[4]=4

For a CompleteGraph, the diameter is 1:

In[5]:=5

✖

https://wolfram.com/xid/05fvxus4fq-199oob

Out[5]=5

For a PathGraph of size , the diameter is :

In[6]:=6

✖

https://wolfram.com/xid/05fvxus4fq-nan2hv

Out[6]=6

For a CycleGraph of size , the diameter is :

In[7]:=7

✖

https://wolfram.com/xid/05fvxus4fq-xdcrj5

Out[7]=7

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

In[8]:=8

✖

https://wolfram.com/xid/05fvxus4fq-3nsp14

Out[8]=8

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

In[11]:=11

✖

https://wolfram.com/xid/05fvxus4fq-xyoniq

Out[11]=11

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

In[12]:=12

✖

https://wolfram.com/xid/05fvxus4fq-85xu8b

Out[12]=12

For a CompleteKaryTree tree of depth , the diameter is :

In[13]:=13

✖

https://wolfram.com/xid/05fvxus4fq-bwecfz

Out[13]=13

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

In[1]:=1

✖

https://wolfram.com/xid/05fvxus4fq-hc7ipt

Out[1]=1

In[2]:=2

✖

https://wolfram.com/xid/05fvxus4fq-d8i6l7

Out[2]=2

Properties & Relations (3)Properties of the function, and connections to other functions

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

In[1]:=1

✖

https://wolfram.com/xid/05fvxus4fq-b74jc

Out[1]=1

In[2]:=2

✖

https://wolfram.com/xid/05fvxus4fq-p1igzl

Out[2]=2

In[3]:=3

✖

https://wolfram.com/xid/05fvxus4fq-gihody

Out[3]=3

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

In[1]:=1

✖

https://wolfram.com/xid/05fvxus4fq-l8baf

Out[1]=1

In[2]:=2

✖

https://wolfram.com/xid/05fvxus4fq-42x2y

Out[2]=2

In[3]:=3

✖

https://wolfram.com/xid/05fvxus4fq-pa5v

Out[3]=3

The graph diameter is unchanged when reversing every edge:

In[1]:=1

✖

https://wolfram.com/xid/05fvxus4fq-6m9vb

In[2]:=2

✖

https://wolfram.com/xid/05fvxus4fq-elsv0u

Out[2]=2

In[3]:=3

✖

https://wolfram.com/xid/05fvxus4fq-cbztik

Out[3]=3

Top