期刊名称：IAENG International Journal of Computer Science
印刷版ISSN：1819-656X
电子版ISSN：1819-9224
出版年度：2019
卷号：46
期号：3
页码：439-444
出版社：IAENG - International Association of Engineers
摘要：An edge coloring graph G is rainbow connectedif every two vertices are connected by a rainbow path, i.e.,a path with all edges of different colors. An edge coloringunder which G is rainbow connected is a rainbow coloring.Rainbow connection number of G is the minimum numberof colors needed under a rainbow coloring. In this paper, wepropose a lower bound to the size of the rainbow connectionnumber of pyramid networks. We believe that our techniquesused for the lower bound is useful to prove lower bounds inthe class of pyramid-like networks. In this paper, we also givea linear-time algorithm for constructing a rainbow coloring onpyramid networks and thus get an upper bound to the rainbowconnection number of pyramid networks. The result shows thatalthough the ratio of the upper bound and the lower bound areassociated with a proportional increase in the dimension of thenetworks, the resulting ratios are still bounded.
