2-regular Digraphs of the Lovelock Lagrangian
Richard J. Mathar





http://www.mpia-hd.mpg.de/ mathar 
Max-Planck Institute of Astronomy, Königstuhl 17, 69117 Heidelberg, Germany 



02.10.Ox, 04.20.Fy, 11.10.Ef


The manuscripts tabulates arc lists of the 1, 1, 3, 8, 25, 85, 397 …unlabeled 2-regular digraphs on 
n=0, 1, 2, …,9
nodes, including disconnected graphs, graphs with multiarcs and/or graphs with loops.
Each of these graphs represents one term of the Lagrangian of Lovelock's type —
a contraction of a product of n Riemann tensors — once the 2 covariant and 2 contravariant
indices of a tensor are associated with the in-edges and out-edges of a node.


2-regular Digraphs of the Lovelock Lagrangian
    Richard J. Mathar
    December 30, 2023
=============================================





§ REGULAR DIGRAPHS



 §.§ Nomenclature

In the common language of graph theory, digraphs (directed graphs) are graphs where
the edges (called arcs) are oriented, i.e., the two nodes of an arc are distinguished to be tail and head
of the arc. The indegree of a node is the number of arcs that
have heads at a node; the outdegree is the number of arcs that have tails at a node.
k-regular digraphs are digraphs where the indegree and outdegree at each node is the
same k <cit.>.
Loops are arcs where head and tail are the same node. (Each loop increases the
indegree and outdegree of the node by one.)
Multiarcs are multisets of two or more arcs that share a head and tail node.

The underlying simple graph of a digraph is obtained by reducing the arcs to undirected edges,
replacing multiedges by single edges, and removing loops. We will be only interested
in these simple graphs to classify the digraphs by the number of components of their
underlying simple graphs. (That means according to weak connectivity).

(Vertex) labeled graphs have distinct labels at their nodes, usually taken
to be the positive integers while handling graphs on computers, or letters from a onwards.
We define the Adjacency Matrix of a digraph of nodes labeled 1,2,… as the square
matrix which contains in row r and column c the number of arcs which start at node r 
and end at node c. Construction of the labeled k-regular digraphs admitting multiarcs and loops
is therefore equivalent
to constructing the n× n matrices with non-negative integer entries where all
row sums and all column sums are k.
These are registered in Table A008300 in the Online Encyclopedia of Integer Sequences
for the cases where multiarcs are not admitted, and in Table A257493
if multiarcs are admitted <cit.>.

Denote the number of unlabeled and labeled k-regular digraphs with n nodes
and c components by U_k(n,c) and L_k(n,c). 

The unlabeled graphs with c>1 components can be derived from
the connected graphs quickly
by the Multiset Transformation, collecting arrangements
over all partitions of n into c parts <cit.><cit.>:

    U_k(n,c) = ∑_n=n_1+2n_2+⋯ +cn_cn_i≥ 0∏_i=1^c U_k(i,1)+n_i-1n_i.


The number of unlabeled and labeled
k-regular digraphs with n nodes 
is

    U_k(0)=1;   U_k(n)    ≡   ∑_c=1^n U_k(n,c); 
    
    L_k(0)=1;   L_k(n)    ≡   ∑_c=1^n L_k(n,c).

The case of the unlabeled 1-regular digraphs is simple: the connected
1-regular digraphs are cycles (unicycles), including the case with 1 node and its loop: 

    U_1(n,1) =1.

So the
number of unlabeled, not necessarily connected, 1-regular digraphs on n nodes, U_1(n),
is the number of partitions of n <cit.>,
and the U_1(n,c) are the partition numbers <cit.>.



 §.§ Symmetries


The key part of this work is to identify the Automorphism Group of the labeled
2-regular digraphs, which is the group of permutations of the labels which keeps
the Adjacency Matrix of a graph the same. This bundles a set of one or more
labeled digraphs which are mapped onto each other by the permutations of
the group, and each such set is represented by a single unlabeled 2-regular digraph.
This is one way of erasing/forgetting any particular order
on the nodes while maintaining the connectivity and structure of the graph.

The unlabeled 2-regular digraphs might also be obtained by starting from the cubic QED 
vacuum polarization diagrams 
<cit.>,
coalescing each edge that represents an undirected photon line and its two incident nodes
into a single node such that only the directed fermion lines connect to the remaining nodes—representing
nodes of a φ^4 theory—, 
plus a cleanup that eliminates duplicates.
Another approach is to construct first the 4-regular undirected unlabeled graphs 
<cit.><cit.>, and to add directions later.

