8 Grafos especiales

grafos $k$-regulares	$d(G)=\epsilon(G)=k\;\;(=\delta(G)=\Delta(G))$
grafos completos $K^r$	$G=(V,[V]^2), \vert V\vert=r$
caminos: $P^k$	$G=(\{v_0,\dots,v_k\},\{v_0v_1,v_1v_2,\dots v_{k-1}v_k\})$
ciclos $C^k$	$G=(\{v_0,\dots,v_k\},\{v_0v_1,v_1v_2,\dots v_{k-1}v_0\})$

Obviamente se puede describir un camino o ciclo por su secuencia de vértices.

Vocabulario:

longitud	número de aristas de un camino o ciclo
cíclico	un grafo que contiene un ciclo es cíclico
acíclico	un grafo que no contiene ningún ciclo es acíclico
cintura	un ciclo mínimo que un grafo contiene
circumferencia	ciclo máximo que un grafo contiene

Notaciones:

$g(G)$	longitud de la cintura de $G$, ($g(G)=\infty$ si $G$ acíclico)
$D(G)$	longitud de la circumferencia de $G$ ($D(G)=0$ si $G$ acíclico)

grafos bipartidos $B$

grafos bipartidos completos $K^{n_1,n_2}$

hipercubos $Q^k$

Propiedades (con excepciones para $Q^0$ y $Q^1$):

• $n=\vert V\vert=2^k$
• $k$-regular
• bipartidos (¿Cómo particionar?)
• $g(Q^k)=4$
• $D(Q^k)=2^k$ (¿Cuál es un ciclo máximo?)