betaFeedback

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 G=(V(G),E(G))G=(V(G),E(G)) be a graph, where V(G)V(G) and E(G)E(G) denote the vertex set and edge set of GG, respectively. The order and size of GG are denoted by ∣V(G)∣\lvert V(G)\rvert and ∣E(G)∣\lvert E(G)\rvert, respectively. For convenience, we write n=∣V(G)∣n=\lvert V(G)\rvert and m=∣E(G)∣m=\lvert E(G)\rvert. For a vertex v∈V(G)v\in V(G), the degree of vv is denoted by dG(v)d_G(v), and its neighbourhood is defined by NG(v)={u∈V(G):uv∈E(G)}N_G(v)=\{u\in V(G):uv\in E(G)\}. A graph GG is called rr-regular if dG(v)=rd_G(v)=r for every v∈V(G)v\in V(G).

A simple path in GG 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 u,v∈V(G)u,v\in V(G), the set of all simple paths joining uu and vv is denoted by P(u,v)\mathcal{P}(u,v). The distance between uu and vv, denoted by dG(u,v)d_G(u,v), is the length of a shortest path joining them.

A graph HH is called a subgraph of GG if H⊆GH\subseteq G. Two graphs GG and HH are said to be isomorphic, denoted by G≅HG\cong H, if there exists a bijection between their vertex sets that preserves adjacency. The complement of GG is denoted by G‾\overline{G}. A tree is a connected graph containing no cycles.

The adjacency matrix of a graph GG on vertices v1,v2,…,vnv_1,v_2,\ldots,v_n is denoted by A(G)=(aij)A(G)=(a_{ij}), where aij=1a_{ij}=1 if viv_i and vjv_j are adjacent, and aij=0a_{ij}=0 otherwise.

Let Gn\mathcal{G}_n denote the family of all connected graphs on nn vertices. For a real symmetric matrix MM, the largest eigenvalue and smallest eigenvalue of MM are denoted by λmax⁡(M)\lambda_{\max}(M) and λmin⁡(M)\lambda_{\min}(M), respectively, and the trace of MM is denoted by tr⁡(M)\operatorname{tr}(M). The spread of MM is defined by λmax⁡(M)−λmin⁡(M)\lambda_{\max}(M)-\lambda_{\min}(M). The diagonal matrix with diagonal entries ℓ1,ℓ2,…,ℓn\ell_1,\ell_2,\ldots,\ell_n is denoted by diag⁡(ℓ1,ℓ2,…,ℓn)\operatorname{diag}(\ell_1,\ell_2,\ldots,\ell_n). We use InI_n and JnJ_n to denote the identity matrix and the all-ones matrix of order nn, respectively. When the order is clear from the context, we simply write II and JJ. The all-ones vector of appropriate order is denoted by 11.

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 GG be a graph on vertices v1,v2,…,vnv_1,v_2,\ldots,v_n, and let Δ(G)=diag⁡(dG(v1),dG(v2),…,dG(vn))\Delta(G)=\operatorname{diag}(d_G(v_1),d_G(v_2),\ldots,d_G(v_n)) be the degree matrix of GG. The Laplacian matrix and signless Laplacian matrix of GG are defined by L(G)=Δ(G)−A(G)L(G)=\Delta(G)-A(G) and Q(G)=Δ(G)+A(G)Q(G)=\Delta(G)+A(G), respectively. Wilson and Zhu [15] later demonstrated that stronger discrimination can be obtained by combining several matrices simultaneously, namely the adjacency matrix AA, the Laplacian matrix LL, the signless Laplacian matrix QQ, and the normalized Laplacian matrix L~\widetilde{L}, where L~(G)=I−Δ(G)−1/2A(G)Δ(G)−1/2\widetilde{L}(G)=I-\Delta(G)^{-1/2}A(G)\Delta(G)^{-1/2}.

