The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.
 / 
Graph-Maker-Other-19
River stage zero No dependents
1 ++
/ Graph::Maker::MostMaximumMatchingsTree

NAME

Graph::Maker::MostMaximumMatchingsTree - create trees of most maximum matchings

SYNOPSIS

 use Graph::Maker::MostMaximumMatchingsTree;
 $graph = Graph::Maker->new ('most_maximum_matchings_tree', N => 9);

DESCRIPTION

Graph::Maker::MostMaximumMatchingsTree creates a Graph.pm graph of N vertices with the most maximum matchings per

A matching is a set of vertex pairs with the vertices of each pair connected by an edge, and no vertex used more than once. Or equivalently, a set of edges with no end vertices in common. In a given tree, there is a maximum size matching (the match number). Various different matchings may be this maximum size.

Heuberger and Wagner consider the number of maximum matchings a tree of N vertices might have and show for N != 6,34 there is a unique tree with the most maximum matchings, and for N=6,34 two trees of equal most.

The trees have various special cases for small N, and then general forms according to N mod 7. Vertices are presently numbered 1 to N, but don't rely on that, nor on exactly which is attached to which.

Trees of N=0 to 6 vertices inclusive are stars the same as Graph::Maker::Star. The second tree of 6 vertices is a special N=6.5.

       2                                *
       |       N => 6                   |    N => 6.5
    6--1--3    star,           *--B--*--B
      / \      5 maximum                |    5 maximum
     5   4     matchings                *    matchings

For 34 vertices, the general case tree is

                         *   *
                          \ /
                           B
                           |             N => 34
          *   *            *
           \ /     *\      |             59049 maximum matchings
            B        B--*--B--*          match number 10
            |      */      |
            *              *
    *\      |              |      /*
      B--*--B------*-------B--*--B
    */      |              |      \*
            *              *
            |              |
            B              B
           / \            / \
          *   *          *   *

And the second tree is a special N=34.5,

          *   *          *   *
           \ /            \ /            N => 34.5
            B              B
            |              |             same
            *      *       *             59049 maximum matchings
    *\      |      |       |      /*     match number 10
      B--*--B--*---B---*---B--*--B
    */      |      |       |      \*
            *      *       *
            |      |       |
            B      B       B
           / \    / \     / \
          *   *  *   *   *   *

Heuberger and Wagner take vertices in two types. Type B are matched in every maximum matching, and type A are not. Their final most maximum matchings trees have A and B alternating. All leaf vertices and vertices an even distance from a leaf are type A, and all odd distance from a leaf are type B.

The match number is the number of B vertices. This is since when making the match number, a vertex with a leaf neighbour must be matched (or it and one of its leaves unmatched would be not maximal), and taking the leaf rather than the next vertex inwards is an equal or bigger match number for the rest.

Coordinates

There's a secret undocumented coordinates option which sets vertex attributes for locations in the style of Heuberger and Wagner's example picture. This is a good way to see the pattern, but don't rely on this yet as it might change or be removed.

FUNCTIONS

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

The key/value parameters are

    N           => integer, number of vertices
                     or special 6.5 or 34.5
    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 ways 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

    1310     N=1     singleton
    19655    N=2     path-2
    32234    N=3     path-3
    500      N=4     claw, star-4
    544      N=5     star-5
    598      N=6     star-6
    288      N=6.5   other equal most N=6
    498      N=7     complete binary tree
    31053    N=8
    672      N=9
    25168    N=10    (mean distance = 1/2 diameter)
    34225, 34227, 34229, 34231, 34233    N=11 to N=15
    34235, 34237, 34239, 34241, 34243    N=16 to N=20
    34245, 34247, 34249, 34251, 34253    N=21 to N=25
    34255, 34257, 34259, 34261, 34263    N=26 to N=30
    34265, 34267, 34269                  N=31 to N=33
    31068    N=34
    31070    N=34.5
    31057    N=181   example in Heuberger and Wagner's paper

SEE ALSO

Graph::Maker

My vpar includes an examples/most-maximum-matchings.gp program making these trees in Pari/GP, and recurrences for their number of maximum matchings.

Heuberger and Wagner's Sage code includes general case tree creation, and counting of the maximum matchings.

HOME PAGE

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

LICENSE

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