Matemática => Teoría de grafos => Mensaje iniciado por: wrrp en 24 Noviembre, 2019, 01:09



Título: k-ésima potencia de un grafo y notación
Publicado por: wrrp en 24 Noviembre, 2019, 01:09
Pobar que

[texx]d(P_n^k)>2k-1[/texx] donde [texx]n>k^2+k[/texx]


Título: Re: k-esima potencia de un grafo y notacion
Publicado por: wrrp en 24 Noviembre, 2019, 01:12
de antemano me disculpo si este no es el lugar adecuado para publicar este mensaje, pero encontre este problema y no he podido encontrar que es   [texx]P_n[/texx].


Título: Re: k-ésima potencia de un grafo y notación
Publicado por: Luis Fuentes en 24 Noviembre, 2019, 17:26
Hola

 Bienvenido al foro.

 Recuerda leer y seguir  las reglas (http://rinconmatematico.com/foros/index.php?topic=678.0)[texx]^{(1)}[/texx] del mismo así como el tutorial del LaTeX (http://rinconmatematico.com/instructivolatex/formulas.htm) para escribir las fórmulas matemáticas correctamente.

Pobar que

[texx]d(P_n^k)>2k-1[/texx] donde [texx]n>k^2+k[/texx]

Supongo que [texx]P_n[/texx] se refiere al camino ("path graph (https://en.wikipedia.org/wiki/Path_graph)") de [texx]n[/texx]-vértices. Es decir el grafo:

[texx]v_1--v_2--v_3-.\ldots--v_n[/texx]

Entiendo que la potencia [texx]k[/texx]-ésima del grafo se refiera esto (https://en.wikipedia.org/wiki/Graph_power): el grafo con los mismos vértices y aristas uniendo vértices que en el grafo original estban a lo sumo a distancia [texx]k[/texx].

Lo que no estoy seguro que estás denotando por [texx]d(P_n^k)[/texx]. ¿El diámetro?. Si fuese así el resultado no veo que sea cierto, porque si consideramos [texx]n=13[/texx] y [texx]k=3[/texx], se tiene que [texx]n>3^2+3[/texx], pero el diámetro de [texx]P_{13}^3[/texx] es (creo) [texx]4[/texx], que no cumple [texx]4>2\cdot 3-1[/texx].

Saludos.


[texx]^{(1)}[/texx] Enlace corregido.


Título: Re: k-ésima potencia de un grafo y notación
Publicado por: wrrp en 24 Noviembre, 2019, 20:57
Hola

Muchas gracias por la bienvenida.

En cuanto a d se refiere a que d=[texx]\displaystyle\frac{1}{n}\cdot\sum_{i=1}^n{deg(v_i)}[/texx].
En cuanto a la potencia de un grafo estamos de acuerdo en los conceptos.
Lo que no me queda muy claro es que es un camino de [texx]n-[/texx]vértices, ¿sera un árbol?.


Título: Re: k-ésima potencia de un grafo y notación
Publicado por: Luis Fuentes en 25 Noviembre, 2019, 03:40
Hola

Lo que no me queda muy claro es que es un camino de [texx]n-[/texx]vértices, ¿sera un árbol?.

No. No coloqué el enlace que pretendía; lo he corregido. El grafo [texx]P_n[/texx] es el grafo que tiene los vértices [texx]v_1,v_2,\ldots,v_n[/texx] y aristas únicamente [texx](v_i,v_i+1)[/texx] con [texx]i=1,2,\ldots,n-1[/texx].

(http://rinconmatematico.com/foros/index.php?action=dlattach;topic=111431.0;attach=21472)

En cuanto a d se refiere a que d=[texx]\displaystyle\frac{1}{n}\cdot\sum_{i=1}^n{deg(v_i)}[/texx].

Bien. Entonces nota que en [texx]P_n^k[/texx], exceptuando los primeros y últimos [texx]k[/texx] vértices, el resto de ellos tiene grado [texx]2k[/texx], porque están asociados con [texx]k[/texx] vértices a izquierda y derecha.

El grado de los vértices [texx]1,2,\dots,k[/texx] es respectivamente:

[texx]k,k+1,k+2,\ldots,2k-1[/texx]

Idem para los [texx]k[/texx] últimos.

Entonces:

[texx]\displaystyle\sum_{i=1}^n{deg(v_i)}=2(k+(k+1)+(k+2)+\ldots+(2k-1))+(n-2k)\cdot 2k=(3k-1)k+(n-2k)2k=2kn-(k^2+k)[/texx]

y

[texx]d(P_n^k)=\dfrac{1}{n}\displaystyle\sum_{i=1}^n{deg(v_i)}=2k-\dfrac{k^2+k}{n}[/texx]

Termina...

Saludos.


Título: Re: k-ésima potencia de un grafo y notación
Publicado por: wrrp en 01 Diciembre, 2019, 22:39
Hola, perdon por no contestar rapido, es que se me había dificultado entender algunas cuestiones.
Ya tengo lo que creo que puede ser la demostración...

Demostración:

Se sabe que:
[texx]\displaystyle\sum_{i=1}^n{deg(v_i)}=2(k+(k+1)+\ldots + (k+k-1))+2k(n-2k)=(3k−1)k+(n−2k)2k=2kn−(k^2+k)[/texx]
y por lo anterior tenemos:

d[texx](P_n^k)=2k-\frac{k^2+k}{n}>2k-1[/texx]

porque [texx]1>\frac{k^2+k}{n}[/texx].



Título: Re: k-ésima potencia de un grafo y notación
Publicado por: Luis Fuentes en 02 Diciembre, 2019, 03:40
Hola

 Está bien.

Saludos.