Graphs with the same diameter but differing lambda_2

The second smallest Laplacian eigenvalue constrains the diameter of a graph on n vertices since $$d\geq4/n \lambda_2$$
We pull out a bunch of connected graphs on n vertices, group them by diameter and compare the graphs with the most extreme values of lambda_2.
Not shown, however, my restricted searches were'nt able to find any graphs where the inequality is tight.

lam2 <- function(g){
  # returns the second smallest Laplacian eigenvalue for a graph
  eig <- eigen(laplacian_matrix(g))$values
  eig[length(eig)-1]
  }

g8 <- Filter(is.connected, make_all_graphs(8))

g8.dsplit <- lapply(1:7, function(i){
  # But, no need to consider 1 or 7, the path and complete graph are the only such graphs
  Filter(function(g){diameter(g) == i}, g8)
  })

g8.dsplit.l2sort <- lapply(g8.dsplit, function(glist){
  ord <- order(sapply(glist, lam2))
  glist[ord]
  })

g8.min.max.l2 <- lapply(g8.dsplit.l2sort, function(glist){
  list(glist[[1]],
        rev(glist)[[1]]
        )
  })

par(mfrow = c(2, 2))
lapply(c(3,5), function(i){
  glist <- g8.min.max.l2[[i]]
  print(c("4/nd", 4 / (8 * i)))
  plot(glist[[1]]); print(lam2(glist[[1]]))
  plot(glist[[2]]); print(lam2(glist[[2]]))
  NULL
  })

# diam 3
[1] "4/nd"              "0.166666666666667"
[1] 0.3542487
[1] 2.354249

# diam 5
[1] "4/nd" "0.1" 
[1] 0.2022567
[1] 0.5107114

Since $$d \geq 2$$ for any connected non-complete graph, we have $$d \geq \max\{2, 4/n\lambda_2\}$$ for any non-trivial graph. The eigenvalue-based constraint only kicks in when $$4/n\lambda_2 > 2$$ or $$\lambda_2 < 2/n$$.
If we compute $$\lambda_2$$ and the diameter for each connected graph on 7, 8 and 9 vertices we can try and find those graphs for which this bound is strongest or weakest.
We define the residual to be $$(d - 4/n\lambda_2) / d$$ so that we have a non-negative score that is comparable between graphs with distinct diameters.

f <- function(g, n){
  # returns the lower bound on the diameter provided by the eigenvalue
  ev <- rev(eigen(graph.laplacian(g))$values)[2]
  ev2 <- 4 / (n * ev)
  ev2
  }

resid.func <- function(g){
  stopifnot(is.connected(g))
  n <- length(V(g))
  d <- diameter(g)
  return( (d - f(g, n)) / d)
  }

g7 <- Filter(is.connected, make_all_graphs(7))
# g8 above
g9 <- Filter(is.connected, make_all_graphs(9)) # takes a while

Note that the fraction of graphs where the eigevalue bound kicks in is pretty small:
length(Filter(function(g){f(g, 7) > 2}, g7)) / length(g7)
# [1] 0.01145038
length(Filter(function(g){f(g, 8) > 2}, g8)) / length(g8)

# [1] 0.005293551
length(Filter(function(g){f(g, 9) > 2}, g9)) / length(g9)

# [1] 0.001629274

residual7 <- sapply(g7, resid.func)
residual8 <- sapply(g8, resid.func)
residual9 <- sapply(g9, resid.func)

par(mfrow = c(3, 2))
plot(g7[[which.min(residual7)]]); plot(g7[[which.max(residual7)]])
plot(g8[[which.min(residual8)]]); plot(g8[[which.max(residual8)]])
plot(g9[[which.min(residual9)]]); plot(g9[[which.max(residual9)]])

Which is pretty neat, the graphs with the lowest (scaled) discrepancy between the eigenvalue bound and the diameter were long spindly beasts and those with the highest discrepancy were n-2 regular.

Graphs that are betweenness and/or degree-regular

All connected graphs on between 3 and 8 vertices that have identical betweenness values for all vertices:

is.generic.regular <- function(g, centrality.func, tol = 1E-10){
  centrals <- centrality.func(g)
  diffs <- abs(centrals - centrals[1])
  sum(diffs) < tol
  }

