pith. sign in

arxiv: 0912.2919 · v2 · pith:WWWYOQMZnew · submitted 2009-12-15 · 🧮 math.CO

Toughness and Vertex Degrees

classification 🧮 math.CO
keywords degreestheoremvertexbestconditionsgivemonotonetough
0
0 comments X
read the original abstract

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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.