Encontrar un grafo 3-regular "con el menor número de vértices" que contenga P6 como subgrafo inducido

Question

¿Puedes decirme un grafo 3-regular con el menor número de vértices, que contenga a P-6 como subgrafo inducido?

Un gráfico 3-regular es aquel en el que el grado de cada vértice es 3.

P-6 parece: o--o--o--o--o--o

H es un subgrafo inducido de G si el conjunto de vértices de H es un subconjunto del conjunto de vértices de G y uv es una arista que conecta los vértices 'u' y 'v' en H sólo si uv es una arista en G.

El principal problema es la cláusula del "menor número de vértices".

Ya lo he intentado para todos los siguientes grafos 3-regulares y he encontrado que ninguno de estos grafos contiene P6 como subgrafo inducido. Así que el orden del gráfico tiene que ser más de 8 con seguridad.

Answer 1

Los vértices de la zona inducida $P_6$ tienen títulos $1, 2, 2, 2, 2, 1$ en el camino, y necesitan tener el grado total $3,3,3,3,3,3$ , por lo que necesitan $2+1+1+1+1+2=8$ bordes más saliendo de ellos. Ninguna de ellas puede ir a otros vértices del $P_6$ porque es inducido, por lo que tienen que ir a otros vértices del gráfico.

Estos $8$ los bordes necesitan al menos $\lceil \frac83 \rceil = 3$ vértices a los que ir. Pero no podemos tener sólo $3$ otros vértices, porque no hay $3$ -grafo regular en $9$ vértices. (El lema del apretón de manos dice que tal gráfico tendría $\frac{3\cdot 9}{2} = 13.5$ bordes). Así que debemos tener al menos $4$ otros vértices.

Con $4$ otros vértices, su grado total debe ser $4 \cdot 3 = 12$ por lo que tienen que tomar la $8$ bordes que salen de la $P_6$ y tienen $2$ más aristas internas. (Cada arista interna contribuye $2$ a la suma de sus grados). Hay muchas formas de hacerlo; una de ellas se muestra a continuación.

Aquí hay una imagen más simétrica de este gráfico, con una $P_6$ destacado: