`vpar.gp`

This is some functions for Pari/GP making calculations on labelled oriented trees (graph theory trees) as "vpar" vector of parent vertex numbers. Functions include to unlabelled,free, downwards ith, Prufer sequence.

- Height, depth, eccentricity, radius, diameter, centre, centroid, weights, Wiener index and terminal Wiener.
- Children, neighbours, siblings, singletons, rows, min/max ancestor, min/max descendant.
- Matrix adjacency, skew adjacency, incidence, path lengths, Laplacian, characteristic polynomial of adjacency.
- Independent sets, matchings, maximal matchings, equimatchable, stable equimatchable, almost equimatchable.
- Dominating sets, minimal dominating sets, independent dominating sets, total dominating sets, semi-total domination number, perfect dominating sets, disjoint domination number.
- Relabelling, re-rooting, upwards/downwards.
- Isomorphism as unlabelled, free, ordered. Canonicial forms unlabelled, free, ordered, unrooted.
- Automorphisms, asymmetric, as unlabelled, free.
- Iteration labelled, unlabelled, free, preorder. I'th preorder, downwards.
- Prime code, graph6, sparse6.
- Subdivide, join, delete, contract, branch reduce, root above, forest components.
- Sequences pre-order, post-order, rows, up ascend (Prüfer), up queue, subtree height, subtree sizes, blob, successive paths, childless paths.
- Make some specific trees, including random labelled, preorder, downwards.
- Counts of various trees, forests, or properties.
- Least child monk, hereditary least single.

Vertices are numbered 1 to n. A tree is a vector `vpar`

where
`vpar[v]`

is parent of `v`

, or `0`

if no
parent. Such a representation is oriented in that there is a distinguished
root (or roots for a forest) and labelled in that each vertex has a particular
number. There are no other attributes etc.

The main use is to calculate or verify properties of specific trees of interest. Various functions like diameter are the same for any root or labelling so effectively act as on a "free" tree and the vertex numbers just for tree creation. Most functions are linear in the number of vertices so can be used on large trees.

The connections to Pari/GP specifics are at polynomials and
`Set()`

s for independent sets etc, matrices for some linear algebra
or eigenvalues etc, permutations in relabelling, and then general compactness
of GP for experimenting etc.

`vpar.gp`

is
free software (free
as in freedom), published under the terms of the
GNU
General Public License (v3 or higher). Download version
9 here,

`vpar.gp`

(537k, and sig), or compressed`vpar.gp.gz`

(138k)

`vpar-9.tar.gz`

(580k, and sig)

Just `vpar.gp`

is enough to run. The `tar`

file
includes some example scripts, self-tests, and work-in-progress extras (most
of which work but may change wildly). The sig files are
Gnu PG ascii armoured signatures generated
from my key.

See also `gentreeg`

in the
Nauty tools which generates free
trees in this kind of vertex parent form (among other forms) and can be used
command line or C.

See my
`Graph-Maker-Other`

for some graph (and tree) creation in Perl.

This page Copyright 2017, 2018 Kevin Ryde, except for the GPLv3 logo which is Copyright Free Software Foundation and used here in accordance with its terms.

(Back to the sitemap, or the Pari/GP section there).