A graph is hamiltinian if it has a cycle containing all its vertices. Hamiltonian problem is one of the core problems in graph theory. The degree of a vertex is the number of its neighbors. Dirac showed in 1952 that every graph of order n is hamiltonian if any vertex is of degree at least n/2. This result has played an important role in extremal hamiltonian graph theory. For a vertex w, we define implicit-degrees of the vertex w by using the degree sequence of all vertices that has distance one or two from w. We obtained several results by replacing the degree conditions into implicit-degree conditions, that generalize many classic results in this area.
On this proposal for a PhD dissertation, we study the structure of neighborhoods of vertices and define new implicit-degrees that may give sufficient conditions for various hamiltonian problems, for example, pancyclic, dominating cycles, circumference, etc.
Ref.
1. Y. Zhu, H. Li and X. Deng, Implicit-degrees and circumferences,
Context
Objectives
Work program
Extra information
Prerequisite
Détails
Expected funding
Institutional funding
Status of funding
Expected
Candidates
graph theory, combinatorics
Utilisateur
Hao.Li
Créé
Mardi 15 janvier 2013 17:50:26 CET
dernière modif.
Mardi 15 janvier 2013 17:50:26 CET
Fichiers joints
filename
créé
hits
filesize
Aucun fichier joint à cette fiche
Connexion
Ecole Doctorale Informatique Paris-Sud
Directrice
Nicole Bidoit Assistante
Stéphanie Druetta Conseiller aux thèses
Dominique Gouyou-Beauchamps
ED 427 - Université Paris-Sud
UFR Sciences Orsay
Bat 650 - aile nord - 417
Tel : 01 69 15 63 19
Fax : 01 69 15 63 87
courriel: ed-info à lri.fr