Distance-based matrices have proved to be particularly effective in the enumeration of cospectral graphs. Let GG be a connected graph on vertices v1,v2,…,vnv_1,v_2,\ldots,v_n. The distance matrix of GG is D(G)=(dG(vi,vj))i,j=1nD(G)=\left(d_G(v_i,v_j)\right)_{i,j=1}^{n}. The transmission of a vertex viv_i is defined by Tr⁡(vi)=∑j=1ndG(vi,vj)\operatorname{Tr}(v_i)=\sum_{j=1}^{n}d_G(v_i,v_j), and the corresponding diagonal matrix Tr⁡(G)=diag⁡(Tr⁡(v1),Tr⁡(v2),…,Tr⁡(vn))\operatorname{Tr}(G)=\operatorname{diag}(\operatorname{Tr}(v_1),\operatorname{Tr}(v_2),\ldots,\operatorname{Tr}(v_n)) is called the transmission matrix of GG. The distance Laplacian matrix and distance signless Laplacian matrix of GG are defined by DL(G)=Tr⁡(G)−D(G)D^{L}(G)=\operatorname{Tr}(G)-D(G) and DQ(G)=Tr⁡(G)+D(G)D^{Q}(G)=\operatorname{Tr}(G)+D(G), 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 GG be a graph with vertex set V(G)V(G), and let ϕ=(C1,C2,…,Ck,D)\phi=(C_1,C_2,\ldots,C_k,D) be a partition of V(G)V(G) such that, for all 1≤i,j≤k1\le i,j\le k and for every vertex v∈Dv\in D, the following conditions hold:

  1. for any vi,vj∈Civ_i,v_j\in C_i, ∣NCj(vi)∣=∣NCj(vj)∣\lvert N_{C_j}(v_i)\rvert=\lvert N_{C_j}(v_j)\rvert;

  1. the vertex vv is adjacent to either all, exactly half, or none of the vertices in CiC_i.

The graph G′G' obtained from GG by Godsil–McKay switching is defined as follows: for each vertex v∈Dv\in D, whenever vv is adjacent to exactly half of the vertices in some CiC_i, we delete those edges and join vv instead to the other half of the vertices in CiC_i.

Theorem 1 ([5]). Let GG be a graph, and let ϕ\phi be a partition of V(G)V(G) satisfying the conditions of Godsil–McKay switching. Then the graph G′G' obtained from GG by Godsil–McKay switching is cospectral with GG, and their complements are also cospectral.

Example 1. Consider a regular graph GG, shown in Figure 1, with an even number of vertices. Add a new vertex vv to GG and join it to exactly half of the vertices, namely {w1,w2,w3,w4,w5}\{w_1,w_2,w_3,w_4,w_5\}. Now construct a new graph G′G' by deleting all edges incident with vv and then joining vv to the other half of the vertices, namely {v1,v2,v3,v4,v5}\{v_1,v_2,v_3,v_4,v_5\}. By Godsil–McKay switching, the graphs GG and G′G' are cospectral.

Figure 1. A pair of cospectral graphs obtained by Godsil–McKay switching.

Construction 2 ([5], Construction via congruent binary matrices). Let A1A_1 and A2A_2 be two matrices. We say that A1A_1 and A2A_2 are congruent if A1TA1=A2TA2A_1^{T}A_1=A_2^{T}A_2. Let GG be a graph on nn vertices, and let KK be an m×nm\times n binary matrix. We define G(K)G(K) to be the graph with adjacency matrix

[0KKTA(G)]\begin{bmatrix} 0 & K \\ K^{T} & A(G) \end{bmatrix}

Theorem 2 ([5]). Let HH be a graph on nn vertices, and let AA and BB be binary congruent matrices of size m×nm \times n. Then the graphs H(A)H(A) and H(B)H(B) are cospectral.

Let AA and BB be matrices of sizes m×nm \times n and ℓ×k\ell\times k, respectively. Their tensor product A⊗BA \otimes B is the (mℓ)×(nk)(m\ell) \times(nk) matrix obtained by replacing each entry of AA by that entry multiplied by the entire matrix BB.

Construction 3 ([5], Tensor-product construction). Let G1G_1 and G2G_2 be cospectral graphs, and let XX and HH be binary square matrices of the same order. Then the graph with adjacency matrix

H⊗I+X⊗A(G1)H \otimes I + X \otimes A(G_1)

is cospectral with the graph having adjacency matrix

H⊗I+X⊗A(G2).H \otimes I + X \otimes A(G_2).

