Triangle-Replaced Graph

Author

Eric W. Weisstein
May 20, 2022

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/Triangle-ReplacedGraph.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/Triangle-ReplacedGraph.html.

©2022 Wolfram Research, Inc. except for portions noted otherwise

Images

K6Replaced

tr=Select[GraphData[All],Or@@StringMatchQ[Cases[GraphData[#,"StandardNames"],_String],"K6Replaced*"]&]

tr0=SortBy[GraphData["K6Replaced*"],GraphData[#,"V"]&]

GraphicsRow[Show[GraphData[#,"Image"],PlotLabel->TextCell[GraphData[#,"Name"],PageWidth->100,TextAlignment->Center],BaseStyle->{FontFamily->"Times",FontSlant->Italic}]&/@tr/._AbsolutePointSize:>AbsolutePointSize[2.5],Spacings->-50,ImageSize->400]

TetrahedronReplaced

tr=Select[GraphData[All],Or@@StringMatchQ[Cases[GraphData[#,"StandardNames"],_String],"TetrahedronReplaced*"]&]

tr0=SortBy[GraphData["TetrahedronReplaced*"],GraphData[#,"V"]&]

GraphicsRow[Show[GraphData[#,"Image"],PlotLabel->TextCell[GraphData[#,"Name"],PageWidth->100,TextAlignment->Center],BaseStyle->{FontFamily->"Times",FontSlant->Italic}]&/@tr/._AbsolutePointSize:>AbsolutePointSize[2.5],Spacings->-50,ImageSize->400]

TriangleReplaced

tr=Select[GraphData[All],Or@@StringMatchQ[Cases[GraphData[#,"StandardNames"],_String],"TriangleReplaced*"]&]

tr0=SortBy[GraphData["TriangleReplaced*"],GraphData[#,"V"]&]

GraphicsRow[Show[GraphData[#,"Image"],PlotLabel->TextCell[GraphData[#,"Name"],PageWidth->100,TextAlignment->Center],BaseStyle->{FontFamily->"Times",FontSlant->Italic}]&/@tr/._AbsolutePointSize:>AbsolutePointSize[2.5],Spacings->-50,ImageSize->400]

Examples

"K6ReplacedDoubledMoebiusKantorGraph"

NO HD.  (But it is Ham-conn)

TwoMK=EdgeDuplicatedGraph[GraphData["MoebiusKantorGraph"],2]

g=CompleteReplacedRegularGraph[TwoMK]

K6ReplacedDoubledMoebiusKantorGraph=g;

VertexCount[g]

VertexDegree[g]//Union

RecognizeGraph[%]

"K18ReplacedSextupledCubicalGraph"

NO HD.  (But it is Ham-conn)

SixQ3=EdgeDuplicatedGraph[GraphData["Q3"],6]

g=CompleteReplacedRegularGraph[SixQ3]

K18ReplacedSextupledCubicalGraph=g;

VertexCount[g]

VertexDegree[g]//Union

RecognizeGraph[%]

"K6ReplacedDoubledCubicalGraph"

NO HD.  (But it is Ham-conn)

TwoQ3=EdgeDuplicatedGraph[GraphData["Q3"],2]

g=CompleteReplacedRegularGraph[TwoQ3]

IsomorphicGraphQ[g,GraphData["K6ReplacedDoubledCubicalGraph"]]

VertexDegree[g]

RecognizeGraph[%]

K6ReplacedDoubledCubicalGraph=System`Graph[{{1,2},{1,3},{1,4},{1,5},{1,6},{1,7},{2,3},{2,4},{2,5},{2,6},{2,13},{3,4},{3,5},{3,6},{3,25},{4,5},{4,6},{4,10},{5,6},{5,16},{6,28},{7,8},{7,9},{7,10},{7,11},{7,12},{8,9},{8,10},{8,11},{8,12},{8,19},{9,10},{9,11},{9,12},{9,31},{10,11},{10,12},{11,12},{11,22},{12,34},{13,14},{13,15},{13,16},{13,17},{13,18},{14,15},{14,16},{14,17},{14,18},{14,20},{15,16},{15,17},{15,18},{15,37},{16,17},{16,18},{17,18},{17,23},{18,40},{19,20},{19,21},{19,22},{19,23},{19,24},{20,21},{20,22},{20,23},{20,24},{21,22},{21,23},{21,24},{21,43},{22,23},{22,24},{23,24},{24,46},{25,26},{25,27},{25,28},{25,29},{25,30},{26,27},{26,28},{26,29},{26,30},{26,32},{27,28},{27,29},{27,30},{27,38},{28,29},{28,30},{29,30},{29,35},{30,41},{31,32},{31,33},{31,34},{31,35},{31,36},{32,33},{32,34},{32,35},{32,36},{33,34},{33,35},{33,36},{33,44},{34,35},{34,36},{35,36},{36,47},{37,38},{37,39},{37,40},{37,41},{37,42},{38,39},{38,40},{38,41},{38,42},{39,40},{39,41},{39,42},{39,45},{40,41},{40,42},{41,42},{42,48},{43,44},{43,45},{43,46},{43,47},{43,48},{44,45},{44,46},{44,47},{44,48},{45,46},{45,47},{45,48},{46,47},{46,48},{47,48}}]

VertexDegree[K6ReplacedDoubledCubicalGraph]//Union

IsomorphicGraphQ[g2,K6ReplacedDoubledCubicalGraph]

"PentatopeReplacedIcosahedralGraph"

CompleteReplacedRegularGraph[GraphData["IcosahedralGraph"]]//RecognizeGraph

CompleteReplacedRegularGraph[GraphData["IcosahedralGraph"]]//VertexCount

CompleteReplacedRegularGraph[GraphData["IcosahedralGraph"],.2,Normalize->#]&/@{True,False}

"TetrahedronReplacedCoxeterLineGraph"

GraphData["TetrahedronReplacedCoxeterLineGraph"]

“HamiltonDecomposable” = False

“HamiltonConnected” = True

"Class1” = True

TetrahedronReplacedCoxeterLineGraph=System`Graph[UndirectedEdge@@@{{1,2},{1,3},{1,4},{1,5},{2,3},{2,4},{2,9},{3,4},{3,13},{4,17},{5,6},{5,7},{5,8},{6,7},{6,8},{6,10},{7,8},{7,97},{8,105},{9,10},{9,11},{9,12},{10,11},{10,12},{11,12},{11,129},{12,161},{13,14},{13,15},{13,16},{14,15},{14,16},{14,18},{15,16},{15,21},{16,25},{17,18},{17,19},{17,20},{18,19},{18,20},{19,20},{19,53},{20,61},{21,22},{21,23},{21,24},{22,23},{22,24},{22,26},{23,24},{23,29},{24,33},{25,26},{25,27},{25,28},{26,27},{26,28},{27,28},{27,85},{28,137},{29,30},{29,31},{29,32},{30,31},{30,32},{30,34},{31,32},{31,37},{32,41},{33,34},{33,35},{33,36},{34,35},{34,36},{35,36},{35,113},{36,153},{37,38},{37,39},{37,40},{38,39},{38,40},{38,42},{39,40},{39,45},{40,49},{41,42},{41,43},{41,44},{42,43},{42,44},{43,44},{43,93},{44,165},{45,46},{45,47},{45,48},{46,47},{46,48},{46,50},{47,48},{47,54},{48,57},{49,50},{49,51},{49,52},{50,51},{50,52},{51,52},{51,117},{52,121},{53,54},{53,55},{53,56},{54,55},{54,56},{55,56},{55,58},{56,62},{57,58},{57,59},{57,60},{58,59},{58,60},{59,60},{59,101},{60,145},{61,62},{61,63},{61,64},{62,63},{62,64},{63,64},{63,65},{64,69},{65,66},{65,67},{65,68},{66,67},{66,68},{66,70},{67,68},{67,73},{68,77},{69,70},{69,71},{69,72},{70,71},{70,72},{71,72},{71,149},{72,157},{73,74},{73,75},{73,76},{74,75},{74,76},{74,78},{75,76},{75,81},{76,86},{77,78},{77,79},{77,80},{78,79},{78,80},{79,80},{79,109},{80,118},{81,82},{81,83},{81,84},{82,83},{82,84},{82,87},{83,84},{83,89},{84,94},{85,86},{85,87},{85,88},{86,87},{86,88},{87,88},{88,138},{89,90},{89,91},{89,92},{90,91},{90,92},{90,95},{91,92},{91,98},{92,102},{93,94},{93,95},{93,96},{94,95},{94,96},{95,96},{96,166},{97,98},{97,99},{97,100},{98,99},{98,100},{99,100},{99,103},{100,106},{101,102},{101,103},{101,104},{102,103},{102,104},{103,104},{104,146},{105,106},{105,107},{105,108},{106,107},{106,108},{107,108},{107,110},{108,114},{109,110},{109,111},{109,112},{110,111},{110,112},{111,112},{111,115},{112,119},{113,114},{113,115},{113,116},{114,115},{114,116},{115,116},{116,154},{117,118},{117,119},{117,120},{118,119},{118,120},{119,120},{120,122},{121,122},{121,123},{121,124},{122,123},{122,124},{123,124},{123,125},{124,130},{125,126},{125,127},{125,128},{126,127},{126,128},{126,131},{127,128},{127,133},{128,139},{129,130},{129,131},{129,132},{130,131},{130,132},{131,132},{132,162},{133,134},{133,135},{133,136},{134,135},{134,136},{134,140},{135,136},{135,141},{136,147},{137,138},{137,139},{137,140},{138,139},{138,140},{139,140},{141,142},{141,143},{141,144},{142,143},{142,144},{142,148},{143,144},{143,150},{144,155},{145,146},{145,147},{145,148},{146,147},{146,148},{147,148},{149,150},{149,151},{149,152},{150,151},{150,152},{151,152},{151,156},{152,158},{153,154},{153,155},{153,156},{154,155},{154,156},{155,156},{157,158},{157,159},{157,160},{158,159},{158,160},{159,160},{159,163},{160,167},{161,162},{161,163},{161,164},{162,163},{162,164},{163,164},{164,168},{165,166},{165,167},{165,168},{166,167},{166,168},{167,168}}]

CompleteReplacedRegularGraph[GraphData["CoxeterLineGraph"]]//RecognizeGraph

CompleteReplacedRegularGraph[GraphData["CoxeterLineGraph"]]//ToEntity

CompleteReplacedRegularGraph[GraphData["CoxeterLineGraph"]]//VertexCount

CompleteReplacedRegularGraph[GraphData["CoxeterLineGraph"],.2,Normalize->#]&/@{True,False}

"TetrahedronReplacedOctahedralGraph"

CompleteReplacedRegularGraph[GraphData["OctahedralGraph"]]//RecognizeGraph

CompleteReplacedRegularGraph[GraphData["OctahedralGraph"]]//ToEntity

CompleteReplacedRegularGraph[GraphData["OctahedralGraph"]]//VertexCount

CompleteReplacedRegularGraph[GraphData["OctahedralGraph"],.2,Normalize->#]&/@{True,False}

"TriangleReplacedCoxeterGraph"

GraphData["TriangleReplacedCoxeterGraph","StandardName"]

All

GraphData["TriangleReplacedCoxeterGraph","Graph","All"]//StyleGraphs

Halin

GraphData["TriangleReplacedCoxeterGraph","Graph","Halin"]//StyleGraphs

LCF

GraphData["TriangleReplacedCoxeterGraph","LCFSignature"]

GraphData["TriangleReplacedCoxeterGraph","Graph","LCF"]//StyleGraphs

UnitDistance

GraphData["TriangleReplacedCoxeterGraph","UnitDistance"]

UnitDistanceGraphQ[GraphData["TriangleReplacedCoxeterGraph"],Debug->True]//Timing

GraphData["TriangleReplacedCoxeterGraph","Graph","UnitDistance"]//StyleGraphs

Select[%,!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&]

Select[UnitDistanceEmbeddingRefine/@Complement@@(GraphData["TriangleReplacedCoxeterGraph","Graph",#]&/@{"All","UnitDistance"}),UnitDistanceGraphEmbeddingQ]

FindUnitDistanceEmbedding[GraphData["TriangleReplacedCoxeterGraph"],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

UnitDistance FindSubgraphUnitDistanceEmbedding

{"TriangleReplacedCoxeterGraph",l=FindSubgraphUnitDistanceEmbedding[GraphData["TriangleReplacedCoxeterGraph"],TimeConstraint->300,"Results"->All]//Timing}

gs=UniqueEmbeddings[l]

Matchstick

GraphData["TriangleReplacedCoxeterGraph","Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData["TriangleReplacedCoxeterGraph",{"RCN","CN"}]

GraphData["TriangleReplacedCoxeterGraph","Graph","MinimalCrossing"]//StyleGraphs

Default embedding

GraphPlot@GraphData["TriangleReplacedCoxeterGraph","Edges"]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

MinimalCrossing construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData["TriangleReplacedCoxeterGraph"],"CrossingNumber"->12]]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData["TriangleReplacedCoxeterGraph","Edges"]]

3D All

GraphData["TriangleReplacedCoxeterGraph","Graph",{"3D","All"}]

3D UnitDistance

GraphData["TriangleReplacedCoxeterGraph","Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData["TriangleReplacedCoxeterGraph","Polyhedron"]

"TriangleReplacedCubicalGraph" == "TruncatedCubicalGraph"

CompleteReplacedRegularGraph[GraphData["Q3"]]//RecognizeGraph

CompleteReplacedRegularGraph[GraphData["Q3"]]//VertexCount

CompleteReplacedRegularGraph[GraphData["Q3"],.2,Normalize->#]&/@{True,False}

GetGraphData["TruncatedCubicalGraph","File"]

"TriangleReplacedDodecahedralGraph" == "TruncatedDodecahedralGraph"

CompleteReplacedRegularGraph[GraphData["DodecahedralGraph"]]//RecognizeGraph

CompleteReplacedRegularGraph[GraphData["DodecahedralGraph"]]//VertexCount

CompleteReplacedRegularGraph[GraphData["DodecahedralGraph"],.2,Normalize->#]&/@{True,False}

"TriangleReplacedPetersenGraph"

Primary

GraphData["TriangleReplacedPetersenGraph"]//StyleGraphs[#,ImageSize->Small]&

All

GraphData["TriangleReplacedPetersenGraph","Graph","All"]//StyleGraphs

GraphData["TriangleReplacedPetersenGraph","EmbeddingClasses"]

Read and Wilson

Read and Wilson construction

g=Graph[Range[30],UndirectedEdge@@@{{1,2},{1,3},{1,4},{2,3},{2,14},{3,5},{4,6},{4,7},{5,8},{5,11},{6,7},{6,25},{7,9},{8,11},{8,17},{9,10},{9,12},{10,12},{10,13},{11,21},{12,23},{13,15},{13,18},{14,16},{14,19},{15,16},{15,18},{16,19},{17,20},{17,22},{18,20},{19,29},{20,22},{21,23},{21,26},{22,24},{23,26},{24,25},{24,27},{25,27},{26,28},{27,30},{28,29},{28,30},{29,30}},VertexCoordinates->(10^(-4)){{6738,-7820},{7472,-5560},{9061,-7326},{9664,-16832},{10889,-7920},{11586,-18229},{11834,-15865},{12478,-9686},{12963,-14310},{13212,-11946},{13212,-7426},{15133,-13343},{15133,-6029},{15133,10},{16321,-3971},{16321,-2048},{17508,-13343},{17508,-6029},{17508,10},{19429,-11946},{19429,-7426},{19678,-14310},{20163,-9686},{20807,-15865},{21055,-18229},{21753,-7920},{22977,-16832},{23580,-7326},{25169,-5560},{25903,-7820}}]

RecognizeGraph@g

UnitDistance

GraphData["TriangleReplacedPetersenGraph","Graph","UnitDistance"]//StyleGraphs

From Ed via bug(344468) Dec 20, 2017

GraphData[gn="TriangleReplacedPetersenGraph",{"V","M"}]

GraphData[gn,"VertexDegrees"]

Length[all=Flatten[RootReduce[Table[#.RotationMatrix[2 Pi n/5],{n,0,4}]&/@{{0,Root[9-15 #1^2+5 #1^4&,3]},{0,Root[-1+5 #1-10 #1^3+5 #1^4&,3]},{0,Root[-1-5 #1+10 #1^3+5 #1^4&,3]},{Root[21141-92340 #1^2+41040 #1^4+43200 #1^6+6400 #1^8&,3],Root[-9-126 #1-84 #1^2+24 #1^3+16 #1^4&,2]},{Root[261-9720 #1^2+86640 #1^4+48000 #1^6+6400 #1^8&,1],Root[1-56 #1+36 #1^2+64 #1^3+16 #1^4&,4]},{Root[261+180 #1^2-3360 #1^4+6400 #1^8&,2],Root[1+14 #1-24 #1^2-16 #1^3+16 #1^4&,4]}}],1]]

Length[lineall=Select[Subsets[all,{2}],Chop[N[EuclideanDistance@@#-1]]==0&]/.Thread[all->Range[Length[all]]]]

GraphData[gn,"VT"]

g1=System`Graph[Range[Length[all]],UndirectedEdge@@@lineall,VertexCoordinates->all,VertexLabels->"Name"]

VertexDegree[g1]

extra=Position[%,4]//Flatten

g2=HighlightGraph[g1,extra]

g3=EdgeDelete[g1,UndirectedEdge@@@{{16,29},{17,30},{18,26},{19,27},{20,28},
{5,6},{1,7},{2,8},{3,9},{4,10}}];
extra=Flatten[Position[VertexDegree[g3],4]];
g4=HighlightGraph[g3,extra]

RecognizeGraph[g3]

dist=EuclideanDistance@@@(List@@@EdgeList[g3]/.i_Integer:>GraphEmbedding[g3][[i]]);

Do[Print[{i,RootReduce[dist[[i]]]//Timing}],{i,Length[dist]}]

RootReduce[dist]//Union//Timing

ByteCount[GraphEmbedding[g3]]

l={{gn,{0,Append[GraphData[gn,"Embeddings"],ToCommonEdges[g3,GraphData[gn]]]}}}

PropertyReplace[l,"Embeddings","11.3"]

RenameGraphFiles[]

l={{gn,{0,Append[GraphData[gn,"EmbeddingClasses"],{"Integral","MinimalIntegral","UnitDistance"}]}}}

PropertyReplace[l,"EmbeddingClasses","11.3"]

RenameGraphFiles[]

Construction

CompleteReplacedRegularGraph[GraphData["PetersenGraph"]]//RecognizeGraph

CompleteReplacedRegularGraph[GraphData["PetersenGraph"],.2,Normalize->#]&/@{True,False}

CompleteReplacedRegularGraph[GraphData["PetersenGraph"],.3,Normalize->#]&/@{True,False}

"TriangleReplacedTetrahedralGraph" == "TruncatedTetrahedralGraph"

CompleteReplacedRegularGraph[GraphData["TetrahedralGraph"]]//RecognizeGraph

CompleteReplacedRegularGraph[GraphData["TetrahedralGraph"]]//VertexCount

CompleteReplacedRegularGraph[GraphData["TetrahedralGraph"],.2,Normalize->#]&/@{True,False}

GraphData

GraphDataString

K6ReplacedDoubledCubicalGraph

file=OpenWrite["~/K6ReplacedDoubledCubicalGraph.m"]

WriteString[file,GraphDataString[K6ReplacedDoubledCubicalGraph,
"StandardName"->"K6ReplacedDoubledCubicalGraph",
"Name"->"K6\[Hyphen]replaced doubled cubical graph",
"Information"->"Triangle-ReplacedGraph",
"Embeddings"->None,
"Skip"->{"ChromaticPolynomial","TuttePolynomial"},
"Classes"->{"HamiltonConnected","NonhamiltonDecomposable"},
Debug->True,
TimeConstraint->100
]]//Timing//AbsoluteTiming

Close[file]

K6ReplacedDoubledMoebiusKantorGraph

file=OpenWrite["~/K6ReplacedDoubledMoebiusKantorGraph.m"]

WriteString[file,GraphDataString[K6ReplacedDoubledMoebiusKantorGraph,
"StandardName"->"K6ReplacedDoubledMoebiusKantorGraph",
"Name"->"K6\[Hyphen]replaced doubled Möbius\[Hyphen]Kantor graph",
"Information"->"Triangle-ReplacedGraph",
"Embeddings"->None,
"Skip"->{"ChromaticPolynomial","TuttePolynomial"},
"Classes"->{"HamiltonConnected","NonhamiltonDecomposable"},
Debug->True,
TimeConstraint->100
]]//Timing//AbsoluteTiming

Close[file]

K18ReplacedSextupledCubicalGraph

file=OpenWrite["~/K18ReplacedSextupledCubicalGraph.m"]

WriteString[file,GraphDataString[K18ReplacedSextupledCubicalGraph,
"StandardName"->"K18ReplacedSextupledCubicalGraph",
"Name"->"K18\[Hyphen]replaced sextupled cubical graph",
"Information"->"Triangle-ReplacedGraph",
"Embeddings"->None,
"Skip"->{"ChromaticPolynomial","TuttePolynomial"},
"Classes"->{"HamiltonConnected","NonhamiltonDecomposable"},
Debug->True,
TimeConstraint->100
]]//Timing//AbsoluteTiming

Close[file]