WorksMathematics
Enumeration of Cospectral Graphs with Respect to the Average Flow Matrix
Abstract
A graph is said to be determined by the spectrum of a graph-associated matrix if no nonisomorphic graph shares the same spectrum with it. In this paper, we introduce the average flow matrix of a connected graph and study its spectral properties. We investigate its effectiveness in distinguishing graphs by carrying out a computational enumeration of connected graphs having a cospectral mate with respect to this matrix up to order 10. Our computations show that every connected graph on at most 10 vertices is determined by the spectrum of the average flow matrix. To the best of our knowledge, this is the first graph-associated matrix for which the spectrum distinguishes all connected graphs of order at most 10.
Introduction
Spectral graph theory studies the extent to which structural properties of a graph are reflected in the eigenvalues of graph-associated matrices. One of its central questions is whether a graph can be uniquely determined by the spectrum of such a matrix. In this context, graphs that share the same spectrum with a non-isomorphic graph are called cospectral, and the existence of such graphs shows that spectral data do not always determine graph structure completely. Nevertheless, spectral invariants provide useful tools for distinguishing graphs and are therefore also closely related to the graph isomorphism problem.
This question has a long history in spectral graph theory. Before 1956, it was believed that every graph is determined by its adjacency spectrum. Günthard and Primas [6] raised the broader question of whether there exists a graph-associated matrix for which every graph is determined by the corresponding spectrum. Later, Godsil and McKay [4] enumerated adjacency-cospectral graphs on up to 9 vertices and introduced several construction techniques for cospectral graphs, among which Godsil–McKay switching is one of the best known. Brouwer and Spence [3] extended the enumeration of adjacency-cospectral graphs to graphs on 12 vertices. Van Dam and Haemers [11] answered the question of Günthard and Primas [6] positively in principle by showing that it is possible to associate a matrix with a graph such that every graph is determined by its spectrum. However, no such concrete matrix has yet been identified [1]. Van Dam and Haemers [11] also conjectured that the proportion of graphs having a cospectral mate tends to 0 as the order of the graph tends to infinity.
Motivated by these questions, a considerable amount of work has focused on the enumeration of cospectral graphs and on comparing the effectiveness of different graph-associated matrices. Haemers and Spence [8] studied enumeration with respect to the adjacency, Laplacian, and signless Laplacian matrices. Wilson and Zhu [Wilson and Zhu(2007)] showed that the fraction of graphs determined by spectral data can be improved by considering two or three matrices simultaneously. Aouchiche and Hansen [2] demonstrated that distance-based matrices perform better than the adjacency and Laplacian matrices in distinguishing graphs. More recently, Abiad and Alfaro [1] investigated both cospectral and coinvariant graphs and further refined the comparison of graph-associated matrices. These results suggest a common pattern: stronger enumeration results are often obtained when more structural information about a graph is incorporated into the associated matrix.
Despite these advances, none of the graph-associated matrices studied so far has been able to determine all connected graphs on 10 vertices. Although distance-based matrices and combinations of several matrices lead to substantial improvements, they still leave non-isomorphic graphs that cannot be distinguished by the corresponding spectral or arithmetic invariants. This naturally motivates the search for new graph-associated matrices with stronger distinguishing power.
In this paper, we introduce the average flow matrix of a graph. The diagonal entries of this matrix are derived from the average sums of the lengths of simple paths from a vertex to all other vertices, while the off-diagonal entries are determined by the distance structure of the graph. We enumerate cospectral graphs with respect to the average flow matrix and compare the resulting counts with those obtained for other graph-associated matrices. Our results show that every connected graph of order at most 10 is determined by the spectrum of the average flow matrix. In particular, this provides a complete spectral characterization for connected graphs up to order 10 and offers further evidence that almost all graphs may be determined by suitably chosen spectral data.
The paper is organized as follows. § 2 contains the basic notation and terminology. § 3 reviews the related work. In § 4, we introduce the average flow matrix, coflow graphs, and some theoretical results. § 5 and § 6 present computational results. Finally, a conclusion is provided in § 7.
Preliminaries
Throughout this paper, we consider simple connected graphs. All paths are assumed to be simple unless stated otherwise.
Let be a graph, where and denote the vertex set and edge set of , respectively. The order and size of are denoted by and , respectively. For convenience, we write and . For a vertex , the degree of is denoted by , and its neighbourhood is defined by . A graph is called -regular if for every .
A simple path in is a sequence of distinct vertices in which every two consecutive vertices are adjacent. The length of a path is the number of edges it contains. For vertices , the set of all simple paths joining and is denoted by . The distance between and , denoted by , is the length of a shortest path joining them.
A graph is called a subgraph of if . Two graphs and are said to be isomorphic, denoted by , if there exists a bijection between their vertex sets that preserves adjacency. The complement of is denoted by . A tree is a connected graph containing no cycles.
The adjacency matrix of a graph on vertices is denoted by , where if and are adjacent, and otherwise.
Let denote the family of all connected graphs on vertices. For a real symmetric matrix , the largest eigenvalue and smallest eigenvalue of are denoted by and , respectively, and the trace of is denoted by . The spread of is defined by . The diagonal matrix with diagonal entries is denoted by . We use and to denote the identity matrix and the all-ones matrix of order , respectively. When the order is clear from the context, we simply write and . The all-ones vector of appropriate order is denoted by .
Related Work
A graph is said to be determined by the spectrum with respect to a given graph-associated matrix if no non-isomorphic graph shares the same spectrum with it. Spectral characterization problems of this kind have been studied for a variety of graph-associated matrices.
Harary and Read [9] gave one of the earliest enumerations of adjacency-cospectral graphs, determining the number of connected graphs on up to 7 vertices that have an adjacency-cospectral mate. The first major computational study in this direction is due to Godsil and McKay [4], who enumerated adjacency-cospectral graphs on up to 9 vertices. In 2004, Haemers and Spence [8] extended this line of work to the adjacency, Laplacian, and signless Laplacian matrices, and showed that the signless Laplacian matrix yields the best spectral discrimination among these three matrices. Let be a graph on vertices , and let be the degree matrix of . The Laplacian matrix and signless Laplacian matrix of are defined by and , respectively. Wilson and Zhu [15] later demonstrated that stronger discrimination can be obtained by combining several matrices simultaneously, namely the adjacency matrix , the Laplacian matrix , the signless Laplacian matrix , and the normalized Laplacian matrix , where .
Distance-based matrices have proved to be particularly effective in the enumeration of cospectral graphs. Let be a connected graph on vertices . The distance matrix of is . The transmission of a vertex is defined by , and the corresponding diagonal matrix is called the transmission matrix of . The distance Laplacian matrix and distance signless Laplacian matrix of are defined by and , respectively. Aouchiche and Hansen [2] compared the adjacency, Laplacian, signless Laplacian, distance, distance Laplacian, and distance signless Laplacian matrices, and showed that the distance-based matrices provide substantially better discrimination. More recently, Abiad and Alfaro [1] studied both cospectral and coinvariant graphs, and obtained further improvements by combining adjacency- and distance-based invariants.
The present work continues this line of investigation by introducing the average flow matrix and studying its effectiveness in the enumeration of cospectral graphs.
We now recall some standard constructions that produce cospectral graphs.
Construction 1 ([5], Godsil–McKay switching). Let be a graph with vertex set , and let be a partition of such that, for all and for every vertex , the following conditions hold:
for any , ;
the vertex is adjacent to either all, exactly half, or none of the vertices in .
The graph obtained from by Godsil–McKay switching is defined as follows: for each vertex , whenever is adjacent to exactly half of the vertices in some , we delete those edges and join instead to the other half of the vertices in .
Theorem 1 ([5]). Let be a graph, and let be a partition of satisfying the conditions of Godsil–McKay switching. Then the graph obtained from by Godsil–McKay switching is cospectral with , and their complements are also cospectral.
Example 1. Consider a regular graph , shown in Figure 1, with an even number of vertices. Add a new vertex to and join it to exactly half of the vertices, namely . Now construct a new graph by deleting all edges incident with and then joining to the other half of the vertices, namely . By Godsil–McKay switching, the graphs and are cospectral.
Figure 1. A pair of cospectral graphs obtained by Godsil–McKay switching.
Construction 2 ([5], Construction via congruent binary matrices). Let and be two matrices. We say that and are congruent if . Let be a graph on vertices, and let be an binary matrix. We define to be the graph with adjacency matrix
Theorem 2 ([5]). Let be a graph on vertices, and let and be binary congruent matrices of size . Then the graphs and are cospectral.
Let and be matrices of sizes and , respectively. Their tensor product is the matrix obtained by replacing each entry of by that entry multiplied by the entire matrix .
Construction 3 ([5], Tensor-product construction). Let and be cospectral graphs, and let and be binary square matrices of the same order. Then the graph with adjacency matrix
is cospectral with the graph having adjacency matrix
Construction 4 ([5], Tensor-product construction with complements). Let and be cospectral graphs such that their complements and are also cospectral. Let , , , and be binary square matrices of the same order. Then the graph with adjacency matrix
is cospectral with the graph having adjacency matrix
Lepović [10] presented numerical data for graphs on 10 vertices. Extending the computation results of Godsil and McKay Godsil and McKay [4], Haemers and Spence Haemers and Spence [8] enumerated graphs on 10 and 11 vertices that are cospectral with respect to the adjacency, Laplacian, and signless Laplacian matrices. They also constructed such cospectral graphs by formulating Godsil–McKay switching as an operation on certain matrices.
Theorem 3 (Haemers and Spence [8]). Let be a binary matrix of size , and let be the matrix obtained from by Godsil–McKay switching. Let be a symmetric matrix with constant row (and column) sums, and let be a symmetric matrix. Define
Then and are cospectral.
The result of Haemers and Spence Haemers and Spence [8] gives a useful matrix formulation of Godsil–McKay switching and makes it possible to apply the method in a broader setting. In the same paper, Haemers and Spence Haemers and Spence [8] used this point of view in their computational study of cospectral graphs. Since the number of graphs on 10 vertices is 11,716,571, the computation of cospectral graphs requires substantial time and memory. To deal with this, Haemers and Spence Haemers and Spence [8] exploited several necessary spectral conditions. For example, two graphs that are cospectral with respect to the adjacency matrix, and similarly with respect to the Laplacian matrix, must have the same number of edges. Moreover, adjacency-cospectral graphs must also have the same number of triangles. However, this is not true for Laplacian-cospectral graphs, as illustrated in Figure 2.
Figure 2. Laplacian-cospectral graphs with different numbers of triangles [8].
Brouwer and Spence Brouwer and Spence [3] enumerated adjacency-cospectral graphs on 12 vertices. They showed that the number of graphs having a cospectral mate initially increases and begins to decrease at 11 vertices. Wilson and Zhu Wilson and Zhu [15] enumerated cospectral graphs and trees with respect to the adjacency, Laplacian, signless Laplacian, and normalized Laplacian matrix of a graph , as well as their combinations.
In 2016, Haemers [7] conjectured that almost all graphs are determined by their spectrum. He supported this conjecture with the following observations:
The number of graphs having an adjacency-cospectral mate increases up to 10 vertices, but begins to decrease at 11 vertices [3].
(ii) Wang and Xu [14] considered the generalized spectrum, that is, the spectrum of a graph together with the spectrum of its complement. Their experimental results indicate that a large proportion of the graphs tested are determined by their generalized spectrum.
(iii) Wang [12, 13] defined a class of graphs, denoted by , and proved that every graph in is determined by its generalized spectrum. For a graph on vertices with adjacency matrix , the walk matrix is defined by
where denotes the all-ones vector. The class consists of all graphs for which
is an odd square-free integer, where denotes the determinant of .
Aouchiche and Hansen [2] enumerated graphs on 10 vertices that are cospectral with respect to the distance matrix, the distance Laplacian matrix, and the distance signless Laplacian matrix. They also showed that these enumeration results can be sharpened by considering two or three of these matrices simultaneously, that is, by counting the number of graphs that have a cospectral mate with respect to each matrix in the chosen combination. Their best result for graphs on 10 vertices was obtained by considering all three matrices together: only 7,622 graphs were found to have a cospectral mate with respect to . Examples of graphs of smallest order having cospectral mates with respect to the associated distance matrices are shown in Figure 3.
Figure 3. Cospectral graphs with respect to distance matrices and their combinations.
Abiad and Alfaro [1] enumerated cospectral and coinvariant graphs, that is, graphs having the same Smith normal form, for orders up to 10. Let be an integer matrix of rank . The Smith normal form of is the diagonal matrix
where each is a positive integer and divides for , obtained from by multiplication on the left and right by unimodular integer matrices. Two graphs are said to be coinvariant with respect to a graph-associated matrix if the corresponding matrices have the same Smith normal form. They showed that the Smith normal form is not a particularly effective invariant for the adjacency, Laplacian, and signless Laplacian matrices, but performs much better for distance-based matrices [1]. For example, on 10 vertices there are 787,851 graphs having a -cospectral mate, whereas only 642,002 graphs have a -coinvariant mate. Similarly, there are 319,324 graphs having a -cospectral mate, whereas only 264,955 graphs have a -coinvariant mate.
Following the approach in [15, 2], they further refined their enumeration by considering combinations of matrices. In [2], it was shown that there are 7,622 graphs on 10 vertices having a cospectral mate with respect to . In [1], it was shown that there are 7,490 graphs on 10 vertices having an adjacency-cospectral mate that is also a coinvariant mate with respect to and .
For ease of comparison, we use the following notation in Table 1. For a graph-associated matrix , let denote the family of connected graphs on vertices that have a cospectral mate with respect to , and let denote the family of connected graphs on vertices that have a coinvariant mate with respect to . More generally, for graph-associated matrices , let denote the family of connected graphs on vertices having a common cospectral mate with respect to each of the matrices . Mixed notation is interpreted componentwise; for example, denotes the family of connected graphs on vertices having a mate that is cospectral with respect to and coinvariant with respect to . The enumeration results from the articles discussed above are summarized in Table 1.
| References | Family | 5 | 6 | 7 | 8 | 9 | 10 |
| 21 | 112 | 853 | 11,117 | 261,080 | 11,716,571 | ||
| [9] | 0 | 2 | 63 | NA | NA | NA | |
| [4] | 0 | 2 | 63 | 1,353 | 46,930 | NA | |
| 0 | 2 | 63 | 1,353 | 46,930 | 2,462,141 | ||
| [8] | 0 | 4 | 115 | 1,611 | 40,560 | 1,367,215 | |
| 2 | 10 | 80 | 1,047 | 17,627 | 615,919 | ||
| 0 | 0 | 0 | 0 | 82 | 13,864 | ||
| 0 | 0 | 16 | 232 | 4,139 | 107,835 | ||
| [15] | 0 | 0 | 0 | 0 | 8 | 10,716 | |
| 0 | 0 | 0 | 6 | 14 | 10,281 | ||
| 0 | 0 | 0 | 0 | 6 | 10,256 | ||
| 0 | 0 | 0 | 0 | 2 | 10,124 | ||
| 0 | 0 | 22 | 658 | 25,058 | 1,389,986 | ||
| 0 | 0 | 43 | 745 | 20,455 | 787,851 | ||
| [2] | 2 | 6 | 38 | 453 | 8,168 | 319,324 | |
| 0 | 0 | 0 | 0 | 32 | 9,449 | ||
| 0 | 0 | 0 | 0 | 0 | 7,712 | ||
| 0 | 0 | 0 | 90 | 1,965 | 61,909 | ||
| 0 | 0 | 0 | 0 | 0 | 7,622 | ||
| 20 | 112 | 853 | 11,117 | 261,080 | 11,716,571 | ||
| 8 | 57 | 526 | 8,027 | 221,834 | 11,036,261 | ||
| 11 | 78 | 620 | 7,962 | 201,282 | 10,086,812 | ||
| [1] | 15 | 102 | 835 | 11,080 | 260,991 | 11,716,249 | |
| 0 | 0 | 18 | 455 | 16,505 | 642,002 | ||
| 2 | 4 | 20 | 259 | 7,444 | 264,955 | ||
| 0 | 0 | 0 | 32 | 1,770 | 92,915 | ||
| 0 | 0 | 0 | 20 | 432 | 24,517 | ||
| 0 | 0 | 0 | 44 | 1,447 | 46,239 | ||
| 0 | 0 | 0 | 0 | 32 | 9,253 | ||
| 0 | 0 | 0 | 0 | 32 | 8,935 | ||
| 0 | 0 | 0 | 0 | 2 | 7,688 | ||
| 0 | 0 | 0 | 0 | 0 | 7,646 | ||
| 0 | 0 | 0 | 0 | 138 | 12,246 | ||
| 0 | 0 | 0 | 0 | 32 | 8,743 | ||
| 0 | 0 | 0 | 0 | 0 | 7,550 | ||
| 0 | 0 | 0 | 0 | 0 | 7,490 | ||
| 0 | 0 | 0 | 0 | 0 | 7,510 |
Table 1. Number of graphs having a cospectral or coinvariant mate for various families of connected graphs.
Table 1 shows that the use of several matrices together substantially reduces the number of graphs having a cospectral or coinvariant mate. In particular, the strongest reductions are obtained when distance-based matrices are combined with additional spectral or arithmetic information. Nevertheless, even these refinements still leave a nontrivial number of unresolved cases. This naturally leads to the search for other graph-associated matrices with stronger distinguishing power, which motivates the study undertaken in the present paper.
The Average Flow Matrix of a Graph
We study graph-associated matrices and their spectra in order to improve the enumeration of cospectral graphs. Existing results indicate that stronger spectral discrimination is often achieved by incorporating richer structural information into the associated matrix [1, 2, 8, 4]. For instance, the Laplacian matrix [8] distinguishes more graphs than the adjacency matrix [4], since it reflects both adjacency and degree information. Similarly, the distance matrix [2] outperforms both the adjacency and the Laplacian matrices [2, 8], as it encodes the pairwise distances between vertices. Furthermore, the distance Laplacian and distance signless Laplacian matrices [2] provide an additional improvement over the distance matrix. Motivated by these observations, we introduce the average flow matrix of a graph, which augments the negative distance matrix with a vertex-wise quantity measuring the average length of all simple paths originating at each vertex.
Let be a connected graph with vertex set , and let . For each vertex , let denote the set of all simple paths from to . The average flow of , denoted by , is defined by
where denotes the length of the path . Thus, is the total length of all simple paths from to all other vertices, divided by the total number of such paths. Since is finite, each set is finite and nonempty, and therefore is a well-defined positive rational number. Moreover, is invariant under graph isomorphism.
Using these vertex average flows, we define the associated matrix as follows. The average flow matrix of is the symmetric matrix given by
where denotes the length of a shortest path between and in . Equivalently,
where is the distance matrix of . Figure 4 illustrates a graph together with its average flow matrix .