Construction 4 ([5], Tensor-product construction with complements). Let G1G_1 and G2G_2 be cospectral graphs such that their complements G1‾\overline{G_1} and G2‾\overline{G_2} are also cospectral. Let A1A_1, A2A_2, A3A_3, and A4A_4 be binary square matrices of the same order. Then the graph with adjacency matrix

A1⊗I+A2⊗J+A3⊗A(G1)+A4⊗A(G1‾)A_1 \otimes I + A_2 \otimes J + A_3 \otimes A(G_1) + A_4 \otimes A(\overline{G_1})

is cospectral with the graph having adjacency matrix

A1⊗I+A2⊗J+A3⊗A(G2)+A4⊗A(G2‾).A_1 \otimes I + A_2 \otimes J + A_3 \otimes A(G_2) + A_4 \otimes A(\overline{G_2}).

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 NN be a binary matrix of size b×cb \times c, and let N~\widetilde{N} be the matrix obtained from NN by Godsil–McKay switching. Let BB be a symmetric b×bb \times b matrix with constant row (and column) sums, and let CC be a symmetric c×cc \times c matrix. Define

M=[BNNTC]M~=[BN~N~TC].M = \begin{bmatrix} B & N \\ N^{T} & C \end{bmatrix} \qquad \widetilde{M} = \begin{bmatrix} B & \widetilde{N} \\ \widetilde{N}^{T} & C \end{bmatrix}.

Then MM and M~\widetilde{M} 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 L~\widetilde{L} of a graph GG, 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:

  1. 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 GG 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 F\mathcal{F}, and proved that every graph in F\mathcal{F} is determined by its generalized spectrum. For a graph GG on nn vertices with adjacency matrix AA, the walk matrix WW is defined by

W=[1,A1,A21,…,An−11],W = [\mathbf{1}, A\mathbf{1}, A^{2}\mathbf{1}, \ldots, A^{n-1}\mathbf{1}],

where 1\mathbf{1} denotes the all-ones vector. The class F\mathcal{F} consists of all graphs for which

det⁡(W)2⌊n/2⌋\frac{\det(W)}{2^{\lfloor n/2 \rfloor}}

is an odd square-free integer, where det⁡(W)\det(W) denotes the determinant of WW.

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 (D,DL,DQ)(D, D^{L}, D^{Q}). 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 MM be an integer matrix of rank rr. The Smith normal form of MM is the diagonal matrix

diag⁡(d1,d2,…,dr,0,…,0),\operatorname{diag}(d_{1}, d_{2}, \ldots, d_{r}, 0, \ldots, 0),

where each did_i is a positive integer and did_i divides di+1d_{i+1} for 1≤i<r1 \leq i < r, obtained from MM 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 DLD^{L}-cospectral mate, whereas only 642,002 graphs have a DLD^{L}-coinvariant mate. Similarly, there are 319,324 graphs having a DQD^{Q}-cospectral mate, whereas only 264,955 graphs have a DQD^{Q}-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 (D,DL,DQ)(D, D^{L}, D^{Q}). 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 DLD^{L} and DQD^{Q}.

For ease of comparison, we use the following notation in Table 1. For a graph-associated matrix MM, let Cncs(M)\mathcal{C}^{\mathrm{cs}}_n(M) denote the family of connected graphs on nn vertices that have a cospectral mate with respect to MM, and let Cnci(M)\mathcal{C}^{\mathrm{ci}}_n(M) denote the family of connected graphs on nn vertices that have a coinvariant mate with respect to MM. More generally, for graph-associated matrices M1,M2,…,MkM_1,M_2,\ldots,M_k, let Cncs(M1,M2,…,Mk)\mathcal{C}^{\mathrm{cs}}_n(M_1,M_2,\ldots,M_k) denote the family of connected graphs on nn vertices having a common cospectral mate with respect to each of the matrices M1,M2,…,MkM_1,M_2,\ldots,M_k. Mixed notation is interpreted componentwise; for example, Cncs-ci(M1,M2)\mathcal{C}^{\mathrm{cs\text{-}ci}}_n(M_1,M_2) denotes the family of connected graphs on nn vertices having a mate that is cospectral with respect to M1M_1 and coinvariant with respect to M2M_2. The enumeration results from the articles discussed above are summarized in Table 1.

