Egawa Graph

Author

Eric W. Weisstein
April 16, 2021

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/EgawaGraph.nb.

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

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

Source

Yoshimi Egawa, Characterization of H(n, q) by the parameters, Journal of Combinatorial Theory, Series A, Volume 31, Issue 2, 1981, Pages 108-125, ISSN 0097-3165,:doi:
10.1016/0097−3165(81)90007−8
10.1016. (http://www.sciencedirect.com/science/article/pii/0097316581900078)

Graphs

GraphData["Egawa"]

gs=Sort[{Lookup[GraphData[#,"NotationRules"],"Egawa"],#}&/@GraphData["Egawa"]]

DeleteCases[Show[GraphData[#2],PlotLabel->GraphData[#2,"Name"]]&@@@gs,_Show]

Special cases

With[{class="Egawa"},TextGrid[Sort[{Lookup[GraphData[#,"NotationRules"],class],GraphData[#,"V"],#}&/@GraphData[class]],Dividers->All,Alignment->{{Left,Decimal,Left}}]]

Properties

VertexCount

Function[{gn,p,s},{gn,GraphData[gn,"V"],(4^(2p+s))}]@@@({#,Sequence@@Lookup[GraphData[#,"NotationRules"],"Egawa"]}&/@GraphData["Egawa"])

DeleteCases[%,{_,x_,x_}]

Construction

Sage

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

Vertex count:

TextGrid[Flatten[Table[{p,s,(16^p)4^s},{p,0,4},{s,0,4}],1],Dividers->All]

inds=Sort[{p,s}/.{ToRules[Reduce[(16^p)4^s≤1024&&p≥0&&s≥0,{p,s},Integers,"Backsubstitution"->True]]}]

data=Function[{p,s},{
{p,s},
TimeConstrained[SageGraph[SageEvaluate["graphs.EgawaGraph("<>ToString[p]<>","<>ToString[s]<>").edges()"]],10]
}]@@@inds

TextGrid[{#,VertexCount[#2],RecognizeGraph[#2]}&@@@data,Dividers->All,Alignment->{{{Decimal},Left}}]

GraphDataString

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

Function[{k,r},WriteString[file,GraphDataString[SageGraph[SageEvaluate["graphs.EgawaGraph(2,0).edges()"]],
"StandardName"->{"Egawa",{2,0}},
"Name"->"(2,0)\[Hyphen]Egawa graph",
"Information"->"EgawaGraph",
"Embeddings"->{},
"Skip"->{"Arboricity","Chord","Chords","ChromaticNumber","ConnectedInducedSubgraphPolynomial","ConnectedInducedSubgraphs","Cycles","CyclePolynomial","CycleSignature","DominatingSet","DominatingSets","EdgeChromaticNumber","EdgeCovers","GracefulLabeling","GracefulLabelings","HamiltonianCycles","HamiltonianPaths","HamiltonianWalks","IdiosyncraticPolynomial","IndependentVertexSets","LongestCycles","MatchingGeneratingPolynomial","MaximalIndependentEdgeSets","MaximalIndependentVertexSets","MaximallyNonhamiltonian","MaximumIndependentEdgeSets","MinimumCoveringsByMaximalCliques","MinimumEdgeColoring","MinimumVertexColoring","MinimumVertexCut","MinimumVertexCuts","MinimumWeightFractionalColoring","MinimumWeightFractionalEdgeColoring","ComplementOddChordlessCycle","ComplementOddChordlessCycles","PathPolynomial","RadioLabeling","RadioLabelings","Skewness","VertexCover"},
TimeConstraint->10
]]]@@@{{5,11}};

Close[file]