Figure 4. A graph together with its average flow matrix . The diagonal entries are rounded to four decimal places.
We next establish a simple relationship between the distance spectrum of a graph and the spectrum of its average flow matrix. We say that a graph is flow-stable if all its vertices have the same average flow, that is,
Proposition 1. Let be a flow-stable graph of order , let denote the common average flow of its vertices, and let be its distance matrix with distance spectrum , listed with multiplicities. Then the average flow matrix has spectrum
with the same multiplicities. Moreover, and have the same eigenvectors.
Proof. Since is flow-stable, every diagonal entry of equals . Hence, by (2),
If is an eigenvector of corresponding to the eigenvalue , then
Therefore, is an eigenvector of corresponding to the eigenvalue . It follows that the spectrum of is , with the same multiplicities, and that and have the same eigenvectors.
As a direct application of Proposition 1, we obtain the following corollary for vertex-transitive graphs.
Corollary 1. Every vertex-transitive graph is flow-stable. Consequently, if is a vertex-transitive graph with common average flow and distance spectrum , then the spectrum of its average flow matrix is .
Proof. If is vertex-transitive, then for any two vertices there exists an automorphism of mapping to . Since is invariant under graph automorphisms, it follows that all vertices of have the same average flow. Hence is flow-stable, and the conclusion follows from Proposition 1.
We now determine the spectrum of the average flow matrix of the complete graph .
Proposition 2. Let be the complete graph on vertices, and let denote the common average flow of its vertices. Then
In particular, the largest eigenvalue of is
Proof. Since is vertex-transitive, it is flow-stable, and hence every diagonal entry of equals . Moreover, every pair of distinct vertices in is adjacent, so whenever . Therefore,
It is well known that
By Proposition 1, it follows that
Since , we have , and therefore
Corollary 2. Let denote the largest eigenvalue of the average flow matrix of . If , then
Proof. By Proposition 2,
The conclusion follows immediately from the bound .
Coflow Graphs
Enumerating cospectral graphs of larger order is computationally demanding because the number of connected graphs grows rapidly with the number of vertices. For example, there are 11,716,571 connected graphs on 10 vertices. A direct pairwise spectral comparison over such a large collection is prohibitively expensive on standard hardware. To reduce the search space, we first identify a larger class of graphs that necessarily contains all cospectral pairs.
For a connected graph , we define its average flow sum by
Two graphs are said to be coflow mates if they have the same average flow sum. Equivalently, graphs with the same value of belong to the same coflow class.
Since the diagonal entries of the average flow matrix are precisely the vertex average flows, we have
Moreover, the trace of a square matrix is equal to the sum of its eigenvalues. It follows that if two graphs are cospectral with respect to the average flow matrix, then they must have the same average flow sum. Therefore,
Thus, coflow classes provide a natural and efficient first filter in the enumeration of cospectral graphs.
We enumerated the connected graphs belonging to non-singleton coflow classes for all orders up to 10. The results are presented in Table 2. Only a small fraction of connected graphs have a coflow mate; for example, among the 11,716,571 connected graphs on 10 vertices, only 730,276 belong to non-singleton coflow classes, which is approximately 6.23%.
| # connected graphs | 21 | 112 | 853 | 11,117 | 261,080 | 11,716,571 |
| # coflow graphs | 0 | 8 | 13 | 63 | 737 | 730,276 |
Table 2. Connected graphs belonging to non-singleton coflow classes on up to 10 vertices.
Remark 1. Coflow mates need not have the same number of edges. The graphs shown in Figure 5 form the smallest such pair.
Figure 5. A pair of coflow graphs with different numbers of edges.
Cominimal and Comaximal Graphs
Two graphs are said to be cominimal if they share the same least eigenvalue of the average flow matrix. Similarly, two graphs are said to be comaximal if they share the same largest eigenvalue. Since cospectral graphs necessarily have the same minimum and maximum eigenvalues, the classes of cominimal and comaximal graphs provide natural filters for the enumeration of cospectral graphs.
We therefore enumerate, for each order , the connected graphs having at least one cominimal mate and the connected graphs having at least one comaximal mate. The resulting fractions are summarized in Table 3. The proportion of graphs having a cominimal mate varies substantially with : it is approximately 23% for , increases slightly to 28% for , and then decreases to 24.73%, 16.92%, and 10.32% for , respectively, as shown in Figure 7a. On 10 vertices, however, this fraction rises sharply to approximately 65.62%.
| Cominimal | Comaximal | Coflow + Cominimal | Coflow + Comaximal | |
| 5 | 0.2300 | 0 | – | 0 |
| 6 | 0.2800 | 0 | 0.0178 | 0 |
| 7 | 0.2473 | 0 | 0.0023 | 0 |
| 8 | 0.1692 | 0.0001 | 0.0025 | 0 |
| 9 | 0.1032 | 0.0012 | 0.0009 | 0 |
| 10 | 0.6562 | 0.0523 | 0.0001 | 0 |
Table 3. Fractions of connected graphs having a cominimal mate, a comaximal mate, and additional coflow constraints.

