grafos:raioevertices [WikiMat]

Essa página está em modo somente de leitura. Você pode visualizar a fonte, mas não alterá-la. Informe-se com o administrador do Wiki, caso você ache que isso está incorreto.
=====  Relação entre o raio de um grafo e o seu número de vértices =====

<WRAP round box 80%>
=== Teorema ===
//Seja $G$ um grafo de [[.defraiograf|raio]] máximo $k$ e [[.grauV| grau máximo]] no máximo $d \geq 3$,então $V(G)$ tem menos que $\frac{d}{d-2}(d-1)^k$ vértices.//
</WRAP>

<WRAP round box 100%>
//**Demonstração:**//

Vamos tomar $z$ como o [[.defCentral|vértice central]] de $G$ e tomemos $D_i$ os conjuntos dos vértices que distam $i$ arestas de $z$. Podemos ver isso como "círculos" em torno de $z$, como um sonar.
É simples visualizar que $V(G)=\bigcup_{i=0}^k D_i$, e claramente $|D_0| = 1$ e $|D_1| \leq d$.

Para $i \geq 1$ temos que $|D_{i+1}| \leq (d-1)|D_i|$, pois cada vértice em $D_{i+1}$ é [[.vizinhosDeV| vizinho]] de um vértice de $D_i$ e cada vértice $D_i$ possui no máximo $(d-1)$ vizinhos em $D_{i+1}$ (pois pode haver outro vizinho em $D_{i-1}$). Portanto, $|D_{i+1}| \leq d(d-1)^i$ para todos $i<k$ por indução. Isso nos dá:

$$|V| \leq 1 + d \sum_{i=0}^{k-1} (d-1)^i = 1 + \frac{d}{d-2}((d-1)^k - 1) < \frac{d}{d-2}(d-1)^k.$$
$$\Downarrow$$
$$|V| < \frac{d}{d-2}(d-1)^k$$

Assim sendo, o Teorema segue.

<wrap right>$\square$</wrap>
</WRAP>

----

Da mesma forma, podemos limitar a ordem de $G$ de baixo para cima assumindo que tanto seu grau mínimo quanto sua circunferência são grandes. Para $d \in \mathbb{R}$ e $g \in \mathbb{N}$ deixe

$$n_0(d,g) := \begin{cases} 1+d \sum_{i=0}^{r-1}(d-1)^{i},& \mbox{se } g =: 2r+1 &\mbox{é ímpar;}\\ \\ 2 \sum_{i=0}^{r-1}(d-1)^{i}, & \mbox{se } g =: 2r & \mbox{é par.} \end{cases}$$

Não é difícil provar que um grafo de grau mínimo $\delta$ e circunferência $g$ tem pelo menos $n_0(\delta,g)$ vértices. Curiosamente, pode-se obter o mesmo limite para seu grau médio:

<WRAP round box 100%>
=== Teorema ===
//Seja $G$ um grafo. Se $d(G) \geq d \geq 2$ e $g(G) \geq g \in \mathbb{N}$, então $|G| \geq n_0(d,g)$.//
</WRAP>

Um aspecto do Teorema acima é que ele garante a existência de um ciclo curto em comparação com $|G|$. 

<WRAP round box 100%>
=== Corolário ===
//Se $\delta(G) \geq 3$, então $g(G) < 2 \log |G|$.//
</WRAP>

<WRAP round box 100%>
//**Demonstração:**//

Se $g := g(G)$ é par, então:

$$n_0(3,g) =2 \frac{2^{g/2}-1}{2-1} = 2^{g/2} + (2^{g/2}-2) > 2^{g/2},$$

enquanto se $g$ é ímpar, temos:

$$n_0(3,g) = 1 + 3 \frac{2^{(g-1)/2}-1}{2-1} = \frac{3}{\sqrt{2}}2^{g/2} -2 > 2^{g/2}.$$

Como $|G| \geq n_0(3,g)$, o resultado segue.

<wrap right>$\square$</wrap>
</WRAP>