++ed by:

1 non-PAUSE user.

Kevin Ryde
and 1 contributors

# 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