We shall keep track of the Automorphism Group A of each graph by writing down the
Cycle Index of the group of the node permutations <cit.>. Since A
is  a subgroup of the group of all permutations of n, its order, | A|, is a divisor of n!.
The denominator of the cycle index polynomial is | A|, so we can recover
the number of labeled digraphs by dividing n! through the denominator of the Cycle Index <cit.>.
For n=3 nodes, for example, U_2(3)=8 unlabeled 2-regular digraphs exist
with 4 different Cycle Indices:


  * 1 graph with cycle index (t_1^3)/1,

  * 3 graphs with cycle index (t_1^3+t_1t_2)/2,

  * 2 graphs with cycle index (t_1^3+2t_3)/3,

  * and 2 graphs with cycle index (t_1^3+3t_1t_2+2t_3)/6,

and 1× 3!/1 + 3× 3!/2 + 2× 3!/3 + 2× 3!/6=21 = L_2(3) 
is the number of labeled
graphs on 3 nodes <cit.>.
As we are admitting loops, there is always at least one graph on n nodes (the one consisting of 
n isolated nodes with two loops each) that has the maximum symmetry here, | A|=n!.



The labeled graphs with c>1 components
are deduced from the weakly connected labeled graphs by a Bell transformation,
summing over all compositions of n into positive parts weighted by multinomial
coefficients <cit.>:

    L_k(n,c) = 1/c!∑_n=n_1+n_2+⋯ +n_cn_i≥ 1nn_1,n_2,⋯, n_c∏_i=1^c L_k(n_i,1).

If

    L_k(x,1) ≡∑_n≥ 1L_k(n,1)/n!x^n

denotes the exponential generating function of the weakly connected labeled graphs,
the bivariate exponential generating function of the labeled graphs is <cit.>

    L_k(x,t) ≡∑_n,c≥ 0L_k(n,c)/n!x^n t^c
    = exp[ t L_k(x,1)].


The corresponding derivation starting from L_1(n,1)=1 demonstrates that L_1(n,c)
are the Stirling Numbers of the Second Kind <cit.>
and L_1(n) the Bell Numbers <cit.>.

For L_2, the number of labeled digraphs refined by the number of weakly connected components
is summarized in Table <ref>.  








§ GALLERY OF UNLABELED 2-REGULAR DIGRAPHS

The unlabeled 2-regular digraphs on n≤ 5 nodes are illustrated in the following
sections. Each digraph has 2n arcs.
For easier visual recognition, the graphs with more than one component are surrounded
by a frame. 
These visualize throw schemes  for
n 2-armed jugglers.


 §.§ 1 graph on 1 node



    < g r a p h i c s >




 §.§ 3 graphs (2 connected) on 2 nodes



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >




 §.§ 8 graphs (5 connected) on 3 nodes



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >





 §.§ 25 graphs (14 connected) on 4 nodes



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >




 §.§ 85 graphs (50 connected) on 5 nodes



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >



    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >







§ BIJECTION WITH LOVELOCK TERMS


Bogdanos has pointed at a graphical representation of the terms of Lovelock's Lagrange density
<cit.>:
A graph of a particular term which is a product of n Riemann Tensors is constructed as follows:
(i) Start with a bottom row of n nodes plus a top row of another n nodes,
where nodes are associated left-to-right with a left-to-right reading of the R-factors of the product.
(ii) Add an edge from the b-th bottom node to the t-th top node if  a covariant lower index
of factor number b appears as a contravariant index of factor number t.
This assignment works because the two contravariant indices are permutations of the covariant indices.
Since the Riemann Tensor is (skew)-symmetric in the first and in the last two indices, the
representation does not need to track the two edges at each node to distinguish a “first” from a “second.”
Bogdanos' representation is a labeled, undirected 2-regular graph on 2n nodes.

Our graphical representation transforms these bipartite graphs once more <cit.>:


  * Bogdanos' edges are turned into directed edges (arcs), always heading from a node of the bottom row to a
node on the top row.  

  * Each pair of nodes associated with the same R-factor is 
collapsed
into
a single node, keeping all arcs fastened to their nodes. Loops appear if the R-factors
were already contracted (Ricci tensors).

  * Labels are erased, meaning that the left-to-right reading orders of the product of the R
are all equivalent reflecting the usual commutative law for multiplications. 
The multiplicity may be recovered by examining the Automorphism Group of the new graph

This transformation of Bogdanos' bipartite graphs on 2n nodes to our 2-regular digraphs on n nodes
is lossless (reversible).



§ LINE GRAPHS
 
Each digraph has an associated line digraph which is defined as follows <cit.>:
Each arc in the digraph is rendered as one node in the line digraph.
An arc from node a in the line digraph (corresponding to an arc from node u to node v in the digraph)
to node b in the line digraph (corresponding to an arc from node w to node x in the digraph)
exists if the nodes v and w are the same, which means, if the two arcs in the graph
are adjacent to each other and have aligned directions.

