%% 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{      }{   }
