On suficient conditions involving distances for hamiltonian properties in graphs
Let G be a 2-connected graph of order A set is essential if it is independent and contains two vertices at distance two apart. For = f1 2 3g we de…ne min max to be respectively the smallest, the second smallest and the largest value in f12 23 31g where = j() \ ( )j In this paper we show that the closure concept can be used to prove su¢cient conditions on hamiltonicity when distances are involved. As main results, we prove for instance that if either (i) each essential triple of satis…es the condition 2 () ¸ + or (ii) j() [ ()j + min f() ()g ¸ for all pairs of ( ) at distance two then its 0-dual closure is complete. By allowing classes of nonhamiltonian graphs we extend this result by one unit. A large number of new su¢cient conditions are derived. The proofs are short and all the results are sharp. Key words: Hamiltonian graph, closure, dual closure, neighborhood closure, essential sets.
|Date of creation:||Jun 2013|
|Date of revision:|
|Contact details of provider:|| Postal: |
Web page: http://www.ceregmia.eu/Email:
More information through EDIRC
When requesting a correction, please mention this item's handle: RePEc:crg:wpaper:dt2013-13. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Janis Hilaricus)
If references are entirely missing, you can add them using this form.