is.beta.regular <- function(g, tol = 1E-10){
  # checks if all the betweenness values for a graph
  # are equal (that is, less than a specified tolerance)
  is.generic.regular(g, betweenness, tol)
  }

is.delta.regular <- function(g, tol = 1E-10){
  # checks if all the degree values for a graph are equal
  # - tolerance should be irrelevant since degrees are integers
  is.generic.regular(g, degree, tol)
  }

##############################################

# All non-isomorphic connected graphs on up to 8 vertices
all.graphs <- lapply(1:8, function(i){
  Filter(is.connected, make_all_graphs(i))
  })

##############################################

# The subset of graphs that are betweenness-regular
beta.regs <- lapply(all.graphs,
  function(G.list){
    Filter(is.beta.regular, G.list)
    })
sapply(beta.regs, length)
#[1] 1 1 1 2 2 5 3 8

# The subset of graphs that are regular (ie, degree-regular)
delta.regs <- lapply(all.graphs,
  function(G.list){
    Filter(is.delta.regular, G.list)
    })
sapply(delta.regs, length)
# [1]  1  1  1  2  2  4  4 13

# The subset of graphs that are regular for both centralities
beta.and.delta.regs <- lapply(beta.regs, function(G.list){
  Filter(is.delta.regular, G.list)
  })
sapply(beta.and.delta.regs, length)
# [1] 1 1 1 2 2 4 3 7
par(mfrow = c(2, 4))
lapply(beta.and.delta.regs[[8]], plot)
# Some examples on 8 vertices:

# The subset of graphs that are betweeness-regular but not degree regular
beta.not.delta.regs <- lapply(beta.regs, function(G.list){
  Filter(function(g) !is.delta.regular(g), G.list)
  })
# [1] 0 0 0 0 0 1 0 1
par(mfrow = c(1, 2))
plot(beta.not.delta.regs[[6]][[1]])
plot(beta.not.delta.regs[[8]][[1]])

# The subset of graphs that are degree- but not betweenness-regular
delta.not.beta.regs <- lapply(delta.regs, function(G.list){
  Filter(function(g) !is.beta.regular(g), G.list)
  })
sapply(delta.not.beta.regs, length)

#[1] 0 0 0 0 0 0 1 6
par(mfrow = c(2, 4))
plot(delta.not.beta.regs[[7]][[1]])
lapply(delta.not.beta.regs[[8]], plot)

Make all graphs on up to n vertices; Number of non-isomorphic classes of such graphs

#####################################################
is_non_increasing <- function(v){
  if(length(v) == 1){return(TRUE)}
  diff <- v[1:(length(v) - 1)] - v[2:length(v)]
  all(diff >= 0)
  }

#####################################################
reduce_by_isomorphism_class <- function(adj.mats){
  # Assume undirected, ie symmetrical matrices
  # TODO - Find other simply calculated graph params
  #          from adjacency matrix to reduce # of calls
  #          to is_isomorphic_to
  require(Matrix) # doesn't rank the zero matrix correctly
  require(igraph)
  
  degree.vecs <- t(sapply(adj.mats, colSums))
  ranks       <- sapply(adj.mats, rankMatrix)
  eigs        <- t(sapply(adj.mats, function(x) eigen(x)$values))
  eigs.trunc  <- round( eigs, 3 )
  
  matrix.params <- cbind(degree.vecs, ranks, eigs.trunc)
  
  # Convert the vector of (nonincreasing) degrees,
  #   the matrix rank, and the rounded eigenvalues
  #   into a single factor to permit quick matching prior to
  #   isomorphism tests
  match.params <- data.frame(
    mat = 1:length(adj.mats),
    params = factor(
      apply(matrix.params, 1, 
      function(row){paste(row, collapse = ' ')})
      )
    )
  
  iso.classes <- lapply(levels(match.params$params),
    function(par.str){
      rows <- which(match.params$params == par.str)
      temp.classes <- list()
      temp.classes <- append(temp.classes, adj.mats[rows][1])
      if(length(rows) > 1){
        # drop adj.mats[current.row] if its is isomorphic
        #   to a graph in temp.classes
        for(r in rows){
          test.mat <- adj.mats[[r]]
          test.g <- graph.adjacency(
            test.mat,
            'undirected'
            )
          iso.to.any <- sapply(temp.classes, function(storedmat){
            stored.g <- graph.adjacency(
              storedmat,
              'undirected'
              )
            is_isomorphic_to(test.g, stored.g)
            })
          iso.to.any <- any(iso.to.any)
          if(! iso.to.any){
            temp.classes <- append(temp.classes, adj.mats[r])
            }
          }
        }
      temp.classes
    })
  do.call('c', iso.classes)
  }

