NAME

Graph::Maker::Beineke - create Beineke non-line graphs

SYNOPSIS

 use Graph::Maker::Beineke;
 $graph = Graph::Maker->new ('Beineke', G => 9);

DESCRIPTION

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.

FUNCTIONS

$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

House of Graphs entries for the graphs here are

G1, https://hog.grinvin.org/ViewGraphInfo.action?id=500
G2, https://hog.grinvin.org/ViewGraphInfo.action?id=438
G3, https://hog.grinvin.org/ViewGraphInfo.action?id=450
G4, https://hog.grinvin.org/ViewGraphInfo.action?id=922
G5, https://hog.grinvin.org/ViewGraphInfo.action?id=21099
G6, https://hog.grinvin.org/ViewGraphInfo.action?id=744
G7, https://hog.grinvin.org/ViewGraphInfo.action?id=21093
G8, https://hog.grinvin.org/ViewGraphInfo.action?id=21096
G9, https://hog.grinvin.org/ViewGraphInfo.action?id=204

And also

12-vertex union https://hog.grinvin.org/ViewGraphInfo.action?id=748
Subgraph relations https://hog.grinvin.org/ViewGraphInfo.action?id=25225

SEE ALSO

Graph::Maker, Graph::Maker::Star, Graph::Maker::Wheel

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