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

• Height, depth, eccentricity, radius, diameter, centre, centroid, weights, Wiener index and terminal Wiener.
• Children, neighbours, siblings, leaves, singletons, rows, min/max ancestor, min/max descendant.
• Matrix adjacency, incidence, path lengths, reachability, Laplacian. Characteristic polynomial of adjacency, Laplacian.
• 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. Canonical unlabelled, free, ordered, unrooted, lexmin.
• Automorphisms, asymmetric, as rooted or free.
• Iterate labelled, unlabelled, free, preorder. I'th preorder, downwards.
• Prime code, graph6, sparse6, balanced binary.
• Subdivide, join, delete, contract, branch reduce, root above, forest components.
• Sequences pre-order, post-order, rows, up ascend (Prüfer), up queue, down queue, subtree height, subtree sizes, blob, successive paths, childless paths.
• Make some specific trees. Make random labelled, preorder, downwards.
• Counts of various trees, forests, or properties.
• Least child monk, hereditary least single, strongly monotone, equaldepths.

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 for roots (spectra), Set()s for independent sets, matrices for some linear algebra, 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 12 here,

vpar.gp (594k, and sig), or compressed vpar.gp.gz (154k)
vpar-12.tar.gz (680k, and sig)

Just vpar.gp is enough to run. Comments at the start give an overview. The tar file includes some example scripts, self-tests, and work-in-progress extras. The extras mostly work but may change wildly. The sig files are Gnu PG ascii armoured signatures generated from my key.

The examples include bits of

• Bulgarian solitaire.
• Cospectrals per Mowshowitz.
• Equimatchable tree counts.
• Integral trees (integer adjacency spectrum) by diameter per Csikvari.
• Maximal asymmetric subtrees per Nesetril.
• Most maximum matchings per Heuberger and Wagner.
• Perm to upwards per Dennis Walsh.