Quantidade de orientações de grafos livres de circuitos direcionados cíclicos (2012)
- Authors:
- Autor USP: PARENTE, ROBERTO FREITAS - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Assunto: TEORIA DOS GRAFOS
- Agências de fomento:
- Language: Português
- Abstract: Seja H' uma orientação do grafo H. Alon e Yuster [The number of orientations having no fixed tounament, Combinatória, 26 (2006), no. 1, 1-6] propuseram o problema de determinar ou estimar D(n,m,H'), a quantidade máxima de orientações livres de H' de um grafo com n vértices e m arestas. Se substituirmos o máximo pelo 'máximo essencial', ou seja, consideramos o máximo sobre quase todos os grafos de n vértices e com m arestas, em oposição à todos deles, o problema é mais acessível. Mostramos que esse máximo essencial é 2^o(m) se H' é o circuito direcionado cíclico C'_l de tamanho l (l >= 3), se m >> n^{1+1/(l-1)}. Por outro lado, o mínimo essencial é 2^(1-o(1))m, se m << n^{1+1/(l-1)}. O método de prova nos dá resultado da mesma natureza para grafos orientados bipartidos H' que contém circuito direcionado cícliclo.
- Imprenta:
- Data da defesa: 13.12.2011
-
ABNT
PARENTE, Roberto Freitas. Quantidade de orientações de grafos livres de circuitos direcionados cíclicos. 2012. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2012. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-22032012-150640/. Acesso em: 13 fev. 2026. -
APA
Parente, R. F. (2012). Quantidade de orientações de grafos livres de circuitos direcionados cíclicos (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-22032012-150640/ -
NLM
Parente RF. Quantidade de orientações de grafos livres de circuitos direcionados cíclicos [Internet]. 2012 ;[citado 2026 fev. 13 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-22032012-150640/ -
Vancouver
Parente RF. Quantidade de orientações de grafos livres de circuitos direcionados cíclicos [Internet]. 2012 ;[citado 2026 fev. 13 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-22032012-150640/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