Figure 7. Fractions of graphs having a cominimal mate or a comaximal mate on vertices.
By contrast, very few graphs have a comaximal mate. Up to 7 vertices, no connected graph has a comaximal mate. On 8, 9, and 10 vertices, the corresponding fractions are approximately 0.01%, 0.12%, and 5.23%, respectively, as shown in Figure 7b. Figure 6b shows that the number of comaximal graphs increases rapidly at .

Figure 6. (a) Number of cominimal graphs on vertices.

Figure 6b. (b) Number of comaximal graphs on vertices.

Figure 6 (PDF p. 11). Numbers of cominimal and comaximal graphs on vertices.

Figure 7a. (a) Fraction of cominimal graphs on vertices.

Figure 7b. (b) Fraction of comaximal graphs on vertices.
Although cominimality and comaximality provide valid spectral filters, they are not by themselves sufficiently restrictive for the final cospectral search. For instance, on 10 vertices there are 7,688,945 connected graphs having a cominimal mate and 613,212 having a comaximal mate, leaving a search space that is still computationally large.
We therefore combine these filters with the coflow condition introduced in § 4.1. Since cospectral graphs must be coflow, cominimal, and comaximal, it is natural to examine the intersections of these classes. The results show that the fraction of coflow graphs that also have a cominimal mate decreases substantially for larger : it is 1.78% on 6 vertices, 0.23% on 7 vertices, approximately 0.25% for , 0.09% for , and only 0.01% for , as shown in Figure 10a. Moreover, up to 10 vertices, no coflow graph has a comaximal mate, as shown in Figure 10b.
These observations indicate that the coflow condition is considerably more effective than the extremal-eigenvalue filters in reducing the search space. Consequently, it is computationally preferable to first restrict attention to coflow classes and then, if necessary, refine the search further using comaximality.
Figure 8. The unique pair of comaximal graphs on 8 vertices.

