scientific article; zbMATH DE number 15353
[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)\).).
- Hamiltonian properties of graphs with large neighborhood unions
- Long cycles, degree sums and neighborhood unions
- Long cycles in graphs containing a 2-factor with many odd components
- Degree sums, \(k\)-factors and Hamilton cycles in graphs
- A note on dominating cycles in 2-connected graphs
- Toughness in graphs -- a survey
- scientific article; zbMATH DE number 4208106 (Why is no real title available?)
- scientific article; zbMATH DE number 837058 (Why is no real title available?)
- \(k\)-factors and Hamilton cycles in graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3971997)
