Independent Spanning Trees of Product Graphs and Their Construction

Koji OBOKATA; Yukihiro IWASAKI; Feng BAO; Yoshihide IGARASHI

Independent Spanning Trees of Product Graphs and Their Construction

Koji OBOKATA, Yukihiro IWASAKI, Feng BAO, Yoshihide IGARASHI

Full Text Views

0

Cite this

Summary :

A graph G is called an n-channel graph at vertex r if there are n independent spanning trees rooted at r. A graph G is called an n-channel graph if G is an n-channel graph at every vertex. Independent spanning trees of a graph play an important role in fault-tolerant broadcasting in the graph. In this paper we show that if G₁ is an n₁-channel graph and G₂ is an n₂-channel graph, then G₁G₂ is an (n₁ + n₂)-channel graph. We prove this fact by a construction of n₁+n₂ independent spanning trees of G₁G₂ from n₁ independent spanning trees of G₁ and n₂ independent spanning trees of G₂. As an application we describe a fault-tolerant broadcasting scheme along independent spanning trees.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E79-A No.11 pp.1894-1903

Publication Date: 1996/11/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Graphs and Networks

Cite this

Copy

Koji OBOKATA, Yukihiro IWASAKI, Feng BAO, Yoshihide IGARASHI, "Independent Spanning Trees of Product Graphs and Their Construction" in IEICE TRANSACTIONS on Fundamentals, vol. E79-A, no. 11, pp. 1894-1903, November 1996, doi: .
Abstract: A graph G is called an n-channel graph at vertex r if there are n independent spanning trees rooted at r. A graph G is called an n-channel graph if G is an n-channel graph at every vertex. Independent spanning trees of a graph play an important role in fault-tolerant broadcasting in the graph. In this paper we show that if G₁ is an n₁-channel graph and G₂ is an n₂-channel graph, then G₁G₂ is an (n₁ + n₂)-channel graph. We prove this fact by a construction of n₁+n₂ independent spanning trees of G₁G₂ from n₁ independent spanning trees of G₁ and n₂ independent spanning trees of G₂. As an application we describe a fault-tolerant broadcasting scheme along independent spanning trees.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e79-a_11_1894/_p

Copy

@ARTICLE{e79-a_11_1894,
author={Koji OBOKATA, Yukihiro IWASAKI, Feng BAO, Yoshihide IGARASHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Independent Spanning Trees of Product Graphs and Their Construction},
year={1996},
volume={E79-A},
number={11},
pages={1894-1903},
abstract={A graph G is called an n-channel graph at vertex r if there are n independent spanning trees rooted at r. A graph G is called an n-channel graph if G is an n-channel graph at every vertex. Independent spanning trees of a graph play an important role in fault-tolerant broadcasting in the graph. In this paper we show that if G₁ is an n₁-channel graph and G₂ is an n₂-channel graph, then G₁G₂ is an (n₁ + n₂)-channel graph. We prove this fact by a construction of n₁+n₂ independent spanning trees of G₁G₂ from n₁ independent spanning trees of G₁ and n₂ independent spanning trees of G₂. As an application we describe a fault-tolerant broadcasting scheme along independent spanning trees.},
keywords={},
doi={},
ISSN={},
month={November},}

Copy

TY - JOUR
TI - Independent Spanning Trees of Product Graphs and Their Construction
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1894
EP - 1903
AU - Koji OBOKATA
AU - Yukihiro IWASAKI
AU - Feng BAO
AU - Yoshihide IGARASHI
PY - 1996
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E79-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 1996
AB - A graph G is called an n-channel graph at vertex r if there are n independent spanning trees rooted at r. A graph G is called an n-channel graph if G is an n-channel graph at every vertex. Independent spanning trees of a graph play an important role in fault-tolerant broadcasting in the graph. In this paper we show that if G₁ is an n₁-channel graph and G₂ is an n₂-channel graph, then G₁G₂ is an (n₁ + n₂)-channel graph. We prove this fact by a construction of n₁+n₂ independent spanning trees of G₁G₂ from n₁ independent spanning trees of G₁ and n₂ independent spanning trees of G₂. As an application we describe a fault-tolerant broadcasting scheme along independent spanning trees.
ER -