A Note on Contractible Edges in Chordal Graphs - Computer Science > Discrete MathematicsReport as inadecuate




A Note on Contractible Edges in Chordal Graphs - Computer Science > Discrete Mathematics - Download this document for free, or read online. Document in PDF available to download.

Abstract: Contraction of an edge merges its end points into a new vertex which isadjacent to each neighbor of the end points of the edge. An edge in a$k$-connected graph is {\em contractible} if its contraction does not result ina graph of lower connectivity. We characterize contractible edges in chordalgraphs using properties of tree decompositions with respect to minimal vertexseparators.



Author: N.S.Narayanaswamy, N.Sadagopan, Apoorve Dubey

Source: https://arxiv.org/







Related documents