- R. C. Holt and E. M. Reingold, On the time required to detect cycles and connectivity in graphs. Math. Systems Theory 6 (1972) 103--106.Google ScholarCross Ref
Index Terms
- On the time required to recognize properties of graphs: a problem
Recommendations
Some properties of contraction-critical 5-connected graphs
Let k be a positive integer and let G be a k-connected graph. An edge of G is called k-contractible if its contraction still results in a k-connected graph. A non-complete k-connected graph G is called contraction-critical if G has no k-contractible ...
Properties of minimally t-tough graphs
A graph G is minimally t-tough if the toughness of G is t and the deletion of any edge from G decreases the toughness. Kriesell conjectured that for every minimally 1-tough graph the minimum degree (G)=2. We show that in every minimally 1-tough graph (G)...
Some structural properties of minimally contraction-critically 5-connected graphs
An edge of a k-connected graph is said to be k-removable (resp. k-contractible) if the removal (resp. the contraction ) of the edge results in a k-connected graph. A k-connected graph with neither k-removable edge nor k-contractible edge is said to be ...
Comments