/ 
Graph-Maker-Other-19
River stage zero No dependents
/ Graph::Maker::BiStar

NAME

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

SYNOPSIS

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

DESCRIPTION

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
  1-----------6---8
 / \         /          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.

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

FUNCTIONS

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

FORMULAS

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

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

SEE ALSO

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

HOME PAGE

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

LICENSE

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