(a) (a) Number of cominimal graphs among coflow graphs on vertices.

(b) (b) Number of comaximal graphs among coflow graphs on vertices.
Figure 9. Cominimal and comaximal graphs among coflow graphs on vertices.

(a) (a) Fraction of cominimal graphs among coflow graphs on vertices.

(b) (b) Fraction of comaximal graphs among coflow graphs on vertices.
Figure 10. Fractions of coflow graphs that are also cominimal or comaximal on vertices.
Enumeration Results
We now present the main enumeration results for the average flow matrix and compare them with the best previously reported results for other graph-associated matrices. Godsil and McKay [Godsil and McKay [4] enumerated cospectral graphs with respect to the adjacency matrix for graphs on up to 9 vertices. Haemers and Spence [Haemers and Spence [8] extended this line of work to the matrices , , and , obtaining the strongest results for . Wilson and Zhu [Wilson and Zhu [15] showed that improved enumeration can be achieved by considering several matrices simultaneously, namely , , , and . Aouchiche and Hansen [Aouchiche and Hansen [2] further improved the enumeration results by considering the distance-associated matrices , , and . More recently, Abiad and Alfaro [1] studied cospectral and coinvariant graphs, and showed that additional improvement can be obtained by combining adjacency- and distance-based invariants.
For each , we generated all connected graphs on vertices and computed their average flow matrices. We restricted the enumeration to connected graphs on at most 10 vertices because the number of connected graphs grows extremely rapidly with , making exhaustive spectral comparisons beyond this range computationally prohibitive on standard hardware. To reduce the computational cost of exhaustive pairwise spectral comparisons, we first partitioned the graphs into coflow classes, since two graphs can be cospectral with respect to only if they have the same average flow sum. We then used the largest eigenvalue as an additional filter, retaining only those graphs that were both coflow and comaximal. Finally, for the remaining candidates, we compared the full spectra of their average flow matrices numerically in order to identify cospectral mates.
All computations were performed on a machine equipped with an Intel® Core™ i5-8365U CPU @ 1.60 GHz, 8.00 GB RAM, a 64-bit operating system, and Python 3.11. The eigenvalues were computed numerically using 7-digit precision, so that the resulting counts are directly comparable with those reported in the existing literature. The results are summarized in Table 4.
Table 4. Number of connected graphs that have a cospectral or cospectral-coinvariant mate with respect to various graph-associated matrices.
Table 4 shows that, among the graph-associated matrices considered so far in the literature, the average flow matrix provides the strongest spectral discrimination on connected graphs with up to 10 vertices. In particular, within the adopted numerical precision, our computations yielded no connected graph on at most 10 vertices having a cospectral mate with respect to . This improves upon all previously reported results listed in Table 4, for which nontrivial cospectral classes still remain at order 10.
Conclusions
In this paper, we introduced the average flow matrix, a new graph-associated matrix that combines the average lengths of all simple paths originating at each vertex with the pairwise shortest-path distances between vertices. The primary aim of this work was to assess the effectiveness of this matrix in the enumeration of cospectral graphs.
In addition, we established several supporting properties of the average flow matrix, including its behavior on flow-stable graphs and complete graphs, and introduced the notions of coflow, coniminal, and comaximal graphs as natural spectral filters. While these results are primarily supportive in nature, they help clarify the structure of the matrix and provide useful tools for the computational analysis.
The main contribution of the paper is computational. We carried out an exhaustive enumeration of connected graphs on up to 10 vertices and, within the adopted numerical precision, found no connected graph having a cospectral mate with respect to the average flow matrix. In this sense, the average flow matrix provides stronger spectral discrimination on this range than the graph-associated matrices considered in the existing literature, including those studied by Godsil and McKay [Godsil and McKay [4], Haemers and Spence [Haemers and Spence [8], Wilson and Zhu [Wilson and Zhu [15], Aouchiche and Hansen [Aouchiche and Hansen [2], and Abiad and Alfaro [Abiad and Alfaro [1]. In particular, it improves on the best previously reported enumeration results, all of which still leave nontrivial cospectral classes at order 10.
Our experiments also yield several useful observations about the search space. Among the filters considered in this paper, the coflow condition provides the strongest reduction, while comaximality offers a useful secondary refinement and cominimality is comparatively less effective. These observations suggest that the average flow sum captures a substantial amount of spectral information and is particularly valuable in large-scale enumeration.
The restriction to graphs on at most 10 vertices reflects the rapid growth in the number of connected graphs and the resulting computational cost of exhaustive spectral comparison. Several directions for future work remain open. It would be natural to extend the enumeration beyond 10 vertices using improved filtering strategies or greater computational resources, and to investigate exact verification methods for cospectrality with respect to the average flow matrix. Another interesting direction is to study how the matrix behaves on important graph classes such as trees, distance-regular graphs, and other highly symmetric families. A more detailed analysis of coflow, cominimal, and comaximal classes may also help explain why the average flow matrix performs so well in practice.
References
- [1][Abiad and Alfaro(2021)] Abiad, A., Alfaro, C., 2021. Enumeration of cospectral and coinvariant graphs. Applied Mathematics and Computation 408, 126–348.
- [2][Aouchiche and Hansen(2018)] Aouchiche, M., Hansen, P., 2018. Cospectrality of graphs with respect to distance matrices. Applied Mathematics and Computation 325, 309–321.DOI
- [3][Brouwer and Spence(2009)] Brouwer, A., Spence, E., 2009. Cospectral graphs on 12 vertices. The Electronic Journal of Combinatorics, N20.DOI
- [4][Godsil and McKay(1976)] Godsil, C., McKay, B., 1976. Some computational results on the spectra of graphs, in: Combinatorial Mathematics IV: Proceedings of the Fourth Australian Conference, University of Adelaide, August 27–29, 1975, Springer. pp. 73–92.DOI
- [5][Godsil and McKay(1982)] Godsil, C., McKay, B., 1982. Constructing cospectral graphs. Aequationes Mathematicae 25, 257–268.DOI
- [6][Günthard and Primas(1956)] Günthard, H., Primas, H., 1956. Zusammenhang von graphentheorie und MO-theorie von molekeln mit systemen konjugierter bindungen. Helvetica Chimica Acta 39, 1645–1653.
- [7][Haemers(2016)] Haemers, W., 2016. Are almost all graphs determined by their spectrum. Notes of the South African Mathematical Society 47, 42–45.
- [8][Haemers and Spence(2004)] Haemers, W., Spence, E., 2004. Enumeration of cospectral graphs. European Journal of Combinatorics 25, 199–211.
- [9][Harary and Read(1971)] Harary, F., K.C.M.A., Read, R., 1971. Cospectral graphs and digraphs. Bulletin of the London Mathematical Society 3, 321–328.DOI
- [10][Lepović(1998)] Lepović, M., 1998. Some statistical data on graphs with 10 vertices. Publikacije Elektrotehničkog Fakulteta. Serija Matematika , 79–88.
- [11][Van Dam and Haemers(2003)] Van Dam, E., Haemers, W., 2003. Which graphs are determined by their spectrum? Linear Algebra and its Applications 373, 241–272.
- [12][Wang(2013)] Wang, W., 2013. Generalized spectral characterization of graphs: revisited. arXiv preprint arXiv:1309.6090.arxiv.org/abs/1309.6090
- [13][Wang(2017)] Wang, W., 2017. A simple arithmetic criterion for graphs being determined by their generalized spectra. Journal of Combinatorial Theory, Series B 122, 438–451.
- [14][Wang and Cheng-Xian(2006)] Wang, W., Cheng-Xian, X., 2006. An excluding algorithm for testing whether a family of graphs are determined by their generalized spectra. Linear Algebra and its Applications 418, 62–74.
- [15][Wilson and Zhu(2008)] Wilson, R., Zhu, P., 2008. A study of graph spectra for comparing graphs and trees. Pattern Recognition 41, 2833–2841.




