Implicit-degrees and circumferences (Q913815): Difference between revisions

The paper introduces two types of ``implicit-degrees'' of a vertex in a graph. If u is a vertex of degree \(k+1\), the set of neighbors of u, \(N_ 1(u)\), and the vertices at a distance 2 from n, \(N_ 2(u)\), are considered. Suppose that the degree sequence of the vertices of \(N_ 1(u)\cup N_ 2(u)\) is \(d_ 1\leq d_ 2\leq...\leq d_ k\leq d_{k+1}\leq...\) Let \(M_ 2\) and \(m_ 2\) be the maximum and minimum degrees, respectively, of vertices in \(N_ 2(u)\). If \(N_ 2(u)\neq \emptyset,\) the implicit-degrees \(d_ 1(u)\) and \(d_ 2(u)\) are given by: \[ d_ 1(u)=\max \{d_{k+1},k+1\}\quad if\quad d_{k+1}\geq M_ 2,\quad d_ 1(u)=\max \{d_ k,k+1\}\quad otherwise \] \[ d_ 2(u)=\max \{m_ 2,k+1\}\quad if\quad m_ 2\quad \geq d_ k\quad d_ 2(u)=d_ 1(u)\quad otherwise \] If \(N_ 2(u)=\emptyset,d_ 1(u)\) and \(d_ 2(u)\) are set equal to d(u). Using the concept of \(d_ 1\), the following criterion for hamiltonicity is obtained for 2-connected graphs of order n: If a and b are two nonadjacent vertices such that \(d_ 1(a)+d_ 1(b)\geq n\), then G is hamiltonian if and only if \(G+ab\) is hamiltonian. On the other hand, \(d_ 2\) is utilized to obtain lower bounds for the circumference of a graph.