#####################################################

## all graphs on n vertices
make_all_adjMats <- function(n){
  # not yet finished - works for n=1..8, but a bit slow
  maxN = 10
  stopifnot(n %in% seq(1, maxN))
  
  if(n == 1){
    return(
      list(matrix(0, nrow = n, ncol = n))
      )
    }
  adj.mats.lo <- lapply(
    # append an extra vertex to each one-smaller adjacency matrix
    make_all_adjMats(n-1),
    function(m){
      M <- matrix(0, nrow = n, ncol = n)
      M[1:(n-1), 1:(n-1)] <- m
      M
      })
  
  # all setwise combinations of 1:n-1, incl the empty set
  all.combs <- lapply(0:(n-1), function(x) combn((n-1), x))
  
  adj.mats <- lapply(adj.mats.lo, function(m){
    sublist <- list()
    # add edges for the new vertex, vertex n
    for(combmat in all.combs){
      if(nrow(combmat) == 0){
        sublist <- append(sublist, list(m))
        } else {
        for(col in 1:ncol(combmat)){
          comb <- combmat[, col]
          temp.m <- m
          temp.m[n, comb] <- 1
          temp.m[comb, n] <- 1
          # ensure deg(i)>=deg(i+1) for i=1..n-1
          if(is_non_increasing(colSums(temp.m))){
            sublist <- append(sublist, list(temp.m))
            }
          }
        }
      }
    sublist
    })
  adj.mats <- do.call('c', adj.mats)
  adj.mats <- adj.mats[order(sapply(adj.mats, sum))]
  # Becomes slow for n = 7
  # Methods to filter by isomorphism class?
  # a - ensure deg(i) >= deg(i+1) - done
  # b - group by degree vector and rank(ie, # connComp)
  #       then use is_isomorphic_to
  adj.mats <- reduce_by_isomorphism_class(adj.mats)
  adj.mats
  }

####################################################
##

make_all_graphs <- function(n){
  require(igraph)
  # let vertices be 1..n and assume deg(i)<=deg(i+1) for all i
  adj.mats <- make_all_adjMats(n)
  graphs <- lapply(
    adj.mats,
    function(m){
      graph_from_adjacency_matrix(
        adjmatrix = m,
        mode = 'undirected'
        )})
  graphs
  }


#######################################################
library(igraph)


# Number of non-isomorphic connected graphs on 7 vertices:

system.time(G7 <- Filter(is.connected, make_all_graphs(7)))

# Without filtering on eigenvalues
#    user  system elapsed 
#    3.35    0.00    3.37

# With filtering on eigenvalues
#    user  system elapsed 
#    2.40    0.00    2.41 

length(G7) # 524 

G7.eigen.adj <- t(sapply(G7, function(g){
  eigen(get.adjacency(g))$values
  }))
length(which(duplicated(G7.eigen.adj))) # 1

length(which(duplicated(round(G7.eigen.adj, 10)))) # 21

G7.eigen.lap <- t(sapply(G7, function(g){
  eigen(graph.laplacian(g))$values
  }))
length(which(duplicated(G7.eigen.lap))) # 2
length(which(duplicated(round(G7.eigen.lap, 10)))) # 14

r <- intersect(

  which(duplicated(round(G7.eigen.adj, 10))),

  which(duplicated(round(G7.eigen.lap, 10)))

  ) # only 441

lapply(r, function(x){

  temp <- G7.eigen.lap - matrix(

    G7.eigen.lap[x, ],

    nrow = nrow(G7.eigen.lap), ncol = 7, byrow = TRUE

    )

  which(rowSums(temp^2) < 0.001)

  })

# 374, 375, 441 

# 374 and 375 have identical degree vec

# 374 not.iso to 375 since 374 contains 3 maximal cliques and 375 contains 2 (max cliques being of size 4)

# rank(374)=5; rank(375)=6 can be seen using pracma::rref and Matrix::rankMatrix (nb, rank(441)=5 also)

# numerical rounding made it look like they had the same spectrum

