Rooted level-disjoint partitions of Cartesian products

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F15%3A10317837" target="_blank" >RIV/00216208:11320/15:10317837 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.amc.2015.05.059" target="_blank" >http://dx.doi.org/10.1016/j.amc.2015.05.059</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.amc.2015.05.059" target="_blank" >10.1016/j.amc.2015.05.059</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Rooted level-disjoint partitions of Cartesian products

Popis výsledku v původním jazyce

In interconnection networks one often needs to broadcast multiple messages in parallel from a single source so that the load at each node is minimal. With this motivation we study a new concept of rooted level-disjoint partitions of graphs. In particular, we develop a general construction of level-disjoint partitions for Cartesian products of graphs that is efficient both in the number of level partitions as in the maximal height. As an example, we show that the hypercube Qn for every dimension n = 3 .2^i or n = 4 . 2^i where i }= 0 has n level-disjoint partitions with the same root and with maximal height 3n - 2. Both the number of such partitions and the maximal height are optimal. Moreover, we conjecture that this holds for any n }= 3.

Název v anglickém jazyce

Rooted level-disjoint partitions of Cartesian products

Popis výsledku anglicky

In interconnection networks one often needs to broadcast multiple messages in parallel from a single source so that the load at each node is minimal. With this motivation we study a new concept of rooted level-disjoint partitions of graphs. In particular, we develop a general construction of level-disjoint partitions for Cartesian products of graphs that is efficient both in the number of level partitions as in the maximal height. As an example, we show that the hypercube Qn for every dimension n = 3 .2^i or n = 4 . 2^i where i }= 0 has n level-disjoint partitions with the same root and with maximal height 3n - 2. Both the number of such partitions and the maximal height are optimal. Moreover, we conjecture that this holds for any n }= 3.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/GA14-10799S" target="_blank" >GA14-10799S: Hyperkrychlové, grafové a hypergrafové struktury</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2015

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Applied Mathematics and Computation

ISSN

0096-3003

e-ISSN

—

Svazek periodika

266

Číslo periodika v rámci svazku

8. června

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

15

Strana od-do

244-258

Kód UT WoS článku

000359300100020

EID výsledku v databázi Scopus

2-s2.0-84930666324