Estudo do número de Ramsey R(3,10): análise de grafos de ordem 40
O número de Ramsey R(k,l) é o menor número inteiro n tal que não exista (k,l,n,e)-grafo, sendo que um (k,l,n,e)-grafo denota um grafo G com n vértices e e arestas e com C(G)<k e I(G)<l, onde C(G) denota o maior clique em G e I(G) denota o maior conjunto independente em G. A teoria de grafos d...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Instituto Federal de Educação, Ciência e Tecnologia do Rio Grande do Sul (IFRS)
2023-11-01
|
| Series: | REMAT |
| Subjects: | |
| Online Access: | https://periodicos.ifrs.edu.br/index.php/REMAT/article/view/6424 |
| _version_ | 1797342266420887552 |
|---|---|
| author | Daniel Coswig Zitzke Danielle Santos Azevedo Jonas Francisco de Medeiros Lenon Saturnino Bernardino |
| author_facet | Daniel Coswig Zitzke Danielle Santos Azevedo Jonas Francisco de Medeiros Lenon Saturnino Bernardino |
| author_sort | Daniel Coswig Zitzke |
| collection | DOAJ |
| description |
O número de Ramsey R(k,l) é o menor número inteiro n tal que não exista (k,l,n,e)-grafo, sendo que um (k,l,n,e)-grafo denota um grafo G com n vértices e e arestas e com C(G)<k e I(G)<l, onde C(G) denota o maior clique em G e I(G) denota o maior conjunto independente em G. A teoria de grafos deu origem a vastas pesquisas, pois por mais simples que seja a definição, calcular os números de Ramsey é uma tarefa árdua e poucos são conhecidos. Exoo (1989), Goedgebeur e Radziszowski (2013) mostraram que 40<= R(3,10)<= 42. Assim, neste artigo, vamos expor proposições que serão úteis no cálculo deste número de Ramsey. Baseado nas ideias de Grinstead e Roberts (1982) e Cariolaro (2007), serão exibidas propriedades e características para um grafo bicolorido de ordem 40, tal que G seja livre de triângulos, isto é, C(G)<3, e não possua conjunto independente de ordem 10, ou seja, I(G)<10. Mostraremos, por exemplo, que dado G = (V,E) um grafo de ordem 40, tal que C(G) < 3 e I(G) < 10, então, para todo vértice v em V, tem-se que 4 <= deg(v) <= 9. Por fim, ressaltamos que os resultados inéditos obtidos pelos autores, em um projeto de pesquisa desenvolvido no IFRS, Campus Alvorada, encontram-se na Seção 4.
|
| first_indexed | 2024-03-08T10:30:49Z |
| format | Article |
| id | doaj.art-cfdaa8dbe33b4febb8e96ca5c2ed486e |
| institution | Directory Open Access Journal |
| issn | 2447-2689 |
| language | English |
| last_indexed | 2024-03-08T10:30:49Z |
| publishDate | 2023-11-01 |
| publisher | Instituto Federal de Educação, Ciência e Tecnologia do Rio Grande do Sul (IFRS) |
| record_format | Article |
| series | REMAT |
| spelling | doaj.art-cfdaa8dbe33b4febb8e96ca5c2ed486e2024-01-27T05:30:33ZengInstituto Federal de Educação, Ciência e Tecnologia do Rio Grande do Sul (IFRS)REMAT2447-26892023-11-0192Estudo do número de Ramsey R(3,10): análise de grafos de ordem 40Daniel Coswig Zitzke0Danielle Santos Azevedo1Jonas Francisco de Medeiros2Lenon Saturnino Bernardino3Instituto Federal de Educação, Ciência e Tecnologia do Rio Grande do Sul (IFRS), Campus Alvorada, Alvorada, RS, BrasilInstituto Federal de Educação, Ciência e Tecnologia do Rio Grande do Sul (IFRS), Campus Alvorada, Alvorada, RS, BrasilInstituto Federal de Educação, Ciência e Tecnologia do Rio Grande do Sul (IFRS), Campus Alvorada, Alvorada, RS, BrasilInstituto Federal de Educação, Ciência e Tecnologia do Rio Grande do Sul (IFRS), Campus Alvorada, Alvorada, RS, Brasil O número de Ramsey R(k,l) é o menor número inteiro n tal que não exista (k,l,n,e)-grafo, sendo que um (k,l,n,e)-grafo denota um grafo G com n vértices e e arestas e com C(G)<k e I(G)<l, onde C(G) denota o maior clique em G e I(G) denota o maior conjunto independente em G. A teoria de grafos deu origem a vastas pesquisas, pois por mais simples que seja a definição, calcular os números de Ramsey é uma tarefa árdua e poucos são conhecidos. Exoo (1989), Goedgebeur e Radziszowski (2013) mostraram que 40<= R(3,10)<= 42. Assim, neste artigo, vamos expor proposições que serão úteis no cálculo deste número de Ramsey. Baseado nas ideias de Grinstead e Roberts (1982) e Cariolaro (2007), serão exibidas propriedades e características para um grafo bicolorido de ordem 40, tal que G seja livre de triângulos, isto é, C(G)<3, e não possua conjunto independente de ordem 10, ou seja, I(G)<10. Mostraremos, por exemplo, que dado G = (V,E) um grafo de ordem 40, tal que C(G) < 3 e I(G) < 10, então, para todo vértice v em V, tem-se que 4 <= deg(v) <= 9. Por fim, ressaltamos que os resultados inéditos obtidos pelos autores, em um projeto de pesquisa desenvolvido no IFRS, Campus Alvorada, encontram-se na Seção 4. https://periodicos.ifrs.edu.br/index.php/REMAT/article/view/6424teoria de grafosgrafos bicoloridosnúmeros de Ramseycliqueconjunto independente |
| spellingShingle | Daniel Coswig Zitzke Danielle Santos Azevedo Jonas Francisco de Medeiros Lenon Saturnino Bernardino Estudo do número de Ramsey R(3,10): análise de grafos de ordem 40 REMAT teoria de grafos grafos bicoloridos números de Ramsey clique conjunto independente |
| title | Estudo do número de Ramsey R(3,10): análise de grafos de ordem 40 |
| title_full | Estudo do número de Ramsey R(3,10): análise de grafos de ordem 40 |
| title_fullStr | Estudo do número de Ramsey R(3,10): análise de grafos de ordem 40 |
| title_full_unstemmed | Estudo do número de Ramsey R(3,10): análise de grafos de ordem 40 |
| title_short | Estudo do número de Ramsey R(3,10): análise de grafos de ordem 40 |
| title_sort | estudo do numero de ramsey r 3 10 analise de grafos de ordem 40 |
| topic | teoria de grafos grafos bicoloridos números de Ramsey clique conjunto independente |
| url | https://periodicos.ifrs.edu.br/index.php/REMAT/article/view/6424 |
| work_keys_str_mv | AT danielcoswigzitzke estudodonumeroderamseyr310analisedegrafosdeordem40 AT daniellesantosazevedo estudodonumeroderamseyr310analisedegrafosdeordem40 AT jonasfranciscodemedeiros estudodonumeroderamseyr310analisedegrafosdeordem40 AT lenonsaturninobernardino estudodonumeroderamseyr310analisedegrafosdeordem40 |