Coloração Total Absolutamente Equilibrada em uma Família Grafos Regulares

A. S. Siqueira, A. R. G. Lozano, S. R. P. Mattos, J. Negreiros

Abstract


Neste trabalho introduzimos os conceitos de coloração total absolutamente equilibrada e composição de grafos. Provamos que para n,k \in \mathbb{N}, se (k + 1)|n, existe um grafo k-regular conexo com n vértices que admite uma coloração total absolutamente equilibrada com no máximo \Delta +2 cores. Esse resultado mostra que existe uma relação entre a regularidade e o número de vértices do grafo que possibilita a construção de uma família de grafos regulares, denominados grafos harmônicos. Em seguida, mostramos que todo grafo harmônico de grau k pode ser obtido como composição sucessiva de grafos completos de grau k. Finalizamos, provando que os grafos harmônicos não possuem vértice de corte, fato que implica que todo grafo desta família possui conectividade de vértices \kappa(G) \geq 2.

Keywords


Coloração Total Absolutamente Equilibrada; Grafos Harmônicos; Composição de Grafos



DOI: https://doi.org/10.5540/tcam.2021.022.01.00031

Article Metrics

Metrics Loading ...

Metrics powered by PLOS ALM

Refbacks

  • There are currently no refbacks.



Trends in Computational and Applied Mathematics

A publication of the Brazilian Society of Applied and Computational Mathematics (SBMAC)

 

Indexed in:

                       

 

Desenvolvido por:

Logomarca da Lepidus Tecnologia