Same eccentricity sequence in non-isomorphic graphs

Question

I want to find two connected, non-isomorphic graphs with order n with the same eccentricity sequence where $n\ge 4$.

The closest I could think of was $K_{1,n}$ having an eccentricity sequence of ${1,2,2,2,2,2...,2}$ and $K_{n+1}$ having an eccentricity sequence of ${1,1,1,1,1,1,1....,1}$. This yields eccentricity sequence being off by $1$ for $n\ge 4$.

Is there some methodical way of finding two non-isomorphic graphs with the same eccentricity sequence?

Answer 1

Try $K_{1,n}$ and $K_{1,n}+e$ (add one more edge to $K_{1,n}$) where $n\ge3$.

Answer 2

A reasonably "methodical" way to find such examples is to use Mathematica. (Other software might do as well.)

First, we get a list of all "notable" connected graphs on 5 vertices (for order 5, all graphs happen to be notable, but if we tried this for a larger order, we'd miss some). The syntax here is a bit awkward: GraphData[5] gives Mathematica's names for all these graphs, and then applying GraphData again to those names gives the actual graphs. If 5 hadn't been enough vertices, we could have tried 6 or more.

graphs = Select[GraphData /@ GraphData[5], ConnectedGraphQ];

Then, we group the graphs into classes with the same eccentricity sequence. (Actually, EccentricityCentrality computes the reciprocals of the eccentricities within a connected component, but that's fine.)

classes = GatherBy[graphs, Sort @* EccentricityCentrality];

The largest of the classes, produced by

MaximalBy[classes, Length]

gives the following output:

All of these graphs have the same eccentricity sequence $1,2,2,2,2$.

---

In general, there's also lots of graphs with eccentricity sequence $2,2,\dots,2$.

First of all, there's the complete bipartite graphs $K_{m,n}$, unless $m=1$ or $n=1$. Also, if we guarantee that in an $n$-vertex graph no vertex has degree $n-1$ (so that all eccentricities are at least $2$) but any two non-adjacent vertices have a neighbor in common (so that the diameter is $2$, and therefore all eccentricities are at most $2$) then we get a graph with this eccentricity sequence.

One way to do that is to make sure all degrees are in the range $(\frac n2, n-1)$ not including the endpoints. Also, as bof points out in the comments, a graph chosen at random (by flipping independent coins for each edge) has this property with probability tending to $1$: a vertex has degree $n-1$ with probability $(\frac12)^{n-1}$, and two vertices are at distance $3$ or more with probability $\frac12(\frac34)^{n-2}$. So all but at most a $n(\frac12)^{n-1}+\frac{n(n-1)}{4}(\frac34)^{n-2}$ fraction of the labeled $n$-vertex graphs - an exponentially small fraction of such graphs - have eccentricity sequence $2,2,\dots,2$.