The square of a tree
The square of a tree
复制标题
一棵树的正方形
DOI：
10.1002/j.1538-7305.1960.tb03936.x
复制
发表时间：
1960
影响因子：
--
通讯作者：
F. Harary
中科院分区：
文献类型：
--
作者：
I. Ross;F. Harary
n点图的邻接矩阵是n阶方阵，其中i，j元素为1当且仅当第i点和第j点相邻，或i = j;否则为0。设A是图G的邻接矩阵，G是一个布尔矩阵，使得1 + 1 = 1。则G2，G的平方，是邻接矩阵为A2的图。我们得到了一个必要和充分条件的图是一棵树的平方，通过提供一个算法来确定一棵树，是平方根的任何图已知是一些树的平方。当一个图不是树的平方时，这个算法不能执行。证明了如果一个图是树的平方，则它有唯一的树平方根。该方法利用一个先前的结果来确定一个给定的图中的所有团，其中团是一个最大的完全子图。这个结果是在尝试描述具有平方根或一般来说具有n次方根的布尔矩阵的更一般问题时得到的。
The adjacency matrix of a graph of n points is the square matrix of order n, in which the i, j element is one if and only if the ith point and the jth point are adjacent, or i = j; and is zero otherwise. Let A be the adjacency matrix of graph G considered as a boolean matrix so that 1 + 1 = 1. Then G2, the square of G, is the graph whose adjacency matrix is A2. We obtain a necessary and sufficient condition for a graph to be the square of a tree by providing an algorithm for determining a tree that is the square root of any graph known to be the square of some tree. This algorithm cannot be carried through when a graph is not the square of a tree. It is shown that, if a graph is the square of a tree, then it has a unique tree square root. The method utilizes a previous result for determining all the cliques in a given graph, where a clique is a maximal complete subgraph. This result was obtained while attempting the more general problem of characterizing boolean matrices having a square root, or, in general, an nth root.