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

Ring Embedding in Faulty Star Graphs Incorporação de anel em gráficos estelares defeituosos

Jung-Hwan CHANG, Chan-Su SHIN, Kyung-Yong CHWA

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Neste artigo, consideramos o problema de incorporação de anel em gráficos estelares defeituosos. Nossa incorporação é baseada no esquema de transição de caminho e técnica de empréstimo de nó no anel de subestrelas quadridimensionais com falhas uniformemente distribuídas. Deixar Sn ser ngráfico estelar tridimensional tendo n! nós. Mostraremos que um anel de comprimento n! - 2f pode ser encontrada em Sn quando o número de nós defeituosos f é no máximo n-3. Na pior das hipóteses, a perda de 2f nós no tamanho de um anel livre de falhas é inevitável porque o gráfico estrela é bipartido. Além disso, este resultado é superior ao melhor resultado anterior que constrói o anel de comprimento n! - 4f sob a mesma condição de falha. Além disso, estendendo este resultado para o gráfico estrela com falhas de nó e de borda simultaneamente, podemos encontrar o anel de comprimento livre de falhas n! - 2 fn in Sn quando ele contém fn nós defeituosos e fe bordas defeituosas tais que fn + fe n-3.

Publicação
IEICE TRANSACTIONS on Fundamentals Vol.E82-A No.9 pp.1953-1964
Data de publicação
1999/09/25
Publicitada
ISSN online
DOI
Tipo de Manuscrito
PAPER
Categoria
Gráficos e Redes

autores

Palavra-chave