Loops in the digraph create loops in the line digraph. A k-regular digraph on n nodes
preduces a k-regular line digraph on kn nodes.



§ SINGLE EDGE CUTS

If a single arc of the 2-regular digraphs discussed above is cut,
a pair of two additional nodes appears at that place: one with indegree 1 and outdegree 0,
another with indegree 0 and outdegree 1; the other nodes keep their degrees. 
The equivalent action in the tensor product 
is to leave one pair of indices uncontracted; the equivalent action in a φ^4-theory
is to move from the vacuum diagrams to the diagrams of Green's functions.
In a preparational step one might have enumerated the marked line graphs where
the marked nodes in the line graphs would  indicate which lines are cut in
their base graphs. 

The notation U_k,+2(n,c) will be used for the number the unlabeled digraphs
with c components 
with n-2 nodes with indegree and outdegree k plus 2 nodes with the mixed in-outdegrees
of (0,1) and (1,0) created by the cut.
(Adopting the nomenclature of  Chae et al. <cit.>, these “almost” regular graphs will
be called fairly regular graphs.)
The enumeration for any number of components
is U_k,+2(n)≡∑_c U_k,+1(n,c).
Only the connected graphs (where c=1) are relevant because the graphs with 
more than one component can be constructed by taking one connected graph 
and
adding any number of graphs of the 
k-regular class. So the ordinary generating function
of the fairly regular digraphs U_k,+2(n) 
is the product of the ordinary generating function
of U_k,+2(n,1) by the ordinary generating function of U_k(n),
and the equivalent statement holds for the
exponential generating function of the labeled graphs.

The full set of these 1-in 1-out graphs up to 6 nodes obtained
by cutting an arc follows.
The cases without multiarcs up to 7 nodes I have already shown in
a manuscript in <cit.>.





 §.§ 1 connected graph on 2 nodes


    < g r a p h i c s >



 §.§ 1 connected graph on 3 nodes


    < g r a p h i c s >



 §.§ 3 connected graphs on 4 nodes


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >



 §.§ 12 connected graphs on 5 nodes


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >



 §.§ 61 connected graphs on 6 nodes


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >




A summary of the enumeration with one arc cut
is in Table <ref>.




§ PAIRS OF CUTS

Cutting two distinct arcs of a connected 2-regular digraph
produces U_2,+4(n,c) unlabeled digraphs with c components
where 4 nodes
appear at the cuts: 2 with indegree 1 and outdegree 0,
and another 2 with indegree 0 and outdegree 1. The n-4 “internal”
nodes keep their degrees.
(Cutting the same arc twice is not interesting because that merely
produces two disconnected graphs already covered by the previous section.)
The operation with two cuts is topologically more complex
than products of a single cut. (i) There is no longer
a 1-to-1 correspondence from the graph with the 2-in 2-out nodes
to the uncut parent. There are generally two variants
of merging the nodes with total degree 1 to
rebuild a 2-regular digraph; exceptions are cases with high symmetry
like in Section <ref> which obviously has the parent shown
in Section <ref>.
(ii) If the two cuts target a pair of arcs between a single pair
of nodes or more generally two arcs of a 2-connected graph, 
a graph with more than one component (i.e. two
graphs of the type in Section <ref>) may result.
So the generating function of ∑_c U_2,+4(n,c) is the product
of the generating functions U_2,+4(n,1) and ∑_c U_2(n,c)
to account for graphs where all four nodes of degree 1 are in
the same component, plus the symmetrized square
generating function of ∑_c U_2,2(n,c) by ∑_c U_2(n,c)
to account for the
graphs where two nodes of degree 1 are in one component,
the other two nodes in another component, and any other
number of 2-regular graphs in further components.
[The symmetrized square of a generating function g(x) is
[g(x)^2+g(x^2)]/2 following from the cycle index for the symmetric group S_2
<cit.>.]


A gallery of these 2-in 2-out graphs up to 7 nodes illustrates
that concept in the next 3 subsections, showing only
the connected digraphs. 


 §.§ 1 connected graph on 5 nodes
 

    < g r a p h i c s >



 §.§ 4 connected graphs on 6 nodes


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >



 §.§ 21 connected graphs on 7 nodes


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


    < g r a p h i c s >


A summary of the enumeration with two
arcs cut is in Table <ref>.





§ SUMMARY

Table <ref> summarizes the bare counts U_2(n,c). 




