++ed by:

1 non-PAUSE user.

Kevin Ryde
and 1 contributors


Graph::Maker::BiStar - create bi-star graphs


 use Graph::Maker::BiStar;
 $graph = Graph::Maker->new ('bi_star', N=>5, M=>4);


Graph::Maker::BiStar creates Graph.pm bi-star graphs. A bi-star graph is two stars with an edge connecting the centre vertex of the two. Parameters N and M are how many vertices in each star, for total N+M vertices.

     3   2       9
      \ /         \          N=>5  M=>4
      / \         /          total vertices N+M = 9
     4   5       7

Vertices of the first star are numbered per Graph::Maker::Star, then the second star similar but offset +N.

      1                      first star centre
      2 to N inclusive       first star surrounding
      N+1                    second star centre
      N+2 to N+M inclusive   second star surrounding

If N=0 then that star is no vertices and there is no middle edge, leaving just star M. Likewise conversely if M=0. If both N=0 and M=0 then the graph is empty.

If N=1 or M=1 then that star is a single vertex only and so is like an extra arm on the other, giving a single star N+M.


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

The key/value parameters are

    N  => integer, number of vertices in first star
    M  => integer, number of vertices in second star
    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 in both directions (like Graph::Maker::Star does). Option undirected => 1 creates an undirected graph and for it there is a single edge between vertices.


The graph diameter is 3 when both N,M>=2. The smaller cases can be written

    diameter(N,M) = (N>=2) + (M>=2) + (N>=3 || M>=3 || (N>=1&&M>=1))

The Wiener index (total distances between vertex pairs) follows from counts and measures between the leaf and centre vertices. Cases M=0 or N=0 reduce to a single star which are exceptions.

    Wiener(N,M) = N^2 + 3*N*M + M^2 - 3*N - 3*M + 2
                  + if M=0 then N-1
                  + if N=0 then M-1

                = (N+M)*(N+M-3) + N*M + 2
                  + if M=0 then N-1
                  + if N=0 then M-1

With N+M vertices, the number of pairs of distinct vertices is

    Pairs(N,M) = (N+M)*(N+M-1)/2

Mean distance between vertices is then Wiener/Pairs. A bi-star with some particular desired mean distance can be found by solving for N,M, which becomes a binary quadratic form.

    Wiener(N,M) = Pairs(N,M) * mean


House of Graphs entries for the graphs here include

2,2, https://hog.grinvin.org/ViewGraphInfo.action?id=594 (path-4)
3,2, https://hog.grinvin.org/ViewGraphInfo.action?id=30 (fork)
3,3, https://hog.grinvin.org/ViewGraphInfo.action?id=334 (H graph)
4,2, https://hog.grinvin.org/ViewGraphInfo.action?id=208 (cross)
4,3, https://hog.grinvin.org/ViewGraphInfo.action?id=452
4,4, https://hog.grinvin.org/ViewGraphInfo.action?id=586 (Ethane)
5,2, https://hog.grinvin.org/ViewGraphInfo.action?id=266
5,4, https://hog.grinvin.org/ViewGraphInfo.action?id=634
5,5, https://hog.grinvin.org/ViewGraphInfo.action?id=112
6,2, https://hog.grinvin.org/ViewGraphInfo.action?id=332
6,5, https://hog.grinvin.org/ViewGraphInfo.action?id=650
6,6, https://hog.grinvin.org/ViewGraphInfo.action?id=36
7,2, https://hog.grinvin.org/ViewGraphInfo.action?id=366
7,6, https://hog.grinvin.org/ViewGraphInfo.action?id=38
7,7, https://hog.grinvin.org/ViewGraphInfo.action?id=166
8,2, https://hog.grinvin.org/ViewGraphInfo.action?id=436
8,7, https://hog.grinvin.org/ViewGraphInfo.action?id=168
9,2, https://hog.grinvin.org/ViewGraphInfo.action?id=316
10,2, https://hog.grinvin.org/ViewGraphInfo.action?id=320
10,6, https://hog.grinvin.org/ViewGraphInfo.action?id=27414


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


Copyright 2017, 2018, 2019 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/.