Some results related to the tenacity and existence of k k -trees
The tenacity of a graph G G , T(G) T ( G ) , is defined by T ( G ) = min { | S | + ? ( G ? S ) ? ( G ? S ) } , where the minimum is taken over all vertex cutsets S S of V(G) V ( G ) , ?(G?S) ? ( G ? S ) be the number of components of G?S G ? S and ?(G?S) ? ( G ? S ) be the number of vertices in the largest component of the graph induced by G?S G ? S . A k k -tree of a connected graph G G is a spanning tree with maximum degree at most k k . In this paper we show that if T ( G ) ? ? ( G ? S ) ? ( G ? S ) + 1 k ? 2 , for any subset S S of V(G) V ( G ) , with k?3 k ? 3 , then G G has a k k -tree.
tenacity parameter k k -tree k k k k k