The row sums 
1, 3, 8, 25, …count the graphs with any number of components.
U_2(4) and U_2(5) have already been computed by Briggs
<cit.>.
We observe that Briggs' extrapolations 
to
more than 5 nodes <cit.>
underestimate the true number of graphs for 6 – 9 nodes.




§ MACHINE READABLE TABLES


The ancillary directory contains the information of the unlabeled
2-regular digraphs in files named n, where
n is the number of nodes. 
After unzipping, each file contains up to three successive
lines per graph:


  * An arc list for 2n arcs, referring to a representative of the labeled graphs created
by the A-group, with labels from 0 up to n-1, in square brackets.
Each bracket contains a pair of numbers, separated by a comma; the first is
the tail node and second the head node of the arc. Multiarcs are rendered by repeating
such pairs.

  * A capital , the number of multiarcs in the graph (i.e., the number of entries larger
than 1 in the Adjacency Matrix), a blank,
the trace of the Adjacency Matrix (i.e., the number of loops), a blank, and the Pólya Cycle
Index (a multinomial in the free variables t_i).



Filtering the lines that start with  in these files we obtain
1, 3, 8, 27,…unlabeled, not necessarily connected, 2-regular digraphs with n≥ 2 nodes without multiarcs <cit.>.

Filtering the lines that start with  in these files we obtain

1, 2, 5, 23,…unlabeled, loopless, not necessarily connected, 2-regular digraphs with n≥ 3 nodes without multiedges <cit.>.

As a further check, filtering the lines that contain  we obtain 1, 2, 6, 15, 68,…graphs
on n≥ 2 nodes without loops (which may have multiarcs) <cit.>.



One application of this information yields the r-rooted unlabeled
2-regular digraphs by defining the generating function r(x)=1+x for
the number of ways of labeling a node as 0 (not marked) or 1 (marked),
and then substituting t_i→ r(x^i) in the cycle indices. Summation over
the cycle indices of all graphs of fixed n generates Table <ref>.



Another information drawn from the cycle indices are the parities
of the permutations of the node-labeled 2-regular digraphs that
leave the unlabeled graph intact. A permutation is odd, iff
there is an odd number of even-length cycles, i.e., iff for even index 
i there is an odd exponent j in the factor t_i^j of the cycle index.
For products of different i the product rule for the signs of cycles rules.
Example: one of the 25 graphs on 4 nodes has the cycle index (t_1^4 +2t_1^2t_2 +3t_2^2 +2t_4)/8.


  * The term t_1^4 is one permutation with no even index, so this is an even permutation.

  * The term 2t_1^2t_2 is two permutations with an even index with exponent 1, so this
represents two odd permutations.

  * The term 3t_2^2 is three permutations with an even index with exponent 2, so this
represents three even permutations.

  * The term 2t_4 is two permutations with an even index with exponent 1, so this
represents two odd permutations.





The ancillary directory contains the information of the connected unlabeled
fairly 2-regular digraphs of Section <ref> in files named n, where
n is the number of nodes, including the 2 nodes with degree 1. 
The arc lists contain 2n-3 arcs and the lines starting with V
are the cycle indices.

The ancillary directory contains the information of the connected unlabeled
fairly 2-regular digraphs of Section <ref> in files named n, where
n is the number of nodes, including the 4 nodes with degree 1. 
The arc lists contain 2n-6 arcs and the lines starting with V
are the cycle indices.



§ JAVA CODE

The ancillary directory contains the source code of the Java classes
in the .
The  command
in the  compiles the code. The other lines
in the  demonstrate how the counts for the unlabeled
digraphs are obtained by calling two  classes in succession.
The first is  which generates incidence matrices
for digraphs of mixed connectivity and of specified degree squences
and prints the corresponding
edge/arc lists which is redirected to an intermediate file.

then reads such an
edge/arc list and reduces these sets to unlabeled graphs edge
lists by running through all row-column permutations and leaving
only one representative in its standard output.
The two -pages  and 
provide details of options and arguments of the two classes.

The examples in the  are not optimized for speed.
They construct the L_2,+2(n,c) for example with 2 nodes of
degree 1 and n-2 nodes of in- and outdegree 2. Just
two geometries occur: the 2 nodes are connected to the same node or
to different nodes. So one could gather all cases by running
the program twice forgetting the 2 leaf nodes, constructing
graphs with n-2 nodes:
(i) a run with 1 node of indegree 1 and outdegree 1 and n-3 nodes
indegree and outdegree 2, (ii) a run with 1 node of indegree 1 and outdegree 2,
1 node of outdegree 1 and indegree 2, and n-4 nodes of indegree and outdegree 2.
After the reduction to unlabeled graphs the 2 leaf nodes 
could be re-attached at the nodes which are uniquely characterized
by their underrun of degrees.