ReferencesFamily5678910
Gn\mathcal{G}_n2111285311,117261,08011,716,571
[9]Gncs(A)\mathcal{G}^{cs}_n(A)0263NANANA
[4]Gncs(A)\mathcal{G}^{cs}_n(A)02631,35346,930NA
Gncs(A)\mathcal{G}^{cs}_n(A)02631,35346,9302,462,141
[8]Gncs(L)\mathcal{G}^{cs}_n(L)041151,61140,5601,367,215
Gncs(Q)\mathcal{G}^{cs}_n(Q)210801,04717,627615,919
Gncs(A,L)\mathcal{G}^{cs}_n(A,L)00008213,864
Gncs(L,Q)\mathcal{G}^{cs}_n(L,Q)00162324,139107,835
[15]Gncs(A,Q)\mathcal{G}^{cs}_n(A,Q)0000810,716
Gncs(A,L~)\mathcal{G}^{cs}_n(A,\widetilde{L})00061410,281
Gncs(L,L~)\mathcal{G}^{cs}_n(L,\widetilde{L})0000610,256
Gncs(A,L,Q,L~)\mathcal{G}^{cs}_n(A,L,Q,\widetilde{L})0000210,124
Gncs(D)\mathcal{G}^{cs}_n(D)002265825,0581,389,986
Gncs(DL)\mathcal{G}^{cs}_n(D^L)004374520,455787,851
[2]Gncs(DQ)\mathcal{G}^{cs}_n(D^Q)26384538,168319,324
Gncs(D,DL)\mathcal{G}^{cs}_n(D,D^L)0000329,449
Gncs(D,DQ)\mathcal{G}^{cs}_n(D,D^Q)000007,712
Gncs(DL,DQ)\mathcal{G}^{cs}_n(D^L,D^Q)000901,96561,909
Gncs(D,DL,DQ)\mathcal{G}^{cs}_n(D,D^L,D^Q)000007,622
Gnin(A)\mathcal{G}^{in}_n(A)2011285311,117261,08011,716,571
Gnin(L)\mathcal{G}^{in}_n(L)8575268,027221,83411,036,261
Gnin(Q)\mathcal{G}^{in}_n(Q)11786207,962201,28210,086,812
[1]Gnin(D)\mathcal{G}^{in}_n(D)1510283511,080260,99111,716,249
Gnin(DL)\mathcal{G}^{in}_n(D^L)001845516,505642,002
Gnin(DQ)\mathcal{G}^{in}_n(D^Q)24202597,444264,955
Gnin(D,DL)\mathcal{G}^{in}_n(D,D^L)000321,77092,915
Gnin(D,DQ)\mathcal{G}^{in}_n(D,D^Q)0002043224,517
Gnin(DL,DQ)\mathcal{G}^{in}_n(D^L,D^Q)000441,44746,239
Gncs−in(A,DL)\mathcal{G}^{cs-in}_n(A,D^L)0000329,253
Gncs−in(D,DL)\mathcal{G}^{cs-in}_n(D,D^L)0000328,935
Gncs−in(A,DQ)\mathcal{G}^{cs-in}_n(A,D^Q)000027,688
Gncs−in(D,DQ)\mathcal{G}^{cs-in}_n(D,D^Q)000007,646
Gnin(D,DL,DQ)\mathcal{G}^{in}_n(D,D^L,D^Q)000013812,246
Gncs−cs−in(A,D,DL)\mathcal{G}^{cs-cs-in}_n(A,D,D^L)0000328,743
Gncs−cs−in(A,D,DQ)\mathcal{G}^{cs-cs-in}_n(A,D,D^Q)000007,550
Gncs−in−in(A,DQ,DL)\mathcal{G}^{cs-in-in}_n(A,D^Q,D^L)000007,490
Gncs−in−in(D,DL,DQ)\mathcal{G}^{cs-in-in}_n(D,D^L,D^Q)000007,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 GG be a connected graph with vertex set V(G)={v1,…,vn}V(G)=\{v_1,\ldots,v_n\}, and let v∈V(G)v\in V(G). For each vertex u≠vu\ne v, let P(v,u)\mathcal{P}(v,u) denote the set of all simple paths from vv to uu. The average flow of vv, denoted by fl⁡(v)\operatorname{fl}(v), is defined by

