The square of a block graph |
| |
Authors: | Van Bang Le Nguyen Ngoc Tuy |
| |
Institution: | a Universität Rostock, Institut für Informatik, D-18051 Rostock, Germany b Hong Duc University, Thanh Hoa, Viet Nam |
| |
Abstract: | The square H2 of a graph H is obtained from H by adding new edges between every two vertices having distance two in H. A block graph is one in which every block is a clique. For the first time, good characterizations and a linear time recognition of squares of block graphs are given in this paper. Our results generalize several previous known results on squares of trees. |
| |
Keywords: | Graph powers Squares of block graphs Tree squares Good characterizations Graph algorithms |
本文献已被 ScienceDirect 等数据库收录! |