On the Structure of Contractible Vertex Pairs in Chordal Graphs |
| |
| Affiliation: | 1. Department of Computer Science and Engineering, Indian Institute of Technology, Chennai-600036, India;1. School of Mathematics, Statistics and Operations Research, Victoria University, Wellington, New Zealand;2. Department of Mathematics, Louisiana State University, Baton Rouge, LA, USA;1. Nihon Techno Structure Co., Ltd, Shinyokohama 2-7-17, Kita-ku, Yokohama, Kanagawa, Japan;2. The University of Electro-Communications, Chofugaoka 1-5-1, Chofu, Tokyo, Japan;1. Department of Mathematics, United States Naval Academy, United States;2. School of Mathematics and Statistics, Victoria University of Wellington, New Zealand;3. Mathematics Department, Louisiana State University, United States |
| |
| Abstract: | An edge/non-edge in a k-connected graph is contractible if its contraction does not result in a graph of lower connectivity. We focus our study on contractible edges and non-edges in chordal graphs. Firstly, we characterize contractible edges in chordal graphs using properties of tree decompositions with respect to minimal vertex separators. Secondly, we show that in every chordal graph each non-edge is contractible. We also characterize non-edges whose contraction leaves a k-connected chordal graph. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
