A digraph D is a couple D = (V, A), where V is a finite nonempty set and A ⊂ V x V - { (v,v): v ∈ V }. If u,v ∈ V we will write (u,v) as uv. If a ∈ A we write D-a for the digraph (V, A-{a}). A q-cycle is a directed cycle of length q and a directed tree is a digraph obtained from a tree by replacing each edge {u,v} with the two arcs uv and vu.

A digraph D is strongly connected or (simply) strong if every ordered pair of vertices in D are joined by a path. It is well known that the digraph D is strong if and only if its adjacency matrix M is irreducible [2]. For simplicity, in the following we will write strong dipraphs as SC digraphs.

If we add an arc to the set of arcs of an SC digraph D then the cyclic structure of D is modified. This suggests the introduction of the concept of minimal strong digraph. An SC digraph D is minimal if D-a is not strongly connected for any arc a ∈ A. For simplicity, in the following we will write minimal strong digraph as MSC digraph. MSC digraphs can be said to generalize the trees when we consider directed graphs instead of simply graphs. Nevertheless, the structure of MSC digraphs is much richer than that of the trees.

The set of SC digraphs of order n with vertex set V can be partially ordered by the relation of inclusion among their sets of arcs. Then, the MSC digraphs are the minimal elements of this partially ordered set. Analogously, the set of irreducible (0,1)-matrices of order n with zero trace can be partially ordered by means of the coordinatewise ordering. The minimal elements of this partially ordered set are called nearly reducible matrices and so the digraph D is an MSC digraph if and only if its adjacency matrix M is a nearly reducible matrix [2, 6].

Bhogadi [1] gives a characterization of Cunningham's decomposition trees for minimal strong digraphs under X-joint (substitution) composition [3]. He uses his characterization to generate all minimal strong digraphs through 12 vertices and all minimal 2-connected graphs through 13 vertices.

In [5] the authors introduce adequate concepts of expansion of a digraph to obtain a sequential construction of minimal strong digraphs and characterize the class of minimal strong digraphs whose expansion preserves the property of minimality. They prove that every minimal strong digraph of order n ≥ 2 is the expansion of a minimal strong digraph of order n-1 and give sequentially generative procedures for the constructive characterization of the classes of minimal strong digraphs. Finally they describe algorithms to compute unlabeled minimal strong digraphs and their isospectral classes.

Unlabeled MSC digraphs

For the representation of the unlabeled MSC digraphs we use two different formats. Both of them encode the adjacency matrices (a_i,j) of the MSC digraphs in a text file. Let us assume that order = n and that V = { v₁, v₂, ..., v_n }.

Format 1: n+1 lines for each MSC digraph of order n.

D_<number>
<a₁₁> <a₁₂> ... <a_1n>
<a₂₁> <a₂₂> ... <a_1n>
..........
<a_n1> <a_n2> ... <a_nn>

where a_ij = 1 if v_iv_j ∈ A and a_ij = 0 if v_iv_j ∉ A.

Format 2: One line for each MSC digraph of order n.

D_<number> <w₁> <w₂> ... <w_n>

where w_i = a_i12⁰ + a_i22¹ + a_i32² + ... + a_in2^n-1.

Unlabeled MSC digraphs (table last modified 12 Sep 2012)

Notes: ^† results obtained in [1] and ^‡ results obtained in [5].

It is known that the size |A| of an MSC digraph D of order n verifies that n ≤ |A| ≤ 2(n-1), an MSC digraph D is an n-cycle if and only if it has size |A| = n and an MSC digraph D is a directed tree of order n if and only if it has size |A| = 2(n-1).

The number of unlabeled MSC digraphs of order n appears in The On-Line Encyclopedia of Integer Sequences (OEIS). Specifically it is the sequence A130756 and, by the observation in the previous paragraph, is related with the sequence of the number of trees with n unlabeled nodes A000055.

Isospectral classes of MSC digraphs

In [5,7] the authors are also interested in the following nonnegative inverse eigenvalue problem: given real numbers k₁, k₂, ..., k_n, find necessary and sufficient conditions for the existence of a nonnegative matrix A of order n with characteristic polynomial xⁿ + k₁x^n-1 + k₂x^n-2 + ... + k_n. The coefficients of the characteristic polynomial are closely related to the cycle structure of the weighted digraph with adjacency matrix A [4], and the irreducible matricial realizations of the polynomial are identified with SC digraphs [2]. The class of SC digraphs can easily be reduced to the class of MSC digraphs, so we are interested in the characterization of the monic polynomials of degree n with integral coefficients, which are the characteristic polynomials of SC or MSC digraphs of order n.

For the representation of the characteristic polynomials of the isospectral classes of MSC digraphs we use the following format, that encodes the characteristic polynomials of the isospectral classes in a text file. Note that k₁ is always zero.

Format 1: One line for each isospectral class.

P_<number> D_<j> <k₂> <k₃> ... <k_n>

where D_<j> is one of the MSC digraphs of order n with characteristic polynomial P_<number> = xⁿ + k₂x^n-2 + k₃x^n-3 + ... + k_n.

Format 2: w+1 lines for each isospectral class of size w.

P_<number> <k₂> <k₃> ... <k_n>
D_<j₁>
D_<j₂>
..........
D_<j_w>

where D_<j₁>, D_<j₂>... D_<j_w> are the MSC digraphs of order n with characteristic polynomial P_<number> = xⁿ + k₂x^n-2 + k₃x^n-3 + ... + k_n.

Isospectral classes of MSC digraphs (table last modified 12 Sep 2012)

Notes: ^‡ results obtained in [5] and ^* interim result.

References

1. K.K. Bhogadi, Decomposition and generation of minimal strongly connected digraphs, Master's Thesis, Univ. of Georgia, Athens, (1999).
2. R.A. Brualdi and H.J. Ryser, Combinatorial matrix theory, Cambridge University Press, New York, 1992.
3. W.H. Cunningham, Decomposition of directed graphs, SIAM J. Alg. Disc. Methods 3 (1982) 214-228.
4. D.M. Cvetkovic, M. Doob and H. Sachs, Spectra of graphs, Deutscher Verlag Wissenschaften, Berlin, 1982.
5. J. García-López and C. Marijuán, Minimal Strong Digraphs, Discrete Mathematics 312 (4) (2012) 737-744.
6. M. Hedrick and R. Sinkhorn, A special class of irreducible matrices-the nearly reducible matrices, J. Algebra 16 (1970) 143-150.
7. J. Torre-Mayo, M.R. Abril-Raymundo, E. Alarcia-Estévez, C. Marijuán and M. Pisonero, The nonnegative inverse eigenvalue problem from the coefficients of the characteristic polynomial. EBL digraphs, Linear Algebra and its Applications 426 (2007) 729-773.