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

Wolfram Language & System Documentation Center

VertexTransitiveGraphQ

VertexTransitiveGraphQ

VertexTransitiveGraphQ[g]

yields True if the graph g is a vertex–transitive graph and False otherwise.

Details

A graph g is vertex transitive if for any vertices v and w of g, there is an automorphism of g that maps v to w.
VertexTransitiveGraphQ is typically used to test whether all vertices in a graph have identical neighborhoods.

Examples

open all close all

Basic Examples (2)

Test whether a graph is vertex transitive:

Wolfram Language code: PetersenGraph[]

Wolfram Language code: VertexTransitiveGraphQ[%]

A star graph is not vertex transitive:

Wolfram Language code: StarGraph[5]

Wolfram Language code: VertexTransitiveGraphQ[%]

Scope (7)

Test undirected graphs:

Wolfram Language code: VertexTransitiveGraphQ[[image]]

Directed graphs:

Wolfram Language code: VertexTransitiveGraphQ[[image]]

Multigraphs:

Wolfram Language code: VertexTransitiveGraphQ[[image]]

Mixed graphs:

Wolfram Language code: VertexTransitiveGraphQ[[image]]

Tagged graphs:

Wolfram Language code: VertexTransitiveGraphQ[[image]]

VertexTransitiveGraphQ gives False for anything that is not a vertex–transitive graph:

Wolfram Language code: VertexTransitiveGraphQ[a]

VertexTransitiveGraphQ works with large graphs:

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

Wolfram Language code: VertexTransitiveGraphQ[%]//Timing

Applications (1)

Generate a list of vertex–transitive graphs from GraphData:

Wolfram Language code: GraphData["VertexTransitive"]//Short

Check:

Wolfram Language code: VertexTransitiveGraphQ[GraphData[#]] & /@ Take[%, 5]

Properties & Relations (7)

Every vertex–transitive graph is regular:

Wolfram Language code: g = GraphData[{"Antiprism", 6}]

Wolfram Language code: VertexTransitiveGraphQ[g]

Wolfram Language code: VertexDegree[g]

The graph complement of a vertex–transitive graph is vertex transitive:

Wolfram Language code: g = CycleGraph[4]

Wolfram Language code: VertexTransitiveGraphQ[g]

Wolfram Language code: VertexTransitiveGraphQ[GraphComplement[g]]

Use GraphAutomorphismGroup to test whether a graph is vertex transitive:

Wolfram Language code: g = [image];

Wolfram Language code: VertexTransitiveGraphQ[g]

Find the automorphism group:

Wolfram Language code: group = GraphAutomorphismGroup[g];

Compute the orbit of a permutation group:

Wolfram Language code: GroupOrbits[group, PermutationSupport[group]]

Single orbit should permute all vertices:

Wolfram Language code: (Length[%] == 1) && (Length[First[%]] == VertexCount[g])

Use VertexTransitiveGraphQ to test whether a connected graph is edge transitive:

Wolfram Language code: g = GraphData[{"Arrangement", {5, 2}}]

Wolfram Language code: VertexTransitiveGraphQ[LineGraph[g]]

Wolfram Language code: EdgeTransitiveGraphQ[g]

The edge connectivity of a vertex-transitive graph is equal to the degree :

Wolfram Language code: g = [image];

Wolfram Language code: VertexTransitiveGraphQ[g]

Wolfram Language code: EdgeConnectivity[g] == VertexDegree[g, 1]

The vertex connectivity of a vertex-transitive graph will be at least :

Wolfram Language code: g = [image];

Wolfram Language code: VertexTransitiveGraphQ[g]

Wolfram Language code: VertexConnectivity[g] ≥ 2(VertexDegree[g, 1] + 1) / 3

The vertex-transitive graph includes CompleteGraph:

Wolfram Language code: Table[CompleteGraph[n], {n, 3, 6}]

Wolfram Language code: VertexTransitiveGraphQ /@ %

Wolfram Language code: Table[CycleGraph[n], {n, 3, 6}]

Wolfram Language code: VertexTransitiveGraphQ /@ %

Wolfram Language code: PetersenGraph[5, 3]

Wolfram Language code: VertexTransitiveGraphQ[%]

Heawood graph:

Wolfram Language code: GraphData["HeawoodGraph"]

Wolfram Language code: VertexTransitiveGraphQ[%]

Top