04095504

j

04095504 Tian, Yongcheng Zhao, Lianchang On the circumferences of 1-tough graphs. Kexue Tongbao, Foreign Lang. Ed. 33, No.7, 538-541 (1988). 1988 Science Press, Beijing EN circumference of a graph 1-tough graph A connected graph $G$ is 1-tough if the number of components of $G-S$ does not exceed $\vert S\vert$ for any subset $S$ of $V(G)$. The circumference of a graph $G$ is the length of a longest cycle of $G$. Theorem. If $G$ is a 1-tough graph with $p$ ($\ge 11$) vertices and $\lambda = \min \{d(u) + d(v) : u\in V(G), v\in V(G)$ and $uv\not\in E(G)\}$ then $$ c(G) \ge \cases p \qquad& \text{if }\lambda\ge p-4;\\ \lambda + 3 \qquad& \text{if }5 \le \lambda \le p-5 \text{ and }\lambda \text{ is odd }; \\ \lambda + 2 \qquad& \text{if }4 \le \lambda \le p-5 \text{ and }\lambda \text{ is even.} \endcases $$ The proof considers the vertices of attachment to a longest cycle $C$ of a vertex in a component of $G-C$. The theorem is best possible as there are examples presented where the lower bounds are reached. N.Quimpo