The toughness $t(G)$ of a connected graph $G$ is defined as $t(G)=\min\{\frac{|S|}{c(G-S)}\}$, in which the minimum is taken over all proper subsets $S\subset V(G)$ such that $c(G-S)>1$, where $c(G-S)$ denotes the number of components of $G-S$. Let $\lambda$ denote the second largest absolute eigenvalue of the adjacency matrix of a graph. For any connected $d$-regular graph $G$, it has been shown by Alon that $t(G)>\frac{1}{3}(\frac{d^2}{d\lambda+\lambda^2}-1)$, through which he was able to show that for every $t$ and $g$ there are $t$-tough graphs of girth strictly greater than $g$ and thus disproved in a strong sense a conjecture of Chvátal on pancyclicity. Brouwer independently discovered a better bound $t(G)>\frac{d}{\lambda}-2$ for any connected $d$-regular graph $G$, while he also conjectured that the lower bound can be improved to $t(G)\ge \frac{d}{\lambda} - 1$. We confirm this conjecture.

The 2-dimensional global rigidity has been shown to be equivalent to 3-connectedness and redundant rigidity by a combination of two results due to Jackson and Jordán, and Connelly, respectively. By the characterization, a theorem of Lovász and Yemini implies that every 6-connected graph is redundantly rigid and thus globally rigid. The 6-connectedness is best possible, since there exist infinitely many 5-connected nonrigid graphs. Jackson, Servatius, and Servatius used the idea of “essential connectivity” and proved that every 4-connected “essentially 6-connected” graph is redundantly rigid and thus global rigid. Since 3-connectedness is a necessary condition of global rigidity, it is interesting to study 3-connected graphs for redundant rigidity and thus global rigidity. We utilize a different “essential connectivity” and prove that every 3-connected essentially 9-connected graph is redundantly rigid and thus globally rigid. The essential 9-connectedness is best possible. Under this essential connectivity, we also prove that every 4-connected essentially 6-connected graph is redundantly rigid and thus globally rigid. Our proofs are based on discharging arguments.

Abstract This paper is concerned with the design and analysis of improved algorithms for determining the optimal length resolution refutation (OLRR) of a system of difference constraints over an integral domain. The problem of finding short explanations for unsatisfiable Difference Constraint Systems (DCS) finds applications in a number of design domains including program verification, proof theory, real-time scheduling, and operations research. These explanations have also been called “certificates” and “refutations” in the literature. This problem was first studied in Subramani (J Autom Reason 43(2):121–137, 2009 ), wherein the first polynomial time algorithm was proposed. In this paper, we propose two new strongly polynomial algorithms which improve on the existing time bound. Our first algorithm, which we call the edge progression approach, runs in O ( n 2 · k + m · n · k ) time, while our second algorithm, which we call the edge relaxation approach, runs in O ( m · n · k ) time, where m is the number of constraints in the DCS, n is the number of program variables, and k denotes the length of the shortest refutation. We conducted an extensive empirical analysis of the three OLRR algorithms discussed in this paper. Our experiments indicate that in the case of sparse graphs, the new algorithms discussed in this paper are superior to the algorithm in Subramani (J Autom Reason 43(2):121–137, 2009 ). Likewise, in the case of dense graphs, the approach in Subramani (J Autom Reason 43(2):121–137, 2009 ) is superior to the algorithms described in this paper. One surprising observation is the superiority of the edge relaxation algorithm over the edge progression algorithm in all cases, although both algorithms have the same asymptotic time complexity.