No label defined (Q3971997)

[For the entire collection see Zbl 0698.00017.] Three lemmas in a paper of Bauer, Morgana, Schmeichel and Veldman (announced to appear in Discrete Math.) are applied to graphs \(G\) with suitable properties (\(G\) is 2-connected; 1-tough; fulfils some degree- sum-condition; every longest cycle in \(G\) is dominating; etc.) in order to find good lower bounds for the length \(c(G)\) of a longest cycle in \(G\) or to prove that \(G\) is Hamiltonian. Let \(\alpha(G)\) denote the independence number of \(G\), \(d(x)\) and \(N(x)\) the degree and the neighbourhood of the vertex \(x\in V(G)\), respectively, \(\sigma_ 3(G)\), \((NC_ 3(G)\), \(\bar\sigma_ 3(G)\), resp.) the minimum of \(d(u)+d(v)+d(w)\) (of \(| N(u)\cup N(v)\cup N(w)|\), of \(d(u)+d(v)+d(w)-| N(u)\cap N(v)\cap N(w)|\), resp.) for independent vertices \(u,v,w\in V(G)\) if \(3\leq\alpha(G)\), and \(\sigma_ 3(G)=3(n-\alpha(G))\) \((NC_ 3(G)=n-\alpha(G)\), \(\bar\sigma_ 3(G)=2(n- \alpha(G))\), resp.) if \(\alpha(G)<3\), where \(n=| V(G)|\). Then two of the three lemmas read as follows: If \(G\) is 2-connected (resp., 1- tough) with \(\sigma_ 3(G)\geq n+2\) (resp., \(\sigma_ 3(G)\geq n)\) then every longest cycle of \(G\) is a dominating cycle; moreover, if \(G\) is non-Hamiltonian, \(G\) contains a longest cycle \(C\) such that \(\max\{d(x)\mid x\in V(G)-V(C)\}\geq(1/3)\sigma_ 3(G)\). - In particular, the lemmas are used to give a new proof of a result of Flandrin, Jung and Li (announced to appear in Discrete Math.): If \(G\) is 2-connected with \(\bar\sigma_ 3(G)\geq n\) then \(G\) is Hamiltonian. Furthermore, the authors show that many previous results in Hamiltonian graph theory can be obtained (and partly generalized) by using the three lemmas; thus these lemmas unify this complex of results. - As examples for some new results the authors have got by means of the lemmas we mention: If \(G\) is 2-connected (resp., 1-tough) with \(\sigma_ 3(G)\geq n+2\) (resp. \(\sigma_ 3(G)\geq n\geq 3)\), then \(c(G)\geq min(n,n+NC_ 3(G)-\alpha(G))\). If \(G\) is 2-connected and contains a dominating cycle, then \(c(G)\geq min(n,2NC_ 2(G))\) unless \(G\) is the Petersen graph. (Here, \(NC_ 2(G)\) is defined analogously as \(NC_ 3(G)\).).