The hierarchical product of graphs
The hierarchical product of graphs
复制标题
DOI：
10.1016/j.dam.2008.04.018
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Lali Barrière;F. Comellas;C. Dalfó;M. A. Fiol
中科院分区：
文献类型：
--
作者：
Lali Barrière;F. Comellas;C. Dalfó;M. A. Fiol
介绍了一种新的图操作并研究了它的一些性质。我们将其称为层次积，因为结果图中的顶点具有很强的（连通性）层次结构。事实上，得到的图是相应因素的笛卡尔积的子图。笛卡尔积的一些众所周知的特性，例如减少的平均距离和直径、简单的路由算法和一些最优通信协议都被分层积继承。我们还研究两个或多个图的层次积的一些代数性质。特别是，二叉超树Tm（完整图在两个顶点上的多个副本的层次积）的谱得到了充分的表征；事实证明，这是一个有趣的图示例，其所有特征值都不同。最后，提出了层次积的一些自然概括。
A new operation on graphs is introduced and some of its properties are studied. We call it hierarchical product, because of the strong (connectedness) hierarchy of the vertices in the resulting graphs. In fact, the obtained graphs turn out to be subgraphs of the cartesian product of the corresponding factors. Some well-known properties of the cartesian product, such as reduced mean distance and diameter, simple routing algorithms and some optimal communication protocols are inherited by the hierarchical product. We also address the study of some algebraic properties of the hierarchical product of two or more graphs. In particular, the spectrum of the binary hypertree Tm(which is the hierarchical product of several copies of the complete graph on two vertices) is fully characterized; turning out to be an interesting example of graph with all its eigenvalues distinct. Finally, some natural generalizations of the hierarchic product are proposed.