کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420121 683896 2007 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Containment properties of product and power graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Containment properties of product and power graphs
چکیده انگلیسی

In this paper, we study containment properties of graphs in relation with the Cartesian product operation. These results can be used to derive embedding results for interconnection networks for parallel architectures.First, we show that the isomorphism of two Cartesian powers GrGr and HrHr implies the isomorphism of G and H  , while Gr⊆HrGr⊆Hr does not imply G⊆HG⊆H, even for the special cases when G and H are prime, and when they are connected and have the same number of nodes at the same time.Then, we find a simple sufficient condition under which the containment of products implies the containment of the factors: if ∏i=1nGi⊆∏j=1nHj, where all graphs GiGi are connected and no graph HjHj has 4-cycles, then each GiGi is a subgraph of a different graph HjHj. Hence, if G is connected and H   has no 4-cycles, then Gr⊆HrGr⊆Hr implies G⊆HG⊆H.Finally, we focus on the particular case of products of graphs with the linear array. We show that the fact that G×Ln⊆H×LnG×Ln⊆H×Ln does not imply that G⊆HG⊆H even in the case when G and H   are connected and have the same number of nodes. However, we find a sufficient condition under which G×Ln⊆H×LnG×Ln⊆H×Ln implies G⊆HG⊆H.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 155, Issue 3, 1 February 2007, Pages 300–311
نویسندگان
, , ,