Implicit-degrees and circumferences
type: Item
instance of: scholarly article
title: Implicit-degrees and circumferences
zbMATH Open document ID: 0701.05030
DOI: 10.1007/BF01788680
author: Hao Li
author: Xiaotie Deng
author: Yongjin Zhu
published in: Graphs and Combinatorics
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 4148124
zbMATH Keywords: implicit-degrees
reviewed by: Norman F. Quimpo
MaRDI profile type: Publication
cites work: Q3852212
cites work: Hamilton Circuits and Long Circuits
cites work: A method in graph theory
cites work: Q3097395
Recommended article: Implicitization of nested circular curves
Recommended article: Q5203722
Recommended article: Approximation by circles
Recommended article: Q4500709
Recommended article: Radius, girth and minimum degree
Recommended article: Circle incidence theorems
Recommended article: Q4600923
Recommended article: Arithmetization of a Circular Arc
Recommended article: Problem of linear conjugation of a circumference
description: scientific article; zbMATH DE number 4148124