fl⁡(v)≜∑u≠v∑P∈P(v,u)∣P∣pv,pv=∑u≠v∣P(v,u)∣,(1)\operatorname{fl}(v) \triangleq\frac{\sum_{u\ne v}\sum_{P\in\mathcal{P}(v,u)}|P|}{p_v}, \qquad p_v=\sum_{u\ne v}|\mathcal{P}(v,u)|, \tag*{(1)}

where ∣P∣|P| denotes the length of the path PP. Thus, fl⁡(v)\operatorname{fl}(v) is the total length of all simple paths from vv to all other vertices, divided by the total number pvp_v of such paths. Since GG is finite, each set P(v,u)\mathcal{P}(v,u) is finite and nonempty, and therefore fl⁡(v)\operatorname{fl}(v) is a well-defined positive rational number. Moreover, fl⁡(v)\operatorname{fl}(v) is invariant under graph isomorphism.

Using these vertex average flows, we define the associated matrix as follows. The average flow matrix F(G)=[aij]F(G)=[a_{ij}] of GG is the n×nn\times n symmetric matrix given by

aii=fl⁡(vi),aij=−dist⁡G(vi,vj)(i≠j),(2)a_{ii}=\operatorname{fl}(v_i), \qquad a_{ij}=-\operatorname{dist}_{G}(v_i,v_j)\quad(i\ne j), \tag*{(2)}

where dist⁡G(vi,vj)\operatorname{dist}_{G}(v_i,v_j) denotes the length of a shortest path between viv_i and vjv_j in GG. Equivalently,

F(G)=diag⁡(fl⁡(v1),…,fl⁡(vn))−D(G),F(G)=\operatorname{diag}(\operatorname{fl}(v_1),\ldots,\operatorname{fl}(v_n))-D(G),

where D(G)D(G) is the distance matrix of GG. Figure 4 illustrates a graph GG together with its average flow matrix F(G)F(G).

A graph G together with its average flow matrix F(G)

Figure 4. A graph GG together with its average flow matrix F(G)F(G). 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 GG is flow-stable if all its vertices have the same average flow, that is,

fl⁡(v1)=fl⁡(v2)=⋯=fl⁡(vn).\operatorname{fl}(v_1)=\operatorname{fl}(v_2)=\cdots=\operatorname{fl}(v_n).

Proposition 1. Let GG be a flow-stable graph of order nn, let cc denote the common average flow of its vertices, and let D(G)D(G) be its distance matrix with distance spectrum {d1,d2,…,dn}\{d_1,d_2,\ldots,d_n\}, listed with multiplicities. Then the average flow matrix F(G)F(G) has spectrum

{c−d1,c−d2,…,c−dn},\{c-d_1,c-d_2,\ldots,c-d_n\},

with the same multiplicities. Moreover, F(G)F(G) and D(G)D(G) have the same eigenvectors.

Proof. Since GG is flow-stable, every diagonal entry of F(G)F(G) equals cc. Hence, by (2),

F(G)=cI−D(G).F(G)=cI-D(G).

If xx is an eigenvector of D(G)D(G) corresponding to the eigenvalue did_i, then

F(G)x=(cI−D(G))x=cx−dix=(c−di)x.F(G)x=(cI-D(G))x=cx-d_i x=(c-d_i)x.

Therefore, xx is an eigenvector of F(G)F(G) corresponding to the eigenvalue c−dic-d_i. It follows that the spectrum of F(G)F(G) is {c−di}i=1n\{c-d_i\}_{i=1}^{n}, with the same multiplicities, and that F(G)F(G) and D(G)D(G) 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 GG is a vertex-transitive graph with common average flow cc and distance spectrum {d1,…,dn}\{d_1,\ldots,d_n\}, then the spectrum of its average flow matrix is {c−di}i=1n\{c-d_i\}_{i=1}^{n}.

Proof. If GG is vertex-transitive, then for any two vertices u,w∈V(G)u,w\in V(G) there exists an automorphism of GG mapping uu to ww. Since fl⁡(v)\operatorname{fl}(v) is invariant under graph automorphisms, it follows that all vertices of GG have the same average flow. Hence GG is flow-stable, and the conclusion follows from Proposition 1.

