On the structure of contractible edges in \(k\)-connected partial \(k\)-trees

DOI10.1007/s00373-009-0851-yzbMath1189.05088OpenAlexW1974514462MaRDI QIDQ844219

N. Sadagopan, L. Sunil Chandran, N. S. Narayanaswamy

Publication date: 18 January 2010

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-009-0851-y

zbMATH Keywords

contraction\(k\)-treepartial \(k\)-treeConnectivitycontractible edge

Mathematics Subject Classification ID

Connectivity (05C40)

Related Items (1)

Connectivity of the graph induced by contractible edges of a \(k\)-tree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new probabilistic analysis of Karger's randomized algorithm for minimum cut problems
• Contractible edges in 3-connected graphs
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Distribution of contractible edges in k-connected graphs
• Contractible edges in longest cycles in non-Hamiltonian graphs
• A survey on contractible edges in graphs of a prescribed vertex connectivity
• Enumeration of \(K\)-trees and applications
• Vertices of degree 5 in a contraction critically 5-connected graph
• On simple characterizations of k-trees
• Maximum number of contractible edges on Hamiltonian cycles of a 3-connected graph
• A recursive characterization of the 4-connected graphs
• Triangulated graphs and the elimination process
• Longest cycles in 3-connected graphs contain three contractible edges
• Recursive Graphs, Recursive Labelings and Shortest Paths
• Nonseparating cycles inK-Connected graphs
• Uncontractable 4-connected graphs
• Covering contractible edges in 3‐connected graphs. I: Covers of size three are cutsets

This page was built for publication: On the structure of contractible edges in \(k\)-connected partial \(k\)-trees