Senso de Direção Cordal em Sistemas Distribuídos

Senso de direção é uma propriedade de grafos rotulados na qual a rotulação das arestas segue um esquema global consistente. Esta propriedade é conhecida por reduzir consideravelmente a complexidade de diversos problemas distribuídos. Neste trabalho, estudamos uma instância particular de senso de direção denominada senso de direção cordal (SDC). Em especial, caracterizamos a classe de grafos cúbicos que admitem SDC minimal (com o menor número possível de rótulos). Generalizamos vários resultados para a classe dos grafos regulares. Demonstramos que a classe dos grafos regulares que admitem SDC minimal é equivalente à classe dos grafos circulantes, apresentando uma forma eficiente (polinomial) de reconhecimento desta classe quando o grau do grafo é fixo. Analisamos outra propriedade, denominada cobertura dupla por ciclos (CDC), e descrevemos um método construtivo para geração de grafos cúbicos que admitem 6-CDC (CDC onde todos os ciclos possuem comprimento 6). Relacionamos o SDC minimal com a 6-CDC em grafos cúbicos, e mostramos que existe apenas um grafo cúbico (K4) que admite SDC minimal e não admite 6-CDC.