We now determine the spectrum of the average flow matrix of the complete graph KnK_n.

Proposition 2. Let KnK_n be the complete graph on n≥2n\ge2 vertices, and let c=fl⁡(v)c=\operatorname{fl}(v) denote the common average flow of its vertices. Then

spec⁡(F(Kn))={(c+1)[n−1],c−(n−1)}.\operatorname{spec}(F(K_n))=\{(c+1)^{[n-1]},c-(n-1)\}.

In particular, the largest eigenvalue of F(Kn)F(K_n) is

λmax⁡(F(Kn))=c+1.\lambda_{\max}(F(K_n))=c+1.

Proof. Since KnK_n is vertex-transitive, it is flow-stable, and hence every diagonal entry of F(Kn)F(K_n) equals cc. Moreover, every pair of distinct vertices in KnK_n is adjacent, so dist⁡Kn(u,v)=1\operatorname{dist}_{K_n}(u,v)=1 whenever u≠vu\ne v. Therefore,

F(Kn)=cI−D(Kn).F(K_n)=cI-D(K_n).

It is well known that

spec⁡(D(Kn))={n−1,(−1)[n−1]}.\operatorname{spec}(D(K_n))=\{n-1,(-1)^{[n-1]}\}.

By Proposition 1, it follows that

spec⁡(F(Kn))={c−(n−1),(c+1)[n−1]}.\operatorname{spec}(F(K_n))=\{c-(n-1),(c+1)^{[n-1]}\}.

Since n≥2n\ge2, we have c−(n−1)<c+1c-(n-1)<c+1, and therefore

λmax⁡(F(Kn))=c+1.\lambda_{\max}(F(K_n))=c+1.

Corollary 2. Let λmax⁡(F(Kn))\lambda_{\max}(F(K_n)) denote the largest eigenvalue of the average flow matrix of KnK_n. If n−2≤fl⁡(v)≤n−1n-2\le\operatorname{fl}(v)\le n-1, then

n−1≤λmax⁡(F(Kn))≤n.n-1\le\lambda_{\max}(F(K_n))\le n.

Proof. By Proposition 2,

λmax⁡(F(Kn))=fl⁡(v)+1.\lambda_{\max}(F(K_n))=\operatorname{fl}(v)+1.

The conclusion follows immediately from the bound n−2≤fl⁡(v)≤n−1n-2\le\operatorname{fl}(v)\le n-1.

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 GG, we define its average flow sum by

fl⁡(G)≔∑vi∈V(G)fl⁡(vi).(3)\operatorname{fl}(G)\coloneqq\sum_{v_i\in V(G)}\operatorname{fl}(v_i). \tag*{(3)}

Two graphs are said to be coflow mates if they have the same average flow sum. Equivalently, graphs with the same value of fl(G)\mathrm{fl}(G) belong to the same coflow class.

Since the diagonal entries of the average flow matrix F(G)F(G) are precisely the vertex average flows, we have

tr⁡(F(G))=fl(G).\operatorname{tr}(F(G)) = \mathrm{fl}(G).

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,

fl(G)≠fl(H)⟹G and H are not cospectral with respect to F.\mathrm{fl}(G) \ne\mathrm{fl}(H) \qquad\Longrightarrow\qquad G \text{ and } H \text{ are not cospectral with respect to } F.

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%.

nn
# connected graphs2111285311,117261,08011,716,571
# coflow graphs081363737730,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 nn, 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 nn: it is approximately 23% for n=5n = 5, increases slightly to 28% for n=6n = 6, and then decreases to 24.73%, 16.92%, and 10.32% for n=7,8,9n = 7, 8, 9, respectively, as shown in Figure 7a. On 10 vertices, however, this fraction rises sharply to approximately 65.62%.

nnCominimalComaximalCoflow + CominimalCoflow + Comaximal
50.23000–0
60.280000.01780
70.247300.00230
80.16920.00010.00250
90.10320.00120.00090
100.65620.05230.00010

Table 3. Fractions of connected graphs having a cominimal mate, a comaximal mate, and additional coflow constraints.

Fractions of graphs having a cominimal mate or a comaximal mate on $n$ vertices

