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.
See also
Coxeter Graph, H-*-Connected Graph, Hamilton Decomposition, Nonhamiltonian Vertex-Transitive Graph, Petersen Graph
Explore with Wolfram|Alpha
References
Bryant, D. and Dean, M. "Vertex-Transitive Graphs that have no Hamilton Decomposition." 25 Aug 2014. http://arxiv.org/abs/1408.5211.
Referenced on Wolfram|Alpha
Cite this as:
Weisstein, Eric W. "Triangle-Replaced Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Triangle-ReplacedGraph.html