%% Antes de processar este arquivo LaTeX (LaTeX2e) deve %% verificar que o arquivo TEMA.cls estah no mesmo %% diretorio. O arquivo TEMA.cls pode ser obtido do %% endereco www.sbmac.org.br/tema. \documentclass{TEMA} \usepackage[brazil]{babel} % para texto em Português %\usepackage[english]{babel} % para texto em Inglês \usepackage[latin1]{inputenc} % para acentuação em Português %\input{P-margin.inf} \usepackage[dvips]{graphics} \usepackage{subfigure} \usepackage{graphicx} \usepackage{epsfig} \newcommand{\B}{{\tt\symbol{92}}} \newcommand{\til}{{\tt\symbol{126}}} \newcommand{\chap}{{\tt\symbol{94}}} \newcommand{\agud}{{\tt\symbol{13}}} \newcommand{\crav}{{\tt\symbol{18}}} \begin{document} %******************************************************** \title {Produto Funcional de Grafos} \author {A. R. G. Lozano% \thanks{arglozano@terra.com.br}\,, Departamento de Matemática da FFP-UERJ. \\ Escola de Ciências, Educação, Letras, Artes e Humanidades da UNIGRANRIO, Grupo de Pesquisa em Matemática Discreta e Computacional. \\ \\ A. S. Siqueira% \thanks{asiqueira@unigranrio.com.br}\,, Escola de Ciências, Educação, Letras, Artes e Humanidades da UNIGRANRIO, Grupo de Pesquisa em Matemática Discreta e Computacional. \\ \\ S. Jurkiewicz% \thanks{jurki@pep.ufrj.br}\,, Programa de Engenharia da Produção da COPPE-UFRJ. \\ \\ C. V. P. Friedmann% \thanks{cliciavp@terra.com.br}\,, Departamento de Matemática da FFP-UERJ. \\ Grupo de Pesquisa em Matemática Discreta e Computacional. } \criartitulo \runningheads {Lozano et al.}{Produto funcional de grafos} \begin{abstract} {\bf Resumo}. O trabalho apresenta uma generalização do produto cartesiano de grafos que denominamos de produto funcional de grafos. Provam-se algumas propriedades do novo produto e mostra-se uma aplicação do mesmo, que consiste em gerar grafos regulares que admitem coloração com folga $\Delta$ com $\Delta +1$ cores. {\bf Palavras-chave}. Produto funcional de grafos, Coloração com folga, Grafo suporte. \end{abstract} %******************************************************** \newsec{Introdução} \hspace{0.3cm} Em 2008 Lozano, Jurkiewicz e Friedmann \cite{LOZC} apresentaram um algoritmo para troca completa de informações que não dependia da topologia da rede. Para isto, usaram a coloração total equilibrada dos grafos correspondentes às topologias mais comuns e mostraram que tais colorações satisfaziam a Conjectura de Vizing, ou seja, os grafos podiam ser coloridos totalmente com, no máximo, $\Delta+2$ cores. Posteriormente Lozano, Siqueira e Jurkiewicz \cite{LOZA} provaram que, se um grafo regular pode ser colorido com folga $\Delta$ com $\Delta + 1$ cores então a coloração de vértices pode ser completada obtendo-se uma coloração total equilibrada com, no máximo, $\Delta+2$ cores. O resultado acima citado serviu como motivação para estudar a possibilidade de se construir famílias de grafos regulares com as características mencionadas. Para auxiliar nesta construção, introduziu-se o conceito de produto funcional de grafos e suas propriedades, que são explorados na terceira seção deste artigo. Em seguida apresentamos uma das maneiras de obter estas famílias de grafos regulares usando o produto funcional, e finalizamos com uma seção onde são expostas as perspectivas de trabalhos futuros. Neste texto, os grafos são simples, não orientados e sem laços. \\ \newsec{Definições básicas e notações} \hspace{0.5cm} Ao longo do artigo serão usadas as notações listadas a seguir: \begin{itemize} \item $\{u,v \}$ ou $uv$ denota uma aresta do grafo $G$, onde $u$ e $v$ são adjacentes; \item $d_G(v)$ ou $d(v)$ se não houver ambiguidade, denota o grau do vértice $v$ no grafo $G$; \item $\Delta(G)$ ou $\Delta$ se não houver ambiguidade, denota o grau máximo do grafo $G$; \item $N_G(v)$ ou $N(v)$ se não houver ambiguidade, denota o conjunto de os todos vértices adjacentes ao vértice $v$ no grafo $G$; \item $F(X)$ denota o conjunto de todas as bijeções de $X$ em $X$; \item $D(G)$ denota o digrafo obtido pela substituição de cada aresta $uv$ do grafo $G$ pelos arcos $(u,v)$ e $(v,u)$, mantendo o mesmo conjunto de vértices; \item $\mathcal{D}$ denota o conjunto dos digrafos que satisfazem as seguintes condições: \begin{enumerate} \item $(u,v)$ é um arco do digrafo se, e somente se, $(v,u)$ também é um arco do digrafo, \item Não existem dois arcos iguais. \end{enumerate} \item Se $\overrightarrow{G} \in \mathcal{D}$, $G(\overrightarrow{G})$ denota o grafo obtido pela substituição de cada par de arcos $(u,v)$ e $(v,u)$ de $\overrightarrow{G}$ pela aresta $uv$, mantendo o mesmo conjunto de vétices; \item $I_n$ denota o conjunto de números naturais $\{ 0,1,2,3,4, ..., n-1 \}$; \item Se $A$ é um conjunto, $|A|$ denota a cardinalidade de $A$; \item $E(X)$ ou $E$ se não houver ambiguidade, denota o conjunto de arestas (arcos) do grafo (digrafo) $X$; \item $V(X)$ ou $V$ se não houver ambiguidade, denota o conjunto de vértices do grafo (digrafo) $X$ ; \item $C_n$ denota o ciclo de $n$ vértices; \item $K_n$ denota o grafo completo de $n$ vértices.\\ \end{itemize} \begin{defTEMAp}\cite{BONDY} Sejam um grafo $G(V,E)$, um conjunto $S \subset (E \cup V)$, um número natural $k$ e um conjunto arbitrário $C=\{c_1, c_2, \cdots, c_k \}$ cujos elementos são denominados de cores. Uma \textbf{coloração} do grafo $G$ com as cores de $C$ é uma aplicação $f: S \rightarrow C$. \end{defTEMAp} Na definição acima, se $S=V$ então tem-se uma \textbf{coloração de vértices}. No caso de $S=E$, trata-se de uma \textbf{coloração de arestas} e finalmente, se $S=E \cup V$, então $f$ é uma \textbf{coloração total}. Se $x \in S$ e $f(x)=c_i, \; i \in \{1,2, \cdots, k \}$, diz-se que $x$ possui ou está colorido com a cor $c_i$.\\ \begin{defTEMAp}\cite{BONDY} Sejam um grafo $G(V,E)$, um conjunto $S \subset (E \cup V)$ e um conjunto de cores $C=\{c_1, c_2, ...,c_k \}$, onde $k$ é um número natural. Uma coloração $f: S \rightarrow C$ do grafo $G$ com as cores de $C$ é uma \textbf{coloração própria}, se para todo par $x,y \in S$ tem-se que, se $x$ é adjacente ou incidente a $y$ então $f(x) \neq f(y)$. \end{defTEMAp} Deste ponto em diante, todas as colorações neste trabalho serão consideradas próprias e sobrejetivas, a menos que explicitamente se especifique o contrário. \begin{defTEMAp}\cite{YAP} Dados um grafo $G(V,E)$, um conjunto $S \subset (E \cup V)$ e um conjunto de cores $C=\{c_1, c_2, ...,c_k \}$, onde $k$ é um número natural. Uma coloração $f: S \rightarrow C$ do grafo $G$ com as cores de $C$ é uma \textbf{coloração equilibrada}, se para todo par $i,j \in \{1,2, \cdots, k \}$ tem-se que, $||f^{-1}(c_i)|-|f^{-1}(c_j)|| \leq 1$, sendo $|f^{-1}(c_i)|$ e $|f^{-1}(c_j)|$ as cardinalidades dos conjuntos dos elementos de $S$ que possuem as cores $c_i$ e $c_j$, respectivamente. \end{defTEMAp} \begin{defTEMAp}\cite{LOZR} Sejam um grafo $G(V,E)$, um conjunto de cores $C=\{c_1, c_2, ...,c_k \}$, onde $k$ é um número natural, e um número natural $p$, tal que $p \leq \Delta(G)$. Uma aplicação $f: S \rightarrow C$ é uma \textbf{coloração de vértices} do grafo $G$ com as cores de $C$ \textbf{com folga }$p$, se para todo $v \in V$ tem-se que se $d(v) < p$, então $|c(N(v))| = d(v)$, caso contrário, $|c(N(v))| = p$, sendo $|c(N(v))|$ a cardinalidade do conjunto das cores da vizinhança de $v$. \end{defTEMAp} \begin{defTEMAp}\cite{YAP} Um grafo $G$ é de \textbf{classe 1} se admite uma coloração própria de arestas com $\Delta(G)$ cores, caso contrário é de \textbf{classe 2}. \end{defTEMAp} \newsec{Produto funcional de grafos} \hspace{0.5cm}Nesta seção é apresentada a definição de produto funcional de grafos, para este fim, é necessário definir aplicações, denominadas aplicações de ligação, que associam cada aresta de um fator com uma bijeção definida no conjunto de vértices do outro. Esta bijeção indica como será feita a ligação dos vértices do grafo produto. O produto cartesiano de grafos pode ser visto como um produto funcional, onde a todas as arestas são associadas à aplicação identidade correspondente. \begin{defTEMAp} Os \textbf{digrafos} $\overrightarrow{G}_1(V_1,E_1)$ e $\overrightarrow{G}_2(V_2,E_2)$ são ditos \textbf{funcionalmente ligados} pelas aplicações $f_1:E_1 \rightarrow F(V_2)$ e $f_2:E_2 \rightarrow F(V_1)$ se $f_1$ e $f_2$ são tais que: \begin{enumerate} \item Se para todo arco $(u, v) \in E_1$ se $(v, u) \in E_1$, então $f_1((u,v))=(f_1((v,u)))^{-1}$ \item Se para todo $(x, y) \in E_2$ se $(y, x) \in E_2$, então $f_2((x,y))=(f_2((y,x)))^{-1}$ \item \label{ligf} Para todo par de arcos $(u, v) \in E_1$ e $(x, y) \in E_2$, tem-se que $f_2((x,y))(u) \neq v$ ou $f_1((u,v))(x) \neq y$ \end{enumerate} As aplicações $f_1$ e $f_2$ são denominadas \textbf{aplicações de ligação}.\\ \end{defTEMAp} \begin{defTEMAp} Sejam dois grafos $G_1(V_1,E_1)$ e $G_2(V_2,E_2)$. Se $D(G_1)$ e $D(G_2)$ são funcionalmente ligados pelas aplicações $f_1:E(D(G_1)) \rightarrow F(V_2)$ e $f_2:E(D(G_2)) \rightarrow F(V_1)$, então os \textbf{grafos} $G_1(V_1,E_1)$ e $G_2(V_2,E_2)$ são ditos \textbf{funcionalmente ligados} pelas mesmas aplicações. \end{defTEMAp} \begin{defTEMAp} Sejam $\overrightarrow{G}_1(V_1,E_1)$ e $\overrightarrow{G}_2(V_2,E_2)$ \textbf{digrafos} funcionalmente ligados pelas aplicações $f_1:E_1 \rightarrow F(V_2)$ e $f_2:E_2 \rightarrow F(V_1)$. O \textbf{produto funcional} do digrafo $\overrightarrow{G}_1$ pelo digrafo $\overrightarrow{G}_2$ segundo as aplicações $f_1$ e $f_2$, denotado por $(\overrightarrow{G}_1,f_1)\times (\overrightarrow{G}_2,f_2)$, é o digrafo $\overrightarrow{G^*}(V^*,E^*)$ definido por: \begin{itemize} \item $V^*=V_1 \times V_2$. \item $((u,x),(v,y)) \in E^*$ se, e somente se, uma das seguintes condições for verdadeira: \begin{enumerate} \item $(u,v) \in E_1$ e $f_1((u,v))(x)=y$ \item $(x,y) \in E_2$ e $f_2((x,y))(u)=v$. \end{enumerate} \end{itemize} \end{defTEMAp} A Figura \ref{fig1} apresenta dois digrafos com suas respectivas aplicações de ligação e o digrafo obtido como resultado do produto de ambos os pares. \begin{defTEMAp} Sejam $G_1(V_1,E_1)$ e $G_2(V_2,E_2)$ \textbf{grafos} funcionalmente ligados pelas aplicações $f_1:E(D(G_1)) \rightarrow F(V_2)$ e $f_2:E(D(G_2)) \rightarrow F(V_1)$. O \textbf{produto funcional} do grafo $G_1$ pelo grafo $G_2$, denotado por $(G_1,f_1) \times (G_2,f_2)$, é o grafo $G(\overrightarrow{G^*}(V^*,E^*))$, sendo $\overrightarrow{G^*}(V^*,E^*)=(D(G_1),f_1)\times (D(G_2),f_2)$. \end{defTEMAp} \begin{figure}[h!] %\includegraphics{fig2.eps} \centering \scalebox{0.45}{\includegraphics{PfunDigraf.eps} } % \caption{Produto funcional de dois digrafos} % \label{fig1} \end{figure} É interessante notar que o Produto Cartesiano de Grafos é um caso particular do Produto Funcional de Grafos definido acima, quando $f_1$ e $f_2$ atribuem a identidade a todos os arcos dos digrafos correspondentes. A seguir será definido um tipo especial de bijeção, denominado rotação. \begin{defTEMAp} Dado um número natural $n$, uma \textbf{rotação em $I_n$} é uma bijeção $f : I_n \rightarrow I_n$ definida como segue: $f(i) = (i + k) (\mbox{mod } n)$, onde o número natural $k$ é constante. \end{defTEMAp} \begin{defTEMAp} Sejam $n$ um número natural e $A$ um conjunto finito tal que $|A|=n$. Uma bijeção $f: A \rightarrow A$ é uma \textbf{rotação em $A$}, se existem, uma bijeção $h: I_n \rightarrow A$ e uma rotação $r$ em $I_n$ tais que $f(h(i))=h(r(i))$, para todo $i \in I_n $. \end{defTEMAp} \hspace{0.5cm}Observe que, na definição acima, se $h(i)$ é representado por $x_i$, tem-se que $f(h(i))=h(r(i))=x_{r(i)}$. Isso significa que para conhecer a rotação, basta conhecer o valor em $x_0$. Neste texto \textbf{\emph{$r_i(A)$}} denotará a rotação em $A$ tal que $r(h(0))=h(i)$. Se não existir ambiguidade, tal rotação será representada simplesmente por $r_i$.\\ \hspace{0.5cm}A Figura \ref{fig2} representa o produto funcional do caminho $P_3$ por ele mesmo, associado a duas diferentes aplicações de ligação (as rotações $r_1$ e $r_2$). Na figura, cada vértice da forma $(v_i,v_j)$ é representado por $v_iv_j$ e as linhas descontínuas descrevem as arestas do produto cartesiano usual de grafos. \\ \begin{figure}[h!] %\includegraphics{fig2.eps} \centering \scalebox{0.45}{\includegraphics{PfunGraf.eps} } % \caption{Produto funcional de dois grafos} % \label{fig2} \end{figure} Os teoremas a seguir mostram algumas proriedades do produto funcional. \begin{teoTEMA} Sejam $G_1(V_1,E_1)$ e $G_2(V_2,E_2)$ grafos funcionalmente ligados pelas aplicações $f_1:E(D(G_1)) \rightarrow F(V_2)$ e $f_2:E(D(G_2)) \rightarrow F(V_1)$. Então os grafos $G^*(V^*,E^*)=(G_1,f_1) \times (G_2,f_2)$ e $G^{**}(V^{**},E^{**})=(G_2,f_2) \times (G_1,f_1)$ são isomorfos. Neste sentido, o produto funcional de grafos é comutativo. \end{teoTEMA} \begin{proof} Sejam $E'_1=E(D(G_1))$ e $E'_2=E(D(G_2))$. Provaremos que dados dois vértices $(u,x) \in V^*$ e $(v,y) \in V^*$, então a aresta $\{(u,x),(v,y) \} \in E^*$ se, e somente se, a aresta $\{(x,u),(y,v) \} \in E^{**}$. Tem-se que $\{(u,x),(v,y) \} \in E^*$ se, e somente se: \begin{enumerate} \item[1-]$(u,v) \in E'_1 \;$ e $f_1((u,v))(x)=y \; $ e $(v,u) \in E'_1 \;$ e $f_1(v,u)(y)=(f_1((u,v)))^{-1}(y)=x$ $\;$ ou \item[2-] $(x,y) \in E'_2 \;$ e $f_2((x,y))(u)=v \; $ e $(y,x) \in E'_2 \;$ e $f_2(y,x)(v)=(f_2((x,y)))^{-1}(v)=u $. \end{enumerate} $\{(x,u),(y,v) \} \in E^{**}$ se, e somente se: \begin{enumerate} \item[3-] $(x,y) \in E'_2 \;$ e $f_2((x,y))(u)=v \;$ e $(y,x) \in E'_2 \;$ e $f_2(y,x)(v)=(f_2((x,y)))^{-1}(v)=u$ $\;$ou \item[4-]$(u,v) \in E'_1 \;$ e $f_1((u,v))(x)=y \;$ e $(v,u) \in E'_1 \;$ e $f_1(v,u)(y)=(f_1((x,y)))^{-1}(y)=x$.\\ Como 1 é equivalente a 4 e 2 é equivalente a 3 o teorema está provado. \end{enumerate} \end{proof} \begin{teoTEMA} Sejam $G_1=(V_1,E_1)$ e $G_2=(V_2,E_2)$ grafos funcionalmente ligados pelas aplicações $f_1: E_1 \rightarrow F(V_2)$ e $f_2: E_2 \rightarrow F(V_1)$. Para todo vértice $(u,x)$ do grafo $G^*=(V^*,E^*)=(G_1,f_1) \times (G_2,f_2)$ tem-se que: $d_{G^*}((u,x))=d_{G_1}(u)+d_{G_2}(x)$. \end{teoTEMA} \begin{proof} Para cada $(u,x) \in V^*$, denota-se por $E_{G^*}((u,x))$ o conjunto de arestas incidentes nesse vértice no grafo $G^*$. Constrói-se a aplicação $h_1:N_{G_1}(u) \rightarrow E_{G^*}((u,x))$ da seguinte forma: $h_1(v)=\{(v,y),(u,x)\}$ onde $y \in V_2$ é tal que $f_1((u,v))(x)=y$ com $(u,v) \in E(D(G_1))$; $y$ existe pois $f_1((u,v))$ é bijetiva. Por outro lado $h_1$ é injetiva, pois se $v_1,v_2 \in N_{G_1}(u)$ e $v_1 \neq v_2$ então necessariamente ${(v_1,y_1)(u,x)} \neq {(v_2,y_2)(u,x)}$ independentemente do valor de $y_1$ e $y_2$. De forma semelhante, construimos $h_2:N_{G_2}(x) \rightarrow E_{G^*}((u,x))$. Se uma aresta é incidente em $(u,x)$ no grafo $G^*$ ela tem a forma $\{(u,x),(v,y)\}$ logo existe $(u,v) \in E(D(G_1))$ tal que $f_1((u,v))(x)=y$ ou $(x,y) \in E(D(G_2))$ tal que $f_2((x,y))(u)=v$. Por construção de $h_1$ e $h_2$ tem-se que $h_1(N_{G_1}(u))\cup h_2(N_{G_2}(v))=E_{G^*}((u,x))$. Por outro lado, se $\{ (u,x), (v,y)\} \in h_1(N(u))$ e $\{ (u,x), (v,y)\} \in h_2(N(v))$ então existem arcos $(u,v) \in E(D(G_1))$ e $(x,y) \in E(D(G_2))$ tais que $f_1((u,v))(x)=y$ e $f_2((x,y))(u)=v$ o que contradiz a condição \ref{ligf} da definição de aplicações de ligação logo, $h_1(N_{G_1}(u)) \cap h_2(N_{G_2}(v))=\phi$. Podemos agora construir a bijeção \\ $h: N_{G_1}(u) \cup N_{G_2}(x) \rightarrow E_{G^*}((u,v))$, definida por $h(a)=\left\{ \begin{array}{ll} h_1(a) & se \; a \in N_{G_1}(u)\\ h_2(a) & se \; a \in N_{G_2}(x) \end{array} \right..$ O que conclui a prova do teorema. \end{proof} Do teorema anterior se obtém, de forma imediata, o seguinte corolário. \begin{coroTEMAp}\label{coro1} Sejam $G_1=(V_1,E_1)$ e $G_2=(V_2,E_2)$ grafos funcionalmente ligados pelas aplicações $f_1: E_1 \rightarrow F(V_2)$ e $f_2: E_2 \rightarrow F(V_1)$, então o grafo $G^*=(V^*,E^*)=(G_1,f_1) \times (G_2,f_2)$ tem grau máximo $\Delta(G^*)=\Delta(G_1)+\Delta(G_2)$. \end{coroTEMAp} Em relação à conexidade, o produto funcional de grafos conexos não é necessarimamente conexo como mostra a Figura \ref{fig3}, mas também é possível obter um grafo conexo como resultado do produto funcional de dois grafos desconexos. O teorema abaixo oferece uma condição que garante a conexidade do grafo produto funcional, caso os fatores sejam conexos. \begin{figure}[h] %\includegraphics{fig2.eps} \centering \scalebox{0.6}{\includegraphics{NaoConexo.eps} } % \caption{Produto funcional desconexo de dois grafos conexos} % \label{fig3} \end{figure} \begin{teoTEMA} Dados dois grafos $G_1=(V_1,E_1)$ e $G_2=(V_2,E_2)$ conexos e funcio\-nalmente ligados pelas aplicações $f_1: E_1 \rightarrow F(V_2)$ e $f_2: E_2 \rightarrow F(V_1)$, se $f_1$ ou $f_2$ atribui a identidade a todos os arcos do digrafo correpondente, então o produto funcional de $G_1$ por $G_2$ segundo $f_1$ e $f_2$ é conexo. \end{teoTEMA} \begin{proof} Sem perda de generalidade, suponhamos que $f_2$ atribui a identidade a todos os arcos de $D(G_2)$. Sejam $G^*(V^*,E^*)=(G_1,f_1) \times (G_2,f_2)$, $(u,x)$ e $(v,y)$ dois vértices de $G^*$. Como $G_1$ é conexo, existe um caminho $ux_1 \cdots x_p$ com $x_p=v$ em $G_1$. Sejam agora $z_1=f_1((u,x_1))(x)$, $z_{i+1}=f_1((x_{i},x_{i+1}))(z_i)$, $i=1,...,p-1$, consequentemente existe um caminho $P_1=(u,x)(x_1,z_1)(x_2,z_2) \cdots (v,z_p)$ em $G^*$. Como $G_2$ é conexo, existe um caminho $z_py_1 \cdots y_q$ com $y_q=y$ em $G_2$, e como $f_2(e)(v)=v$ para toda aresta $e \in E_2$, então $P_2=(v,z_p)(v,y_1) \cdots (v,y)$ é um caminho em $G^*$. A união de $P_1$ e $P_2$ proporciona um caminho entre $(u,x)$ e $(v,y)$. \end{proof} O Produto Cartesiano de dois Grafos é conexo se, e somente se, ambos os fatores forem conexos, e para mais detalhes, pode-se consultar \cite{VIZI, SABI}. Observe que esse resultado é uma consequência do teorema anterior, pois no Produto Cartesiano de Grafos, as aplicações de ligação $f_1$ e $f_2$ atribuem a identidade a todos os arcos dos digrafos correpondentes. Esse teorema impõe uma condição forte sobre uma das aplicações de ligação para que o produto funcional seja conexo. Mas, neste artigo, tal condição é suficiente para construir famílias de grafos conexos que admitem coloração com folga $\Delta$ com $\Delta+1$ cores, que foi a motivação inicial para a introdução do produto funcional. De qualquer forma, uma proposta de trabalho futuro é determinar condições mais fracas para as aplicações de ligação. \newsec{Uma aplicação do produto funcional \label{sec}} \hspace{0.3cm}Nesta seção, mostraremos alguns resultados relativos à construção de famílias de grafos regulares que admitem uma coloração com folga $\Delta$ com $\Delta+1$ cores. Para um estudo mais detalhado, bem como outros resultados pode-se consultar \cite{LOZA}. Muitos grafos usados como grafos suporte para topologias de redes de interconexão, são obtidos mediante o produto cartesiano de grafos, como é o caso do hipercubo, mas nem sempre estes grafos admitem uma coloração com folga $\Delta$ com $\Delta+1$ cores (como é o caso do toro $C_3 \times C_5$, ilustrado na Figura \ref{fig4}). Com uma modificação adequada, pode-se obter um grafo que admite a coloração desejada mantendo as caracteristicas dos grafos suporte de redes (no que diz repeito à diâmetro, conexidade, regularidade, etc). As definições e teoremas a seguir exploram a ideia anterior. \begin{figure}[h] \centering % \subfigure[Produto cartesiano de $C_3$ e $C_5$]{\scalebox{1}{\includegraphics[height=4.5cm,width=5cm]{toro531art.eps}} } % \hspace{1cm} % \subfigure[Modificação do grafo $C_3 \times C_5$]{\scalebox{1}{\includegraphics[height=4.5cm,width=5cm]{toro532art.eps}} } % \caption{$C_3 \times C_5$ e $C_3 \times C_5$ modificado, coloridos com $5$ ``cores'' } % \label{fig4} \end{figure} \begin{defTEMAp}[Grafo k-suporte] \label{conj1} Dado um número natural $k$, $k \geq 3$, o grafo $G=(V,E)$, é um k-suporte se satisfaz as seguintes condições \begin{enumerate} \item $G$ é um grafo regular de grau $k-3$; \item Existe uma aplicação $f:E(G) \rightarrow F(I_k)$, tal que $G$ e $C_{k}$ estão funcionalmente ligados por $f$ e \textbf{Id}, onde \textbf{Id}$: E(C_{k}) \rightarrow F(I_{|V|})$ é a aplicação que a cada arco de $D(C_{k})$ faz corresponder a função identidade; \item O grafo $G^*=(f_1,G) \times (\mbox{\textbf{Id}},C_{k})$ pode ser colorido com folga $\Delta(G^*)$ com $\Delta(G^*)+1$ cores. \end{enumerate} \end{defTEMAp} \begin{teoTEMA}\label{teo1} Se $G(V,E)$ é um grafo k-regular de classe 1, então $G$ é (k+3)-suporte. \end{teoTEMA} \begin{proof} Sejam $V=\{v_1, v_2, \cdots, v_n \}$, $V(C_{k+3})= \{u_0, u_1, \cdots, u_{k+2} \}$, $C=\{2,3,4 \cdots, k+1 \}$ um conjunto e $c:E \rightarrow C$, uma coloração de arestas de $G$ usando o conjunto $C$. Dividiremos o restante da prova em dois casos: \newcounter{caso} \begin{list}{\textbf{Caso \arabic{caso}.}}{\usecounter{caso} \setlength{\labelwidth}{-2mm} \setlength{\parsep}{0mm} \setlength{\leftmargin}{0mm}} \renewcommand{\labelenumi}{(\alph{enumi})} \item \label{caso1} $k=\Delta(G)$ é par:\\ Denotamos por $i'$ o número $(k+3)-i$, para todo $i \in \{2,3, \cdots, (\frac{k}{2}+1)\}$. Veja agora que $i+i'=0 \; (mod \;\;\; k+3)$, e que para cada par $\{i, \, i' \}$ o subgrafo $G_i(V_i, E_i)$ induzido pelo conjunto de arestas $\{e \in E:c(e)=i \; ou \; c(e)=i' \}$ é um grafo regular de grau $2$ e que $V=V_i$. Logo, as componentes conexas de cada subgrafo $G_i$, são ciclos $G_{i1}, \cdots,G_{it_i}$,onde $t_i$ é um número natural, $t_i \leq \lfloor \frac{n}{3} \rfloor$, e cada ciclo $G_{ij}$ está associado a dois ciclos orientados $\overrightarrow{G}^{1}_{ij}$ e $\overrightarrow{G}^{2}_{ij}$ em $D(G)$. Definimos as aplicações $f_1:E(D(G)) \rightarrow V(C_{\Delta+3})$, $f_2:E(D(C_{\Delta+3}))\rightarrow V$ como segue:\\ $f_1(x) =\left\{ \begin{array}{ll} r_i & se \;\; x \in E(\overrightarrow{G}^{1}_{ij}); \; i \in \{ 2,3, \cdots, \frac{k}{2}+1\}; \; j \in \{ 1,2, \cdots t_i\} \\ \\ r_{i'} & se \;\; x \in E(\overrightarrow{G}^{2}_{ij}); \; i \in \{ 2,3, \cdots, \frac{k}{2}+1\}; \; j \in \{ 1,2, \cdots t_i\} \end{array} \right. $ \\ \\ $f_2(x)=Id(x)$ para todo arco $x \in D(C_{\Delta+3})$, onde $Id$ representa a função identidade.\\ Sejam agora $G^*=(f_1,G_1) \times (f_2,C_{k+3})$, $V^*=V(G^*)$, $E^*=E(G^*)$, A coloração $f:V^* \rightarrow \{ 0,1, \cdots ,(k+2) \}$ definida por: $f((v_i,u_j))=j$, $i=1,2, \cdots, n$; $j=0,1,2, \cdots, (k+2)$ é uma coloração com folga $\Delta(V^*) $ com $\Delta(V^*) +1$ ``cores'' do grafo $G^*$. O conjunto de ``cores'' $\{ 0, 1, \cdots, (k+2)\}$ possui $k +3$ elementos e pelo corolário \ref{coro1} $G^*$ é um grafo regular de grau $\Delta(G)+\Delta(C_{k+3})=k+2$. Para analisar que a coloração tem folga $\Delta(G^*)$, observe que por simetria basta analisar um vétice de $V^*$, por exemplo $(v_1,u_0)$, seja $N_G(v_1)=\{ x_2, ...,x_{k+1}\}$, por facilidade e sem perder generalidade vamos supor que $c(v_1x_j)=j \, , j\in \{2, ...,k+1 \}$ (na verdade cada aresta incidente a $v_1$ possui uma cor diferente) então os extremos dos arcos de $(f_1,\overrightarrow{G}_1) \times (f_2,\overrightarrow{C}_{\Delta^+3})$ que tem como origem $( v_1,u_0)$ são $(v_1,u_1)$, $(v_1,u_{k+2})$, $(x_2, u_2)$, $(x_3, u_3)$,$(x_4, u_4)$, ..., $(x_{k+1}, u_{k+1})$ coloridos com as ``cores'' $1, k+2, 2,3, ...,k+1$ respectivamente, logo a coloração possui folga $\Delta$. \item $k=\Delta(G)$ é ímpar: \\ Observe que $2+(k+1)=3+k= 4+(k-1) \cdots =(\frac{k-1}{2}+1)+(\frac{k+3}{2}+1)=(\frac{k+1}{2}+1)+(\frac{k+1}{2}+1)=k+3$, e denotamos por $i'$ o número $(k+3)-i$, para todo $i \in \{2,3, \cdots, (\frac{k+1}{2}+1)\}$. Agora o subgrafo $G_i(V_i, E_i)$ induzido pelo conjunto de arestas $\{e \in E:c(e)=i \; ou \; c(e)=i' \}$ $i \in \{2,3, \cdots, (\frac{k-1}{2}+1)\}$ é um grafo regular de grau $2$, e o subgrafo $G_{a}$, com $a=\frac{k+1}{2}+1$, induzido pelo conjunto de arestas $\{e \in E:c(e)=\frac{k+1}{2}+1 \}$ é um emparelhamento perfeito, e o raciocinio seguido no caso \ref{caso1}, é válido, o que prova o teorema. \end{list} \end{proof} A figura \ref{teo24}(a) mostra um grafo 3-regular de classe 1, colorido com os elementos do conjunto $\{ 2,3,4 \}$. As setas indicam que ao fazer o produto funcional no sentido indicado é usada a rotação $r_3$ ou $r_4$ segundo o caso. Já no sentido contrário a $r_4$, é usada $r_2$ pois $4+2=0 \; (mod \; 6)$, e no sentido contrário a $r_3$ é usada $r_3$ pois $3+3=0 \; (mod \; 6)$. A figura \ref{teo24}(b) ilustra o produto funcional com o ciclo $C_6$, mas como o número de arestas é muito grande, foram representadas apenas as arestas que tem como extremo o vértice $0$ de algum ciclo. \begin{figure}[h!] %\includegraphics{fig2.eps} \centering \scalebox{0.8}{\includegraphics{Teo24.eps} } % \caption{Grafo 3-regular de classe 1 usado como 6-suporte.} % \label{teo24} \end{figure} \begin{teoTEMA} Se $G(V,E)=$ é um grafo completo então $G$ é um $(|V|+2)$-suporte. \end{teoTEMA} \begin{proof} Seja $G(V,E)=K_n$. Se $n$ é par então $G$ é de classe 1 e o teorema está provado, logo vamos supor que $n$ é ímpar. Sejam $V=\{v_0, v_1, ...,v_{n-1} \}$ e $c:E \rightarrow C=\{0,1,2,\cdots, n \}$ uma coloração de arestas de $G$ definida por $c({v_i,v_j})=\frac{(n+1)}{2}(i+j) \; (mod \; n)$; $i,j \in \{0,1, \cdots, n-1 \}; \; i \neq j$. É claro que $c$ é própria pois fixando $i_0 \in \{0,1, \cdots, n-1 \}$, temos que $\frac{(n+1)}{2}(i_0+j_0) \equiv \frac{(n+1)}{2}(i_0+j_1) \; (mod \; n)$ se, e somente se, $j_0 \equiv j_1 \; (mod \; n)$. Antes de continuar com a prova do teorema, provaremos a seguinte, propriedade de $c$: se $c_0 \in C$ está ausente no vértice $v_{i_0}$ e $c(\{ v_{i_0}, v_{i_1}\})=0$, então $c'_0$ está ausente no vértice $v_{i_1}$, onde $c'_0$ denota o inverso aditivo de $c_0 \; (mod \; n)$. Observe inicialmente que para todo $i \in \{0,1,2, ...,n-1 \}$, a cor $i$ está ausente no vértice $v_i$. De fato, $ \frac{(n+1)}{2}(i+i) \equiv \frac{(n+1)}{2}(i+j) \; (mod \; n)$, se, e somente se, $i \equiv j \; (mod \; n)$, e como $i,j \in \{ 0,1, \cdots, n-1 \}$, então $i=j$, mas $G$ não possui laços, por outro lado $\frac{(n+1)}{2}(i+j)=0 \; (mod \; n)$ se, e somente se, $(i+j)=0 \;(mod \; n)$, isto é, $j=i' (mod \; n)$, de onde segue imediatamente a propriedade. Para cada $i \in \{0, 1,2, \cdots n-1 \}$, denotamos por $e_i$ a aresta $\{v_i, v_{i'} \}$. Agora para cada par de cores $\{i, i' \}$ $i \in \{1,2, \cdots,\frac{n-1}{2} \}$, o subgrafo gerado pelo conjunto de arestas $\{ e \in E: c(e)=i \; ou \; c(e)=i' \} \cup \{e_i \}$ é um grafo regular de grau $2$ cujo conjunto de vértices é $V$, logo $G$ foi decomposto em $\frac{n-1}{2}$ grafos $2$-regulares e podemos utilizar o mesmo raciocínio do teorema \ref{teo1}, usando as rotações $r_2, r_3, ..., r_{\frac{n+3}{2}}$ e suas inversas definidas em $I_{n+2}$ nos respectivos ciclos orientados. \end{proof} A figura \ref{teofin} mostra um $K_3$ sendo usado como $5$-suporte. Novamente foram omitidas as arestas não adjacentes a vértices rotulados com $0$. \begin{figure}[h!] %\includegraphics{fig2.eps} \centering \scalebox{0.8}{\includegraphics{Teofin.eps} } % \caption{$K_3$ usado como 5-suporte.} % \label{teofin} \end{figure} \newsec{Conclusões} \hspace{0.3cm}O produto funcional é uma generalização do produto cartesiano, e que apresenta algumas das propriedades deste, como a comutatividade e o fato de que o grau máximo do grafo produto seja a soma dos graus máximos dos grafos fatores. Por outro lado, o produto funcional mostrou-se eficiente para construir grafos que de alguma forma ``herdam'' boas propriedades dos fatores, como foi mostrado na seção anterior, e ainda oferece mais ``liberdade'' que o produto cartesiano usual na hora de definir as adjacências do grafo produto. Para o futuro, pretende-se estudar o comportamento de algumas invariantes de grafos, assim como condições mais fracas para garantir a conexidade do produto quando os fatores sejam conexos.\\ \begin{abstract} {\bf Abstract} The paper presents a generalization of the Cartesian product of graphs, called functional product. We prove some properties of the new product and show an application, that consist in generate regular graphs that admits $\Delta$-range coloring with $\Delta +1$ colors. \end{abstract} \begin{thebibliography}{8} %\bibitem{CHI} T.S. Chihara, ``An Introduction to Orthogonal Polynomials'', %Mathematics and its Applications Series, Gordon and Breach, New York, 1978. %\bibitem{CLBG} C.S.Q. Caldas, J. Limaco, R.K. Barreto, P. Gamboa, About the %Benjamin-Bona-Mahony equation in domains with moving boundary, %{\em TEMA - Tend. Mat. Apl. Comput.}, {\bf 8}, No. 3 (2007), 329--339. \bibitem{RBarbosa} R. M. Barbosa, M.R.C. Santana, Produtos de Grafos $Z_m$-bem-cobertos, {\em Tema}, {\bf 13} (2012) 75--83. \bibitem{Bo01} V. A. Bojarshinov, Edge and total coloring of interval graphs, {\em Disc. Appl. Math}. 114 (2001) 23--28. \bibitem{BONDY} J. Bondy, U. Murty, ``Graph Theory with Applications'', North-Holland, New York, 1976. \bibitem{CM07} C. N. Campos, C. P. Mello, A result on the total coloring of power of cycles, {\em Disc. Appl. Math}. 155 (2007) 585--597. \bibitem{LOZR} C. V. P. Friedmann, A. R. G. Lozano, L. Markenzon, C. F. E. M. Waga, Total coloring of Block-cactus graphs, {\em The journal of combinatorial mathematics and combinatorial computing}, {\bf 78} (2011) 273--283. \bibitem{IK08} W. Imrich, S. Klavzar, D. Rall, ``Topics in Graph Theory: Graphs and Their Cartesian Products'', A K Peters Ltd, (2008). \bibitem{KM03} A. Kemnitz, M. Marangio, Total colorings of cartesian products of graphs, Congres. Numer. 165 (2003), 99--109. \bibitem{LOZC} A. R. G. Lozano, C. V. P. Friedmann, A. S. Siqueira, Relação entre coloração de vértices com folga e coloração total equilibrada, {\em Almanaque Unigranrio de Pesquisa}, {\bf 1} (2011) 103--106. \bibitem{LOZC} A. R. G. Lozano, S. Jurkiewicz, C.V.P. Friedmann, Coloração total equilibrada de grafos, um modelo para redes de interconexão, {\em Pesquisa Operacional}, {\bf 28} (2008) 161--171. \bibitem{LOZAA} A. R. G. Lozano, ``Coloração Total Equilibrada de Grafos'', Tese de Doutorado, COPPE, UFRJ, Rio de Janeiro, RJ, 2005. \bibitem{PZ09} K. Prnaver, B. Zmazek, On the total chormatic number of direct products graphs, {\em J. Appl. Math Comput}. (2009). \bibitem{SABI} G. Sabidussi, Graph multiplication,{\em Math. Z.},{\bf 72}, (1960) 446--457. \bibitem{LOZA} A. S. Siqueira. ``Coloração total equilibrada em subfamílias de grafos regulares'', Tese de Doutorado, COPPE, UFRJ, Rio de Janeiro, RJ, 2011. \bibitem{TCW09} X. Tan, H. Chen, J. Wu, Total coloring of planar graphs without adjacent 4-cycles. {\em The Eighth International Symposium on Operational Research and its Applications}, China (2009) 20--22 \bibitem{VIZI} V.G. Vizing, The Cartesian product of graphs,{\em Vyc. Sis.},{\bf 9}, (1963) 30--43. \bibitem{YAP} H. Yap, ``Total colorings of graphs'', Springer, Berlin, 1996. \end{thebibliography} \end{document} \newpage $ \ \ $ \thispagestyle{myheadings} \markboth{ }{ }