eig.vs.bet <- t(sapply(G7, function(g){

  lap <- graph.laplacian(g)

  eig <- eigen(lap)

  bet <- betweenness(g)

  which.min.loading <- which.min(abs(eig$vectors[, 6]))

  min.loading <- min(abs(eig$vectors[, 6]))

  which.max.bet <- which.max(bet)

  max.bet <- max(bet)

  cbind(which.min.loading, min.loading, which.max.bet, max.bet)

  }))

# The subset of graphs where lambda2>0 and has multiplicity >= 2

# numerical accuracy < 10^-12

G7.L2.multi <- Filter(

  function(g){

    eig <- eigen(graph.laplacian(g))$values

    abs(eig[5] - eig[6]) < 1E-12

    },

  G7

  )

# 41 graphs

# The subset of graphs where lambda2>0 and has multiplicity 1

G7.L2.single <- Filter(

  function(g){

    eig <- eigen(graph.laplacian(g))$values

    !(abs(eig[5] - eig[6]) < 1E-12)

    },

  G7

  )
# 483 graphs

# Those graphs that have 0-support on at least one vertex for

# every vector in the lambda2-eigenspace

G7.L2.nosupport <- Filter(

  function(g){

    eigvals <- eigen(graph.laplacian(g))$values

    cols <- which(abs(eigvals - eigvals[6]) < 1E-12)

    eigvecs <- eigen(graph.laplacian(g))$vectors

    eig.L2 <- matrix(eigvecs[, cols], ncol = length(cols))

    no.support <- which(rowSums(abs(eig.L2)) < 1E-12)

    length(no.support) >= 1

    },

  G7

  )

# 215 graphs

#######################################################

system.time(G8 <- Filter(is.connected, make_all_graphs(8)))

# Without filtering on eigenvalues
#    user  system elapsed
#   42.17    0.14   42.33

# With filtering on eigenvalues

#    user  system elapsed 

#   19.69    0.02   19.72 

# Recommend working with 10pt accuracy to find 'isospectral' graphs

length(G8) # 4156

G8.eigen.adj <- t(sapply(G8, function(g){
  eigen(get.adjacency(g))$values
  }))

length(which(duplicated(G8.eigen.adj))) # 1
length(which(duplicated(round(G8.eigen.adj, 10)))) # 156
adj.match <- which(duplicated(round(G8.eigen.adj, 10)))

G8.eigen.lap <- t(sapply(G8, function(g){
  eigen(graph.laplacian(g))$values
  }))

length(which(duplicated(G8.eigen.lap))) # 7

length(which(duplicated(round(G8.eigen.lap, 10)))) # 110

lap.match <- which(duplicated(round(G8.eigen.lap, 10)))

r <- intersect(adj.match, lap.match) # 6 entries

# r[1] = 173

# find graphs that have the same Laplacian and Adjacency spectra:

lapply(r, function(x){

  temp <- G8.eigen.lap - matrix(

    G8.eigen.lap[x, ],

    nrow = nrow(G8.eigen.lap), ncol = 8, byrow = TRUE

    )

  which(rowSums(temp^2) < 0.001)

  })

# [1] 103 173

# [1] 228 309

# [1] 1077 1375

# [1] 2103 2110 # have the same degree distribution as well

# [1] 2676 2678 # have the same degree distrubution as well

# [1] 4004 4005 4073 # 4004/5 have the same degree distribution

# The two graphs 2103 and 2110 have the same eigenvalues (to numerical accuracy) for both Laplacian and Adjacency, have the same degree vector, but have differing betweenness vector. They are non-isomorphic, since one contains K_4, but the other doesn't.

# The eigenvectors differ for the two graphs: 

#   loadings follow the degree for the leading adjacency eigenvec;

#   same values in the eigenvec for alg-connectivity but in different places

betweenness(G8[[2103]])

[1] 9.00 3.00 3.00 0.75 0.75 0.50 0.00 0.00

betweenness(G8[[2110]])

[1] 9.00 1.25 1.25 0.00 2.50 2.50 0.50 0.00

degree(G8[[2103]])

[1] 6 4 4 3 3 3 2 1

round(eigen(get.adjacency(G8[[2103]]))$values, 3)

[1]  3.699  1.363  0.618  0.333 -0.706 -1.618 -1.689

[8] -2.000

