Toughness and Vertex Degrees

Details Toughness and Vertex Degrees Toughness and Vertex Degrees

2009-12-15

arxiv.org/abs/0912.2919v2

Mathematics

Combinatorics

13 pages

Scientific paper

We study theorems giving sufficient conditions on the vertex degrees of a graph $G$ to guarantee $G$ is $t$-tough. We first give a best monotone theorem when $t\ge1$, but then show that for any integer $k\ge1$, a best monotone theorem for $t=\frac1k\le 1$ requires at least $f(k)\cdot|V(G)|$ nonredundant conditions, where $f(k)$ grows superpolynomially as $k\rightarrow\infty$. When $t<1$, we give an additional, simple theorem for $G$ to be $t$-tough, in terms of its vertex degrees.

Affiliated with

Also associated with

No associations

Rating

Toughness and Vertex Degrees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Toughness and Vertex Degrees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Toughness and Vertex Degrees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-305770