NAME

Graph::Maker::Kneser - create Kneser graphs

SYNOPSIS

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

DESCRIPTION

Graph::Maker::Kneser creates Graph.pm graphs of Kneser graphs. Each vertex is a K-many subset of the integers 1 to N. Edges are between vertices with all integers distinct. Vertex names are the list of integers separated by commas, such as "1,5,6,8".

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

N=5,K=2 is the Petersen graph.

N=2*K-1 is the "odd" graph K.

K > N/2 has no edges since the K-many subsets are each more than half of 1..N so are never disjoint

FUNCTIONS

$graph = Graph::Maker->new('Kneser', 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=484

N=5, K=2, https://hog.grinvin.org/ViewGraphInfo.action?id=660 (Petersen, odd 3)

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

SEE ALSO

Graph::Maker, Graph::Maker::Johnson

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/.