- 期刊
- OpenAccess
Steiner Distance in Join, Corona, Cluster, and Threshold Graphs
摘要
For a connected graph G and a subset S of its vertices, the Steiner tree problem consists of finding a minimum-size connected subgraph containing S. The Steiner distance of S is the size of a Steiner tree for S, and the Steiner k-diameter of G is the maximum value of the Steiner distance over all vertex subsets S of cardinality k. Calculation of Steiner trees and Steiner distance is known to be NP-hard in general, so applications may benefit from using graphs where the Steiner distance and structure of Steiner trees are known. In this paper, we investigate the Steiner distance and Steiner k-diameter of the join, corona, and cluster of connected graphs, as well as threshold graphs.
延伸閱讀
- Dai, S. J., & Zhang, R. H. (2012). The Merrifield-Simmons Index and Hosoya Index of C(n, k, λ) Graphs. Journal of Applied Mathematics, 2012(), 1429-1436-396. https://doi.org/10.1155/2012/520156
- Liu, X., Chen, H. K., Huang, B. Q., & Tao, Y. B. (2017). Optimal Sizing for Wind/PV/Battery System Using Fuzzy c-Means Clustering with Self-Adapted Cluster Number. International Journal of Rotating Machinery, 2017(), 1-9-026. https://doi.org/10.1155/2017/5142825
- Jian, T. F. (2014). Weight Choosability of theta Graphs [master's thesis, National Taiwan University]. Airiti Library. https://doi.org/10.6342/NTU.2014.03068
- NAJJAR, W., & SRIMANI, P. K. (1993). Conditional Disconnection Probability in Star Graphs. VLSI Design, 1993(), 61-70. https://doi.org/10.1155/1993/84924
- Niu, P. Y. (2014). Dimension Reduction for Tensor Structure Data [master's thesis, National Taiwan University]. Airiti Library. https://doi.org/10.6342/NTU.2014.02254