round(eigen(graph.laplacian(G8[[2103]]))$values, 4)

[1] 7.0908 5.4142 4.8550 3.6023 2.5858 1.5155 0.9365

[8] 0.0000

# lambda_2 eigenvecs (for 2nd smallest eigenval of Laplacian)

round(eigen(graph.laplacian(G8[[2103]]))$vectors[, 7], 3)

[1]  0.057 -0.182 -0.182 -0.090 -0.090 -0.060 -0.343

[8]  0.891

round(eigen(graph.laplacian(G8[[2110]]))$vectors[, 7], 3)

[1] -0.057  0.090  0.090  0.060  0.182  0.182  0.343

[8] -0.891

# mu_1 eigenvecs (for largest eigenval of adjacency mat)

round(eigen(get.adjacency(G8[[2103]]))$vectors[, 1], 3)

[1] -0.526 -0.401 -0.401 -0.339 -0.339 -0.325 -0.217

[8] -0.142

round(eigen(get.adjacency(G8[[2110]]))$vectors[, 1], 3)

[1] -0.523 -0.431 -0.431 -0.369 -0.296 -0.296 -0.158

[8] -0.139

#######################################################################

# Finding non-isomorphic, connected graphs with the same betweenness distribution is easy:

G8.bet <- t(sapply(G8, function(g) sort(betweenness(g))))

head(which(duplicated(G8.bet)))

[1] 323 547 565 579 632 670

G8.bet[323, ]

with(

  list(x = G8.bet - matrix(G8.bet[323, ], nrow = nrow(G8.bet), ncol = 8, byrow = TRUE)),

  which(rowSums(x^2) == 0)

  )

# 115, 323

###########################################################

# TODO
# Find the smallest pair of connected graphs which have the same:

# graph params:
# a) degree distribution # G5[[4]] and G5[[5]]
# b) diameter         # G4[[2]] and G4[[3]]
# c) clique size      # G4[[1]] and G4[[2]]
# d) coclique size    # G4[[1]] and G4[[2]]
# e) betweenness      # G6[[27]] and G6[[34]]

# matrix params:
# f) rank
# g) adjacency eigenvals
# h) laplacian eigenvals

Graphs that are non-isomorphic but have identical betweenness / degree / spectrum etc..

Code to identify a smallest pair of non-isomorphic, connected, undirected graphs that share certain properties:
i)   Share the same degree multiset
ii)  Share the same adjacency spectrum
iii) Share the same laplacian spectrum
iv) Share the same betweenness multiset
v)  Share the same (degree, betweenness) multiset
vi) Share the same adjacency and laplacian spectrum

We consider a graph g1 smaller than g2 if |V(g1)| < |V(g2)| OR |E(g1)| < |E(g2)|

#####################################################
library(igraph)
library(Matrix)

# See other blogposts for make_all_graphs(n) function

####################################################

get_matching_graph_pairs <- function(

    graphset,

    matchset = c('deg', 'bet', 'adjspec', 'lapspec'),

    digits = 10

    ){

  vertex.matchset <- intersect(matchset, c('deg', 'bet'))

  spectrum.matchset  <- intersect(matchset, c('adjspec', 'lapspec'))

  graph.statistics <- NULL

  

  # vertex level matchings
  if(length(vertex.matchset) > 0){

    vertex.statistics <- lapply(graphset, function(g){

      stats.list <- lapply(vertex.matchset, function(vm){

        if(vm == 'deg'){return(data.frame(deg = degree(g)))}

        if(vm == 'bet'){return(data.frame(bet = betweenness(g)))}

        })

      stats.df <- do.call('cbind', stats.list)

      # order the rows by the arbitrary columns:

      stats.df[do.call(order, stats.df), ]

      return(unlist(stats.df))

      })

    vertex.statistics <- do.call('rbind', vertex.statistics)

    graph.statistics <- vertex.statistics
    }

  
  # spectrum matchings

  # Uses Charpoly function as defined in a previous blog
  if(length(spectrum.matchset) > 0){
    spec.statistics <- lapply(graphset, function(g){
      stats.list <- lapply(spectrum.matchset, function(sm){
        if(sm == 'adjspec'){
          return(data.frame(adj = Charpoly(get.adjacency(g))))
          }
        if(sm == 'lapspec'){
          return(data.frame(lap = Charpoly(graph.laplacian(g))))
          }
        })
      stats.df <- do.call('cbind', stats.list)
      return(unlist(stats.df))
      })
    spec.statistics <- do.call('rbind', spec.statistics)
    if(!is.null(graph.statistics)){
      graph.statistics <- cbind(graph.statistics, spec.statistics)
      } else {
      graph.statistics <- spec.statistics
      }
    }

  dups.rows <- which(duplicated(round(

    graph.statistics, digits = digits

    )))

  

  if(length(dups.rows) > 0){

    r <- dups.rows[1]

    rep.matrix <- matrix(

      graph.statistics[r, ],

      nrow = nrow(graph.statistics),

      ncol = ncol(graph.statistics),

      byrow = TRUE

      )

    delta.matrix <- round(graph.statistics - rep.matrix,

                          digits = digits)

    matching.rows <- which(rowSums(abs(delta.matrix)) == 0)

    stopifnot(length(matching.rows) > 1)

    return(graphset[matching.rows[1:2]])

    }

  return(NULL)

  }