Figure 7. Fractions of graphs having a cominimal mate or a comaximal mate on nn 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 n=10n = 10.

Number of cominimal graphs on $n$ vertices

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

Number of comaximal graphs on $n$ vertices

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

Numbers of cominimal and comaximal graphs on $n$ vertices

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

Fraction of cominimal graphs on $n$ vertices

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

Fraction of comaximal graphs on $n$ vertices

Figure 7b. (b) Fraction of comaximal graphs on nn 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 nn: it is 1.78% on 6 vertices, 0.23% on 7 vertices, approximately 0.25% for n=8n = 8, 0.09% for n=9n = 9, and only 0.01% for n=10n = 10, 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.

Number of cominimal graphs among coflow graphs on $n$ vertices

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

Number of comaximal graphs among coflow graphs on $n$ vertices

(b) (b) Number of comaximal graphs among coflow graphs on nn vertices.

Figure 9. Cominimal and comaximal graphs among coflow graphs on nn vertices.

Fraction of cominimal graphs among coflow graphs on $n$ vertices

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

Fraction of comaximal graphs among coflow graphs on $n$ vertices

(b) (b) Fraction of comaximal graphs among coflow graphs on nn vertices.

Figure 10. Fractions of coflow graphs that are also cominimal or comaximal on nn 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 AA for graphs on up to 9 vertices. Haemers and Spence [Haemers and Spence [8] extended this line of work to the matrices AA, LL, and QQ, obtaining the strongest results for QQ. Wilson and Zhu [Wilson and Zhu [15] showed that improved enumeration can be achieved by considering several matrices simultaneously, namely AA, LL, QQ, and L~\tilde{L}. Aouchiche and Hansen [Aouchiche and Hansen [2] further improved the enumeration results by considering the distance-associated matrices DD, DLD^L, and DQD^Q. 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 n≤10n \le10, we generated all connected graphs on nn 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 nn, 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 FF 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.

ReferenceFamily5678910
[4]Gncs(A)\mathcal{G}_{n}^{cs}(A)02631,35346,930NA
[8]Gncs(Q)\mathcal{G}_{n}^{cs}(Q)210801,04717,627615,919
[15]Gncs(A,L,Q,L~)\mathcal{G}_{n}^{cs}(A,L,Q,\widetilde{L})0000210,124
[2]Gncs(D,DQ)\mathcal{G}_{n}^{cs}(D,D^{Q})000007,712
Gncs(D,DL,DQ)\mathcal{G}_{n}^{cs}(D,D^{L},D^{Q})000007,622
[1]Gncs−in−in(D,DL,DQ)\mathcal{G}_{n}^{cs-in-in}(D,D^{L},D^{Q})000007,510
Gncs−in−in(A,DL,DQ)\mathcal{G}_{n}^{cs-in-in}(A,D^{L},D^{Q})000007,490
Our resultsGncs(F)\mathcal{G}_{n}^{cs}(F)000000

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 FF. 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. [1][Abiad and Alfaro(2021)] Abiad, A., Alfaro, C., 2021. Enumeration of cospectral and coinvariant graphs. Applied Mathematics and Computation 408, 126–348.
  2. [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. [3][Brouwer and Spence(2009)] Brouwer, A., Spence, E., 2009. Cospectral graphs on 12 vertices. The Electronic Journal of Combinatorics, N20.DOI
  4. [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. [5][Godsil and McKay(1982)] Godsil, C., McKay, B., 1982. Constructing cospectral graphs. Aequationes Mathematicae 25, 257–268.DOI
  6. [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. [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. [8][Haemers and Spence(2004)] Haemers, W., Spence, E., 2004. Enumeration of cospectral graphs. European Journal of Combinatorics 25, 199–211.
  9. [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. [10][Lepović(1998)] Lepović, M., 1998. Some statistical data on graphs with 10 vertices. Publikacije Elektrotehničkog Fakulteta. Serija Matematika , 79–88.
  11. [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. [12][Wang(2013)] Wang, W., 2013. Generalized spectral characterization of graphs: revisited. arXiv preprint arXiv:1309.6090.arxiv.org/abs/1309.6090
  13. [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. [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. [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.

Paper details

vlnc:W_c3pb76qk
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents