Graph::Maker::Kneser - create Kneser graphs
use Graph::Maker::Kneser; $graph = Graph::Maker->new ('Kneser', N => 8, K => 3);
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
$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
If the graph is directed (the default) then edges are added both forward and backward between vertices. Option
undirected => 1creates an undirected graph and for it there is a single edge between vertices.
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=3, https://hog.grinvin.org/ViewGraphInfo.action?id=19271
Copyright 2015, 2016, 2017 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/.