Enable JavaScript to interact with content and submit forms on Wolfram websites. Learn how

Wolfram Language & System Documentation Center

GraphPeriphery

GraphPeriphery

GraphPeriphery[g]

gives vertices that are maximally distant to at least one vertex in the graph g.

GraphPeriphery[{vw,…}]

uses rules vw to specify the graph g.

Details and Options

GraphPeriphery is also known as peripheral vertices.

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

Examples

open all close all

Basic Examples (1)

Give the graph periphery for a graph:

Wolfram Language code: g = WheelGraph[6];

Wolfram Language code: GraphPeriphery[g]

Highlight the graph periphery:

Wolfram Language code: HighlightGraph[g, %, VertexSize -> Small]

Scope (7)

GraphPeriphery works with undirected graphs:

Wolfram Language code: GraphPeriphery[[image]]

Directed graphs:

Wolfram Language code: GraphPeriphery[[image]]

Weighted graphs:

Wolfram Language code: GraphPeriphery[[image]]

Multigraphs:

Wolfram Language code: GraphPeriphery[[image]]

Mixed graphs:

Wolfram Language code: GraphPeriphery[[image]]

Use rules to specify the graph:

Wolfram Language code: GraphPeriphery[{1 -> 2, 2 -> 3, 3 -> 1, 3 -> 4, 4 -> 5, 5 -> 3}]

GraphPeriphery works with large graphs:

Wolfram Language code: g = GridGraph[{10, 10, 10, 10}];

Wolfram Language code: GraphPeriphery[g]//Length//Timing

Applications (1)

Find the people who are least related to everybody at a family gathering network:

Wolfram Language code: g = ExampleData[{"NetworkGraph", "FamilyGathering"}];

Wolfram Language code: GraphPeriphery[g]

Wolfram Language code: HighlightGraph[g, %]

Properties & Relations (8)

In a connected graph, the periphery can be found using VertexEccentricity:

Wolfram Language code: g = GridGraph[{3, 4}]

Wolfram Language code: VertexEccentricity[g, #]& /@ VertexList[g]

Wolfram Language code: Flatten[Position[%, Max[%]]]

Wolfram Language code: GraphPeriphery[g]

Undirected connected graphs have at least two vertices on the periphery:

Wolfram Language code: Select[RandomGraph[BernoulliGraphDistribution[7, 0.6], 9], ConnectedGraphQ]

Wolfram Language code: Length[GraphPeriphery[#]]& /@ %

Wolfram Language code: And@@Thread[% ≥ 2]

For a CompleteGraph, the periphery includes all vertices:

Wolfram Language code: HighlightGraph[#, GraphPeriphery[#]]& /@ Table[CompleteGraph[n, VertexSize -> Small], {n, 3, 6}]

For a PathGraph with positive weights, the periphery consists of the endpoints:

Wolfram Language code: HighlightGraph[#, GraphPeriphery[#]]& /@ Table[PathGraph[Range[n], VertexSize -> Large], {n, 5, 8}]

With non-negative weights, the periphery forms two paths ending at the respective endpoints:

Wolfram Language code: HighlightGraph[#, GraphPeriphery[#]]&[PathGraph[Range[8], VertexSize -> Large, EdgeWeight -> {0, 1, 1, 0, 1, 0, 0}]]

For a CycleGraph, all vertices are at the periphery:

Wolfram Language code: HighlightGraph[#, GraphPeriphery[#]]& /@ Table[CycleGraph[n, VertexSize -> Small], {n, 3, 6}]

For a WheelGraph of size 5 or more, all vertices but the hub are at the periphery:

Wolfram Language code: HighlightGraph[#, GraphPeriphery[#]]& /@ Table[WheelGraph[n, VertexSize -> Small], {n, 5, 8}]

For a GridGraph, the periphery consists of the vertices at the corners:

Wolfram Language code:

HighlightGraph[#, GraphPeriphery[#]]& /@ Table[GridGraph[dim, VertexSize -> Small, ImageSize -> {Tiny, Tiny}], {dim, {{3, 3}, {3, 4}, {4, 3}, {4, 4}}}]

For a CompleteKaryTree, the periphery consists of the leaves:

Wolfram Language code: HighlightGraph[#, GraphPeriphery[#]]& /@ Table[CompleteKaryTree[n, VertexSize -> Large], {n, 3, 5}]

Top