####################################################

get_smallest_match <- function(

  matchset = c('deg', 'bet', 'adjspec', 'lapspec'),

  max.vertices = 8,

  digits = 10   

  ){

  # Consider only connected graphs

  # Start from n = 3 vertices, since only 1 graph when n<=2

  for (n in 3:max.vertices){

    # Get a list of all connected, non-isomorphic graphs 

    #   on n vertices

    graphset <- Filter(is_connected, make_all_graphs(n))

    

    # Obtain a list of two graphs that match for all of 

    #   the reqd statistics (if possible) and return them

    #   to the user:

    matching.graphs <- get_matching_graph_pairs(

      graphset,

      matchset,

      digits

      )

    if(!is.null(matching.graphs)){

      return(matching.graphs)

      }

    }

  # No graphs could be found that matched on the required statistics

  return(NULL)

  }

###########################################

With the above code, we can find the smallest pair of graphs that are non-isomorphic, but which have the same 

i) degree distribution:

deg.match <- get_smallest_match('deg')

> lapply(deg.match, degree)
[[1]]
[1] 3 2 2 2 1

[[2]]
[1] 3 2 2 2 1

> lapply(deg.match, betweenness)
[[1]]
[1] 3.5 1.0 1.0 0.5 0.0

[[2]]

[1] 4 0 0 3 0

ii) Betweenness distribution

bet.match <- get_smallest_match('bet')

> lapply(bet.match, degree)
[[1]]
[1] 6 2 2 2 2 2 2

[[2]]
[1] 6 3 3 3 1 1 1

> lapply(bet.match, betweenness)
[[1]]
[1] 12  0  0  0  0  0  0

[[2]]
[1] 12  0  0  0  0  0  0

iii) Distribution of (degree, betweenness) ordered pairs
Note the adjacency eigenvalues differ for these two graphs

db.match  <- get_smallest_match(c('deg', 'bet'))

> lapply(db.match, degree)
[[1]]
[1] 4 4 4 4 4 4 4 4

[[2]]
[1] 4 4 4 4 4 4 4 4

> lapply(db.match, betweenness)
[[1]]
[1] 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5

[[2]]
[1] 1.5 1.5 1.5 1.5 1.5 1.5 1.5 1.5

> lapply(db.match, function(x) round(eigen(get.adjacency(x))$values, 10))
[[1]]
[1]  4  2  0  0  0 -2 -2 -2

[[2]]
[1]  4.000000  1.414214  1.414214  0.000000 -1.414214 -1.414214 -2.000000
[8] -2.000000

iv) Adjacency spectrum

adj.match <- get_smallest_match('adjspec')

lapply(adj.match, plot)

v) Laplacian spectrum

lap.match <- get_smallest_match('lapspec')

lapply(lap.match, plot)

vi) Adjacency spectrum and Degree:

da.match <- get_smallest_match(c('deg', 'adjspec'))

vii) Laplacian spectrum and Degree:

dl.match <- get_smallest_match(c('lapspec', 'deg'))

Note that I could not find a pair of graphs on <= 9 vertices (code is pretty slow for > 8 vertices though) that had 
- both identical Laplacian spectrum and identical adjacency spectrum
- both identical adjacency spectrum and betweenness distribution
- both identical Laplacian spectrum and betweenness distribution