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

Wolfram Language & System Documentation Center

EdgeTransitiveGraphQ

EdgeTransitiveGraphQ

EdgeTransitiveGraphQ[g]

yields True if the graph g is a edge-transitive graph and False otherwise.

Details

A graph g is edge transitive if for any edges e₁ and e₂ of g, there is an automorphism of g that maps e₁ to e₂.
EdgeTransitiveGraphQ is typically used to test whether all edges in a graph have identical neighborhoods.

Examples

open all close all

Basic Examples (2)

Test whether a graph is edge transitive:

Wolfram Language code: CompleteGraph[3]

Wolfram Language code: EdgeTransitiveGraphQ[%]

A wheel graph is not edge transitive:

Wolfram Language code: WheelGraph[5]

Wolfram Language code: EdgeTransitiveGraphQ[%]

Scope (7)

Test undirected graphs:

Wolfram Language code: EdgeTransitiveGraphQ[[image]]

Directed graphs:

Wolfram Language code: EdgeTransitiveGraphQ[[image]]

Multigraphs:

Wolfram Language code: EdgeTransitiveGraphQ[[image]]

Mixed graphs:

Wolfram Language code: EdgeTransitiveGraphQ[[image]]

Tagged graphs:

Wolfram Language code: EdgeTransitiveGraphQ[[image]]

EdgeTransitiveGraphQ gives False for anything that is not an edge-transitive graph:

Wolfram Language code: EdgeTransitiveGraphQ[a]

EdgeTransitiveGraphQ works with large graphs:

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

Wolfram Language code: EdgeTransitiveGraphQ[%]//Timing

Applications (1)

Generate a list of edge-transitive graphs from GraphData:

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

Check:

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

Properties & Relations (5)

Connected edge-transitive graphs are either vertex transitive or bipartite:

Wolfram Language code:

data = Intersection[GraphData["EdgeTransitive"], GraphData["Connected"]];
graphs = GraphData[#] & /@ Take[data, {6, 11}]

Wolfram Language code: (VertexTransitiveGraphQ[#] || BipartiteGraphQ[#])& /@ graphs

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-transitive graphs need not be vertex transitive:

Wolfram Language code: g = GraphData["GrayGraph"]

Wolfram Language code: EdgeTransitiveGraphQ[g]

Wolfram Language code: VertexTransitiveGraphQ[g]

The vertex connectivity of an edge-transitive graph equals its minimum degree:

Wolfram Language code: g = [image];

Wolfram Language code: EdgeTransitiveGraphQ[g]

Wolfram Language code: VertexConnectivity[g] == Min[VertexDegree[g]]

The edge-transitive graph includes CompleteGraph:

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

Wolfram Language code: EdgeTransitiveGraphQ /@ %

Complete bipartite graph:

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

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

Wolfram Language code: EdgeTransitiveGraphQ /@ %

Gray graph:

Wolfram Language code: GraphData["GrayGraph"]

Wolfram Language code: EdgeTransitiveGraphQ[%]

Top