Graph::Maker::Beineke - create Beineke non-line graphs
use Graph::Maker::Beineke; $graph = Graph::Maker->new ('Beineke', G => 9);
Graph::Maker::Beineke
creates Graph.pm
graphs of the 9 graphs given by Beineke
Lowell W. Beineke, "Characterizations of Derived Graphs", Journal of Combinatorial Theory, volume 9, 1970, pages 129-135. http://www.sciencedirect.com/science/article/pii/S0021980070800199
Beineke shows that line graphs can be characterized as all graphs which do not contain as induced sub-graphs any of these 9 graphs.
G1 2 G2 2----+ G3 +----2-----+ \ / \ | | / \ | 3--1 3---1 5 | 3---1---5 / \ / | | \ / | 4 4----+ +----4-----+ G1 = claw G3 = K5-e = star-4 complete 5 less one edge G4 2----6 G5 +----2----+ G6 +----2----+--+ / \ | / \ | | / \ | | 3---1 | 3---1 5--6 | 3---1 5--6 \ / | \ / | | \ / | | 4----5 +----4----+ +----4----+--+ G7 2----6 G8 2 G9 2----6 / \ | / \ / \ / | 3---1 | 3---1--5--6 3---1 | \ / | \ / | | \ / \ | 4----5 4----+--+ 4----5 G9 = wheel-6
G1 is the claw (star-4) and is created using Graph::Maker::Star. G9 is the wheel-6 and is created using Graph::Maker::Wheel. The drawing for G8 means edges 4-to-5 and 4-to-6. Similarly in G6 2-to-5 and 2-to-6. Beineke draws G8 as squares
G8 2---3 | / | 1---4 | / | 5---6
The vertex numbering is slightly arbitrary but attempts some similarity between the graphs, including having the outer vertices numbered around in the style of the wheel-6 which is G9
These graphs are just a fixed set of 9 but are a convenient way to have some or all.
$graph = Graph::Maker->new('Beineke', key => value, ...)
The key/value parameters are
G => integer 1 to 9 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 entries for the graphs here are
And also
Graph::Maker, Graph::Maker::Star, Graph::Maker::Wheel
http://user42.tuxfamily.org/graph-maker-other/index.html
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/.