https://scholars.lib.ntu.edu.tw/handle/123456789/630387
標題: | Proof of a Conjecture About Minimum Spanning Tree Cycle Intersection | 作者: | Chen, Min Jen KUN-MAO CHAO |
關鍵字: | Cycle | Graph | Spanning tree | 公開日期: | 15-十一月-2022 | 出版社: | ELSEVIER | 卷: | 321 | 起(迄)頁: | 19 - 23 | 來源出版物: | Discrete Applied Mathematics | 摘要: | Let G be a graph and T a spanning tree of G. For an edge e in G−T, there is a cycle in T∪{e}. We call those edges cycle-edges and those cycles tree-cycles. The intersection of two tree-cycles is the set of all edges in common. If the intersection of two distinct tree-cycles is not empty, we regard that as an intersection. The tree intersection number of T is the number of intersections among all tree-cycles of T. In this paper, we prove the conjecture, posed by Dubinsky et al. (2021), which states that if a graph admits a star spanning tree in which one vertex is adjacent to all other vertices, then the star spanning tree has the minimum tree intersection number. |
URI: | https://scholars.lib.ntu.edu.tw/handle/123456789/630387 https://www.scopus.com/inward/record.uri?eid=2-s2.0-85132911038&doi=10.1016%2fj.dam.2022.06.030&partnerID=40&md5=11b26475af05b2d40b42a11ec90cd974 |
ISSN: | 0166218X | DOI: | 10.1016/j.dam.2022.06.030 |
顯示於: | 生醫電子與資訊學研究所 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。