NAME

Graph::Maker::Johnson - create Johnson graphs

SYNOPSIS

use Graph::Maker::Johnson;
$graph = Graph::Maker->new ('Johnson', N => 8, K => 3);

DESCRIPTION

Graph::Maker::Johnson creates Graph.pm graphs of Johnson graphs. Each vertex is a K-many subset of the integers 1 to N. Edges are between vertices which have K-1 integers the same and 1 integer different. Vertex names are the list of K integers separated by commas, such as "1,5,6,8".

An N,K graph is the same as an N,N-K but different vertex names.

K=1 or K=N-1 is the complete-N graph. For K=1, the vertex names are the same as Graph::Maker::Complete (integers 1 to N).

K=2 or K=N-2 is the triangular graph, which is the line graph of the complete-N graph.

N=5,K=2, which is triangular-5, is the complement of the Petersen graph. The Petersen graph can be considered as the Kneser 5,2 which is edges between pairs of integers with both different, whereas here edges between one different. (Neither has edges for none different as that would be self-loops.)

FUNCTIONS

$graph = Graph::Maker->new('Johnson', key => value, ...)

The key/value parameters are

N  =>  integer
K  =>  integer
graph_maker => subr(key=>value) constructor, default Graph->new

Other parameters are passed to the constructor, either graph_maker or Graph->new().

If the graph is directed (the default) then edges are added both forward and backward between vertices. Option undirected => 1 creates an undirected graph and for it there is a single edge between vertices.

HOUSE OF GRAPHS

House of Graphs entries for the graphs here include

N=4, K=2, https://hog.grinvin.org/ViewGraphInfo.action?id=226

N=5, K=2, https://hog.grinvin.org/ViewGraphInfo.action?id=21154 (complement of Petersen)

SEE ALSO

Graph::Maker, Graph::Maker::Kneser, Graph::Maker::Petersen

HOME PAGE

http://user42.tuxfamily.org/graph-maker-other/index.html

LICENSE

Copyright 2015, 2016, 2017, 2018, 2019, 2020, 2021 Kevin Ryde

This file is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

This file is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with This file. If not, see http://www.gnu.org/licenses/.