TOPICS

# Triangle-Replaced Graph

A triangle-replaced graph 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 .

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 -replaced graph, in which the vertices of a -regular graph are replaced by copies of the complete graph . 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 -replaced graph obtained from the multigraph obtained from the cubical graph by doubling its edges.

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

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

## Explore with Wolfram|Alpha

More things to try:

## References

Bryant, D. and Dean, M. "Vertex-Transitive Graphs that have no Hamilton Decomposition." 25 Aug 2014. http://arxiv.org/abs/1408.5211.

## Cite this as:

Weisstein, Eric W. "Triangle-Replaced Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Triangle-ReplacedGraph.html