The square of a block graph. (English) Zbl 1214.05145
Summary: The square \(H^{2}\) 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.
MSC:
| 05C76 | Graph operations (line graphs, products, etc.) |
Keywords:
graph powers; squares of block graphs; tree squares; good characterizations; graph algorithmsReferences:
| [1] | Agnarsson, Geir; Greenlaw, Raymond; Halldórsson, Magnús M., On powers of chordal graphs and their colorings, Congressus Numer., 144, 41-65 (2000) · Zbl 0976.05027 |
| [2] | Brandstädt, Andreas; Le, Van Bang, Simplicial powers of graphs, (Proceedings of the 2nd Annual International Conference on Combinatorial Optimization and Applications, COCOA’08. Proceedings of the 2nd Annual International Conference on Combinatorial Optimization and Applications, COCOA’08, Lecture Notes in Comput. Science, vol. 5165 (2008)), 160-170 · Zbl 1168.05341 |
| [3] | Brandstädt, Andreas; Le, Van Bang; Sritharan, R., Structure and linear time recognition of 4-leaf powers, ACM Trans. Algorithms, 5 (2008), Article No. 11 · Zbl 1451.05040 |
| [4] | Sunil Chandran, L.; Grandoni, Fabrizo, A linear time algorithm to list the minimal separators of chordal graphs, Discrete Math., 306, 351-358 (2006) · Zbl 1085.05058 |
| [5] | Chang, Maw-Shang; Ko, Ming-Tat; Lu, Hsueh-I, Linear time algorithms for tree root problems, (Proceedings of the 10th Scandinavian Workshop on Algorithm Theory, SWAT 2006. Proceedings of the 10th Scandinavian Workshop on Algorithm Theory, SWAT 2006, Lecture Notes in Comput. Science, vol. 4059 (2006)), 411-422 · Zbl 1142.05365 |
| [6] | Chen, Mingjang; Chang, Gerard J.; West, Douglas B., Interval numbers of powers of block graphs, Discrete Math., 275, 87-96 (2004) · Zbl 1030.05082 |
| [7] | Dahlhaus, Elias; Duchet, Pierre, On strongly chordal graphs, Ars Combin., 24 B, 23-30 (1987) · Zbl 0659.05059 |
| [8] | Babak Farzad, Lap Chi Lau, Van Bang Le, Ngoc Tuy Nguyen, Computing graph roots without short cycles, in: Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, pp. 397-408; Babak Farzad, Lap Chi Lau, Van Bang Le, Ngoc Tuy Nguyen, Computing graph roots without short cycles, in: Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, pp. 397-408 · Zbl 1236.68085 |
| [9] | Golumbic, Martin C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054 |
| [10] | Harary, Frank, Graph Theory (1972), Addison-Wesley: Addison-Wesley Massachusetts · Zbl 0235.05105 |
| [11] | Kearney, Paul E.; Corneil, Derek G., Tree powers, J. Algorithms, 29, 111-131 (1998) · Zbl 0919.68055 |
| [12] | Sreenivasa Kummar, P.; Veni Madhawan, C. E., Minimal vertex separators of chordal graphs, Discrete Appl. Math., 89, 155-168 (1998) · Zbl 0921.68064 |
| [13] | Lau, Lap Chi, Bipartite roots of graphs, ACM Trans. Algorithms, 2, 178-208 (2006), (Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, pp. 952-961) · Zbl 1321.05209 |
| [14] | Lau, Lap Chi; Corneil, Derek G., Recognizing powers of proper interval, split and chordal graphs, SIAM J. Discrete Math., 18, 83-102 (2004) · Zbl 1071.05031 |
| [15] | Lin, Yaw-Ling; Skiena, Steven S., Algorithms for square roots of graphs, SIAM J. Discrete Math., 8, 99-118 (1995) · Zbl 0821.05052 |
| [16] | Anna Lubiw, \( \Gamma \); Anna Lubiw, \( \Gamma \) |
| [17] | Motwani, Rajeev; Sudan, Madhu, Computing roots of graphs is hard, Discrete Appl. Math., 54, 81-88 (1994) · Zbl 0812.68103 |
| [18] | Mukhopadhyay, A., The square root of a graph, J. Combin. Theory, 2, 290-295 (1967) · Zbl 0153.26001 |
| [19] | Raychaudhuri, A., On powers of strongly chordal and circular arc graphs, Ars Combin., 34, 147-160 (1992) · Zbl 0770.05066 |
| [20] | Ross, I. C.; Harary, Frank, The square of a tree, Bell System Tech. J., 39, 641-647 (1960) |
| [21] | Spinrad, Jeremy P., Efficient Graph Representations (2003), Fields Institute Monographs: Fields Institute Monographs Toronto · Zbl 1033.05001 |
| [22] | Tarjan, Robert E., Depth first search and linear time algorithms, SIAM J. Comput., 1, 146-160 (1972) · Zbl 0251.05107 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
