Misma secuencia de excentricidad en grafos no isomorfos

Question

Quiero encontrar a dos conectados, no isomorfo gráficos de orden n con la misma excentricidad de la secuencia donde $n\ge 4$.

Lo más cercano que podía pensar era en $K_{1,n}$ tener una excentricidad de la secuencia de ${1,2,2,2,2,2...,2}$ e $K_{n+1}$ tener una excentricidad de la secuencia de ${1,1,1,1,1,1,1....,1}$. Esto produce que la excentricidad de la secuencia que se fuera por $1$ para $n\ge 4$.

¿Hay alguna manera metódica de encontrar dos personas que no son isomorfos gráficos con la misma excentricidad de la secuencia?

Answer 1

Prueba <span class="math-container">$K{1,n}$</span> y <span class="math-container">$K{1,n}+e$</span> (añadir un borde más a <span class="math-container">$K_{1,n}$</span>) donde <span class="math-container">$n\ge3$</span>.

Answer 2

Razonablemente "metódico" manera de encontrar estos ejemplos es el uso de Mathematica. (Otro software que se puede hacer así.)

En primer lugar, tenemos una lista de todos los "notables" conectado gráficos en 5 vértices (por orden de 5, todos los gráficos pasan a ser notable, pero si tratamos esto para una orden más grande, nos gustaría que nos faltan algunas). La sintaxis de aquí es un poco torpe: GraphData[5] da Mathematica de los nombres de todos estos gráficos y, a continuación, aplicar GraphData más a los nombres da la real de gráficos. Si 5 no había sido suficiente vértices, se podría haber intentado 6 o más.

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

A continuación, tenemos el grupo de los gráficos dentro de las clases con la misma excentricidad de la secuencia. (En realidad, EccentricityCentrality calcula los recíprocos de las excentricidades dentro de un componente conectado, pero está bien.)

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

La más grande de las clases, producido por

MaximalBy[classes, Length]

da el siguiente resultado:

Todos estos gráficos tienen la misma excentricidad secuencia $1,2,2,2,2$.

---

En general, también hay un montón de gráficos con la excentricidad de la secuencia de $2,2,\dots,2$.

Primero de todo, hay la completa grafos bipartitos $K_{m,n}$, a menos que $m=1$ o $n=1$. También, si tenemos la garantía de que en un $n$-vértice de la gráfica de ningún vértice tiene grado $n-1$ (de modo que todas las excentricidades son, al menos, $2$) pero ninguno de los dos no adyacentes vértices tiene un vecino en común (de modo que el diámetro es de $2$, y por lo tanto todas las excentricidades son en la mayoría de las $2$) a continuación tenemos un gráfico con esta excentricidad de la secuencia.

Una manera de hacerlo es asegurarse de que todos los grados están en el rango de $(\frac n2, n-1)$ no incluyendo los extremos. También, como bof señala en los comentarios, un gráfico elegido al azar (por voltear independiente de monedas para cada borde) tiene esta propiedad, con la probabilidad tiende a $1$: un vértice tiene grado $n-1$ con una probabilidad de $(\frac12)^{n-1}$, y dos vértices son a distancia $3$ o más con una probabilidad de $\frac12(\frac34)^{n-2}$. Así que todos, pero en la mayoría de un $n(\frac12)^{n-1}+\frac{n(n-1)}{4}(\frac34)^{n-2}$ fracción de la etiqueta de $n$-vértice gráficos - una exponencialmente pequeña fracción de los gráficos de este tipo - tienen la excentricidad de la secuencia de $2,2,\dots,2$.