Grafos Periplanares Maximais: Sequência de Graus Hamiltoniana e Maxregularidade
Autores
|
3894 |
Rosa Maria Nader Damião Rodrigues
|
1707,44,877,804
|
|
3895 |
1707,44,877,804
|
|
|
5856 |
1707,44,877,804
|
|
|
5857 |
1707,44,877,804
|
Informações:
Publicações do PESC
Título
Grafos Periplanares Maximais: Sequência de Graus Hamiltoniana e Maxregularidade
Linha de pesquisa
Otimização
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
25/11/1997
Resumo
Apresentamos, neste trabalho, um estudo do conceito de periplanaridade, definido por CHARTRAND e HARARY em 1967. Observando o processo de geração de grafos periplanares maximais (mops), constatamos o surgimento de algumas subfamílias especiais de mops, tais como os grafos coroa, leque, serpentina e grega, que possuem propriedades relevantes, definidas através da construção de suas seqüências de graus hamiltonianas. Generalizamos a obtenção de subcadeias proibidas as seqüências de graus harniltonianas de mops e determinamos outras condições necessárias para que esta seqüência possua um mop como sua realização. O conceito de (n, r)-maxregularidade é introduzido como extensão do conceito de regularidade usual para grafos e investigamos o efeito deste novo conceito na classe dos mops. Caracterizamos, então, os mops (n, r)-maxregulares para cada r, r > 2. Para tal, vértices equilibradores foram definidos. Finalmente, um estudo de valoração das arestas de um mop, segundo os graus de seus vértices extremos, é também realizado.
Abstract
We present, in this work, a study on the concept of outerplanarity, as defined by CHARTRAND and HARARY in 1967. By observing the process of generating maximal outerplanar graphs (mops), we noticed the appearance of some mop special subfamilies, such as the crown, fan, strearner and lace graphs, which have relevant characteristics, defined through the construction of their Hamiltonian degree sequences. We generalized the achievement of substring forbidden to the Hamiltonian degree sequences of mops and we determined other necessary conditions so that this sequence may have a mop as its realization. The concept (n,r)-maxregularity is introduced as extension of the concept of usual regularity for graphs and we investigated the effect of this new concept on the class of mops. Thus, we characterized the (&r)-maxregular mops for each r, r 2 2. For that, balancing vertices were defined. Finally, a study of the valuing of the edges of a mop, according to the degrees of their extreme vertices, is also carried out.
Arquivo