Digraphs Whose Nodes are Multigraphs Having Exactly Two Degrees \(f\) and \(2\).

Abstract

An \((f,2)\)-graph is a multigraph \(G\) such that each vertex of \(G\) has degree either \(f\) or \(2\). Let \(S(n, f)\) denote the simple graph whose vertex set is the set of unlabeled \((f,2)\)-graphs of order no greater than \(n\) and such that \(\{G, H\}\) is an edge in \(S(n, f)\) if and only if \(H\) can be obtained from \(G\) by either an insertion or a suppression of a vertex of degree \(2\). We also consider digraphs whose nodes are labeled or unlabeled \((f, 2)\)-multigraphs and with arcs \((G, H)\) defined as for \(\{G, H\}\).

We study the structure of these graphs and digraphs. In particular, the diameter of a given component is determined. We conclude by defining a random process on these digraphs and derive some properties. Chemistry applications are suggested.