Wolfram Research

J(8,4,4) Generalized Johnson Graph

The Second DIMACS Implementation Challenge: 1992-1993

Originator: Panos Pardalos

NP Hard Problems: Maximum Clique, Graph Coloring, and Satisfiability, The Second DIMACS Implementation Challenge: 1992-1993.

A Johnson graph with parameters n, w, d has a node for every binary vector of length n with exactly w 1s. Two vertices are adjacent if and only if their hamming distance is at least d.

(496 vertices, 107880 edges)

Examples

Basic Examples

Retrieve the graph:

In[1]:=
ResourceData["J(8,4,4) Generalized Johnson Graph"]
Out[1]=

Summary properties:

In[2]:=
ResourceData["J(8,4,4) Generalized Johnson Graph", All]["Summary"]
Out[2]=

Basic Applications

Show the properties of the graph:

In[3]:=
g = ResourceData["J(8,4,4) Generalized Johnson Graph"];
In[4]:=
Dataset[<|# -> #[g]|> & /@ {GraphDiameter, GraphDensity, MeanGraphDistance, GraphLinkEfficiency}]
Out[4]=

Wolfram Research, "J(8,4,4) Generalized Johnson Graph" from the Wolfram Data Repository (2019) 

Data Resource History

Source Metadata

Data Downloads

Publisher Information