On the structure of contractible vertex pairs in chordal graphs. (English) Zbl 1267.05220
Balakrishnan, R. (ed.) et al., International conference on graph theory and its applications. Papers from the conference, Coimbatore, India, December 11–13, 2008. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 33, 29-36 (2009).
Summary: 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.
For the entire collection see [Zbl 1239.05003].
For the entire collection see [Zbl 1239.05003].
MSC:
| 05C75 | Structural characterization of families of graphs |
References:
| [1] | West, D. B., Introduction to graph theory (2003), Prentice Hall of India |
| [2] | Golumbic, C., Algorithmic graph theory and perfect graphs (1980), Academic Press · Zbl 0541.05054 |
| [3] | Rose, D. J., Triangulated graphs and elimination process, Journal of Mathematical Analysis and Applications, 32, 597-609 (1970) · Zbl 0216.02602 |
| [4] | Kriesell, M., Contractible non-edges in triangle-free graphs, Graphs and Combinatorics, 15, 429-439 (1999) · Zbl 0939.05053 |
| [5] | Kriesell, M., A survey on contractible edges in graphs of a prescribed vertex connectivity, Graphs and Combinatorics, 18, 1-30 (2002) · Zbl 0997.05054 |
| [6] | Kriesell, M., Contractible non-edges in 3-connected graphs, Journal of Combinatorial Theory Series B, 74, 192-201 (1998) · Zbl 1027.05054 |
| [7] | Jani, M.; Rieper, R. G.; Zeleke, M., Enumeration of \(k\)-trees and applications, Annals of Combinatorics, 6, 375-382 (2002) · Zbl 1017.05010 |
| [8] | Saito, A.; Ando, K.; Enomoto, H., Contractible edges in 3-connected graphs, Journal of Combinatorial Theory-B, 42, 1 (1987) · Zbl 0611.05037 |
| [9] | Tutte, W. T., A theory of 3-connected graphs, Indag.Math, 23, 441-455 (1961) · Zbl 0101.40903 |
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.
