Janko-Kharaghani-Tonchev Graph

Author

Eric W. Weisstein
March 16, 2021

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/Janko-Kharaghani-TonchevGraph.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/Janko-Kharaghani-TonchevGraph.html.

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

Source

Zvonimir Janko, Hadi Kharaghani, and Vladimir D. Tonchev. The existence of a Bush-type Hadamard matrix of order 324 and two new infinite classes of symmetric designs. Des. Codes Cryptogr. 24(2):225–232, 2001. doi:10.1023/A:1011212922844

Embeddings

<<MathWorld`Graphs`

Names

GraphData["JankoKharaghaniGraph936","StandardName"]

GraphData["JankoKharaghaniGraph936","StandardNames"]

Primary

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

All

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

Inexact

Select[GraphData["JankoKharaghaniGraph936","Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData["JankoKharaghaniGraph936","EdgeList"]]

Default embedding

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

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

RecognizeGraph[g]

Degenerate

GraphData["JankoKharaghaniGraph936","Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData["JankoKharaghaniGraph936","Graph","Degenerate"]

Perspective

GraphData["JankoKharaghaniGraph936","Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData["JankoKharaghaniGraph936","Polyhedron"]

Bilateral

GraphData["JankoKharaghaniGraph936","Graph","Bilateral"]//StyleGraphs

Circular

GraphData["JankoKharaghaniGraph936","Graph","Circular"]//StyleGraphs

Planar

GraphData["JankoKharaghaniGraph936","Planar"]

GraphData["JankoKharaghaniGraph936","Graph","Planar"]//StyleGraphs

MinimalCrossing

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

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

MinimalCrossing construction

(cn=CrossingNumber[GraphData["JankoKharaghaniGraph936"],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData["JankoKharaghaniGraph936"],TimeConstraint->10])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData["JankoKharaghaniGraph936"],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData["JankoKharaghaniGraph936"],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData["JankoKharaghaniGraph936","V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData["JankoKharaghaniGraph936"],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["JankoKharaghaniGraph936","Circulant"]

GraphData["JankoKharaghaniGraph936","Graph","Circulant"]//StyleGraphs

Complement graph

GraphData["JankoKharaghaniGraph936","ComplementGraph","Name"]

Line graph

GraphData["JankoKharaghaniGraph936","Line"]

LineGraphQ[GraphData["JankoKharaghaniGraph936"]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== "JankoKharaghaniGraph936"&]

RootGraph[GraphData["JankoKharaghaniGraph936"]]

Halin

GraphData["JankoKharaghaniGraph936","Halin"]

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

Rigid

GraphData["JankoKharaghaniGraph936","Rigid"]

GraphData["JankoKharaghaniGraph936","Graph","Rigid"]//StyleGraphs

Flexible

GraphData["JankoKharaghaniGraph936","Flexible"]

GraphData["JankoKharaghaniGraph936","Graph","Flexible"]//StyleGraphs

LCF

GraphData["JankoKharaghaniGraph936","LCF"]

GraphData["JankoKharaghaniGraph936","HamiltonianCycleCount"]

GraphData["JankoKharaghaniGraph936","LCFSignature"]

GraphData["JankoKharaghaniGraph936","LCFNotations"]

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

Tally[LCFNotation[#][[2]]&/@%]

LCF compute random

FindRandomLCFNotation[GraphData["JankoKharaghaniGraph936"],TimeConstraint->120]

FindRandomLCFNotation[GraphData["JankoKharaghaniGraph936"],TimeConstraint->3600]

LCF compute 10^2

Tally[(lcf=LCF[GraphData["JankoKharaghaniGraph936"],10^2])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

LCF compute 10^3

Tally[(lcf=LCF[GraphData["JankoKharaghaniGraph936"],10^3])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2])]//Timing

Length[gs]

gs

LCF compute 10^4

Tally[(lcf=LCF[GraphData["JankoKharaghaniGraph936"],10^4])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

LCF compute all

Divisors[GraphData["JankoKharaghaniGraph936","V"]]

Length[FindHamiltonianCycle[GraphData["JankoKharaghaniGraph936"],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData["JankoKharaghaniGraph936"],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName["JankoKharaghaniGraph936",".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

i=0;
gs={};
t0=AbsoluteTime[];
count=Length[order2];
Monitor[
Do[
If[!MissingQ[g=BilateralLCFGraph[LCFGraph@@order2[[i]]]],AppendTo[gs,g]],
{i,count}
],
Column[{
ProgressIndicator[i,{1,count}],
Row[{i,"/",count}],
Row[{"estimated time remaining: ",Round[(AbsoluteTime[]-t0) (count/i-1)]," s"}],
Row[{Length[gs]," bilateral graphs"}]
}]
];//Timing

UnitDistance

GraphData["JankoKharaghaniGraph936","UnitDistance"]

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

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

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData["JankoKharaghaniGraph936","VertexList"],GraphData["JankoKharaghaniGraph936","EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData["JankoKharaghaniGraph936","Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData["JankoKharaghaniGraph936"],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData["JankoKharaghaniGraph936","Matchstick"]

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

3D default

Graph3D[GraphData["JankoKharaghaniGraph936","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["JankoKharaghaniGraph936","Polyhedral"]

GraphData["JankoKharaghaniGraph936","Graph",{"3D","Polyhedron"}]

Construction

Sage

https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_generators.html#sage.graphs.graph_generators.GraphGenerators.JankoKharaghaniTonchevGraph

g=SageGraph[SageEvaluate["graphs.JankoKharaghaniTonchevGraph().edges()"]]

Through[{VertexCount,EdgeCount}[g]]

RegularParameters[g]

RecognizeGraph[g]

VertexCount[g]

GraphData

GraphDataClassString

GraphDataClassString[g]

GraphDataString

file=OpenAppend["~/new.m"]

WriteString[file,GraphDataString[g,
"StandardName"->"JankoKharaghaniTonchevGraph",
"Name"->"JankoK\[Hyphen]Kharaghani\[Hyphen]Tonchev graph",
"Information"->"Janko-Kharaghani-TonchevGraph",
"Embeddings"->{},
"Skip"->{"Arboricity","BurningNumber","Chord","ChordlessCycle","ChordlessCycles","Chords","ChromaticNumber","CliqueCoveringNumber","ComplementOddChordlessCycle","ComplementOddChordlessCycles","ConnectedInducedSubgraphPolynomial","ConnectedInducedSubgraphs","CrossingNumber","Cycles","CyclePolynomial","DominatingSet","DominatingSets","EdgeCovers","GracefulLabeling","GracefulLabelings","HamiltonianCycles","HamiltonianPaths","HamiltonianWalks","IdiosyncraticPolynomial","IndependentVertexSets","LongestCycles","MatchingGeneratingPolynomial","MaximalIndependentEdgeSets","MaximalIndependentVertexSets","MaximallyNonhamiltonian","MaximumFlowMatrix","MaximumIndependentEdgeSets","MinimumCoveringsByMaximalCliques","MinimumEdgeColoring","MinimumVertexColoring","MinimumVertexCut","MinimumVertexCuts","MinimumWeightFractionalColoring","MinimumWeightFractionalEdgeColoring","OddChordlessCycles","PathPolynomial","Paths","RadioLabeling","RadioLabelings","RadioNumber","RectilinearCrossingCount","ResistanceMatrix","Skewness","StronglyPerfect","UnitDistance","VertexCover","Thickness"},
TimeConstraint->10
]]

Close[file]