Triangle-Replaced Graph


A triangle-replaced graph T(G) is a cubic graph in which each vertex is replaced by a triangle graph such that each vertex of the triangle is connected to one of the originally adjacent vertices of a graph G.

The triangle-replaced Coxeter graph appears as an exceptional graph in conjectures about nonhamiltonian vertex-transitive graphs, H-*-connected graphs, and Hamilton decompositions.

Bryant and Dean (2014) consider a generalization to a d-replaced graph, in which the vertices of a d-regular graph are replaced by copies of the complete graph K_d. Such graphs provide counterexamples to the conjecture that there are a finite number of connected vertex-transitive graphs that have no Hamilton decomposition. The smallest counterexample is given by the K_6-replaced graph obtained from the multigraph obtained from the cubical graph Q_3 by doubling its edges.

Special cases of triangle-replaced graphs are summarized in the following table.

See also

Coxeter Graph, H-*-Connected Graph, Hamilton Decomposition, Nonhamiltonian Vertex-Transitive Graph, Petersen Graph

Explore with Wolfram|Alpha


Bryant, D. and Dean, M. "Vertex-Transitive Graphs that have no Hamilton Decomposition." 25 Aug 2014.

Cite this as:

Weisstein, Eric W. "Triangle-Replaced Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications