Girth (teoria dos gráficos) - Girth (graph theory)

Na teoria dos grafos , a circunferência de um gráfico não direcionado é o comprimento de um ciclo mais curto contido no gráfico. Se o gráfico não contém nenhum ciclo (ou seja, é uma floresta ), sua circunferência é definida como infinita . Por exemplo, um 4-ciclo (quadrado) tem circunferência 4. Uma grade tem circunferência 4 também, e uma malha triangular tem circunferência 3. Um gráfico com circunferência quatro ou mais é livre de triângulos .

Gaiolas

Um gráfico cúbico (todos os vértices têm grau três) de circunferência g que é o menor possível é conhecido como g - gaiola (ou como g - gaiola (3, g )). O gráfico de Petersen é a única gaiola de 5 (é o menor gráfico cúbico de circunferência 5), ​​o gráfico de Heawood é a única gaiola de 6, o gráfico de McGee é a única gaiola de 7 e a gaiola de Tutte de oito é a única 8- cela. Pode haver várias gaiolas para uma determinada circunferência. Por exemplo, existem três gaiolas não isomórficas de 10, cada uma com 70 vértices: a gaiola de 10 Balaban , o gráfico de Harries e o gráfico de Harries – Wong .

Cilha e coloração de gráfico

Para qualquer inteiros positivos g e χ , existe um gráfico com o perímetro de pelo menos g e número cromática pelo menos χ ; por exemplo, o gráfico de Grötzsch é livre de triângulos e tem número cromático 4, e a repetição da construção Mycielskiana usada para formar o gráfico de Grötzsch produz gráficos livres de triângulos de número cromático arbitrariamente grande. Paul Erdős foi o primeiro a provar o resultado geral, usando o método probabilístico . Mais precisamente, ele mostrou que um gráfico aleatório em n vértices, formado pela escolha independente de incluir cada aresta com probabilidade n (1 -  g ) / g , tem, com probabilidade tendendo para 1 conforme n vai para o infinito, no máximo n / 2 ciclos de comprimento g ou menos, mas não tem conjunto independente de tamanho n / 2 k . Portanto, remover um vértice de cada ciclo curto deixa um gráfico menor com circunferência maior que g , no qual cada classe de cor de uma coloração deve ser pequena e que, portanto, requer pelo menos k cores em qualquer coloração.

Gráficos explícitos, embora grandes, com circunferência alta e número cromático podem ser construídos como certos gráficos de Cayley de grupos lineares sobre campos finitos . Esses gráficos Ramanujan notáveis também têm um grande coeficiente de expansão .

Conceitos relacionados

A circunferência ímpar e a circunferência par de um gráfico são os comprimentos de um ciclo ímpar mais curto e de um ciclo par mais curto, respectivamente.

O a circunferência de um gráfico é a duração dociclomais longo(simples), em vez do mais curto.

Considerado o menor comprimento de um ciclo não trivial, o perímetro admite generalizações naturais como a 1-sístole ou sístoles superiores na geometria sistólica .

Girth é o conceito dual para conectividade de borda , no sentido de que a circunferência de um grafo planar é a conectividade de borda de seu grafo dual e vice-versa. Esses conceitos são unificados na teoria da matróide pela circunferência de uma matróide , o tamanho do menor conjunto dependente da matróide. Para uma matróide gráfica , a circunferência da matróide é igual à circunferência do gráfico subjacente, enquanto para uma matróide co-gráfica é igual à conectividade da borda.

Referências

  1. ^ R. Diestel, Graph Theory , p.8. 3ª Edição, Springer-Verlag, 2005
  2. ^ Weisstein, Eric W. , "Girth" , MathWorld
  3. ^ Brouwer, Andries E. , Cages. Suplemento eletrônico do livro Distance-Regular Graphs (Brouwer, Cohen e Neumaier 1989, Springer-Verlag).
  4. ^ Erdős, Paul (1959), "Graph teoria e probabilidade", Canadian Journal of Mathematics , 11 : 34-38, doi : 10.4153 / CJM-1959-003-9.
  5. ^ Davidoff, Giuliana ; Sarnak, Peter ; Valette, Alain (2003), Elementary number theory, group theory, and Ramanujan graphs , London Mathematical Society Student Texts, 55 , Cambridge University Press, Cambridge, doi : 10.1017 / CBO9780511615825 , ISBN 0-521-82426-5, MR  1989434
  6. ^ Cho, Jung Jin; Chen, Yong; Ding, Yu (2007), "On the (co) girth of a connected matroid", Discrete Applied Mathematics , 155 (18): 2456–2470, doi : 10.1016 / j.dam.2007.06.015 , MR  2365057.