A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

On a Relation between -Centroid and -Blocks in a Graph Sobre uma relação entre -Centróide e -Blocos em um gráfico

Masashi TAKEUCHI, Shoji SOEJIMA

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

O problema de encontrar a localização do centro e o problema de encontrar a mediana em um gráfico são importantes e básicos entre muitos problemas de localização de rede. Em conexão com estes dois problemas, os dois teoremas seguintes são bem conhecidos. Uma delas foi provada por Jordan e Sylvester e mostra que o centro de cada árvore consiste em um vértice ou em dois vértices adjacentes. A outra é provada por Jordan e mostra que o centróide (mediana) de cada árvore consiste em um vértice ou em dois vértices adjacentes. Esses teoremas foram generalizados por muitos pesquisadores até agora. Harary e Norman provaram que o centro de todo gráfico conectado G está em um único bloco de G. Truszczynski provou que a mediana de cada gráfico conectado G está em um único bloco de G. Slater definido k-centrum, que pode expressar tanto o centro quanto a mediana, e provou que o k-centrum de cada árvore consiste em um vértice ou dois vértices adjacentes. Este artigo discute a generalização desses teoremas. Nós definimos o -blocos de um gráfico G como uma generalização dos blocos de G, Onde é um subconjunto do conjunto de vértices de G; e definir o -centróide de G como uma generalização do centróide de G. Primeiro, provamos que -centróide de G está incluído em um -bloco de G. Esta é uma generalização dos teoremas acima relativos ao centróide, de Jordan e Truszczynski. Em segundo lugar, definimos o -centro de G como uma generalização do k-centro de G e provar alguns teoremas relativos à localização de -centro. Usando um dos teoremas aqui provados, podemos facilmente obter o teorema que mostra que k-centro de cada gráfico conectado G está em um único bloco de G. Este teorema é uma generalização do teorema acima de Slater.

Publicação
IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.10 pp.2009-2014
Data de publicação
2000/10/25
Publicitada
ISSN online
DOI
Tipo de Manuscrito
PAPER
Categoria
Gráficos e Redes

autores

Palavra-chave