A comprehensive analysis of degree based condition for Hamiltonian cycles

Md Kamrul Hasan; Mohammad Kaykobad; Young Koo Lee; Sungyoung Lee

doi:10.1109/ICCITECHN.2008.4803067

A comprehensive analysis of degree based condition for Hamiltonian cycles

Md Kamrul Hasan
, Mohammad Kaykobad
, Young Koo Lee
, Sungyoung Lee

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

Rahman and Kaykobad introduced a shortest distance based condition for finding the existence of Hamiltonian paths in graphs as follows: Let G be a connected graph with n vertices, and if d(u) + d(v) + δ(u,v) ≥ n + 1, for each pair of distinct non-adjacent vertices uand v in G, where δ(u, v) is the length of a shortest path between u and v , then G has Hamiltonian path. Rao Li proved that under the same condition, the graph is Hamiltonian or belongs to two different classes of graphs. Recently, Mehedy, Hasan and Kaykobad showed case by casethat under the condition of Rahman and Kaykobad, the graph is Hamiltonian with exceptions for δ(u, v) =2. Shengjia Li et. al. mentions a graph to be Hamiltonian whenever d(u) + d(v) ≥ n - 1 , for all δ(u, v) =2 , otherwise n is odd and the graph falls into a special class. This paper relates the results of Mehedy, Hasan and Kaykobad with the two exceptional classes of graphs introduced by Rao Li and the graph class introduced by Shengjia Li et. al. The paper also provides a thorough analysis of the graph classes and shows the characteristics of a graph when it falls into one of those classes.

Original language	English
Title of host publication	Proceedings of 11th International Conference on Computer and Information Technology, ICCIT 2008
Publisher	IEEE Computer Society
Pages	464-469
Number of pages	6
ISBN (Print)	9781424421367
DOIs	https://doi.org/10.1109/ICCITECHN.2008.4803067
Publication status	Published - 2008
Event	11th International Conference on Computer and Information Technology, ICCIT 2008 - Khulna, Bangladesh Duration: 25 Dec 2008 → 27 Dec 2008

Publication series

Name	Proceedings of 11th International Conference on Computer and Information Technology, ICCIT 2008

Conference

Conference	11th International Conference on Computer and Information Technology, ICCIT 2008
Country/Territory	Bangladesh
City	Khulna
Period	25/12/08 → 27/12/08

Bibliographical note

Funding Information:
This research was supported by the MKE (Ministry of Knowledge Economy), Korea, under the ITRC (Information Technology Research Center) support program supervised by the IITA (Institute of Information Technology Advancement)" (IITA-2009-(C1090-0902-0002)) and was supported by the IT R&D program of MKE/KEIT, [10032105, Development of Realistic Multiverse Game Engine Technology].

Funding Information:
This work also was supported by the Brain Korea 21 projects and Korea Science & Engineering Foundation (KOSEF) grant funded by the Korea government (MOST) (No. 2008-1342).

Keywords

Graphs.
Hamiltonian cycle
Hamiltonian path

Access to Document

10.1109/ICCITECHN.2008.4803067

Cite this

Hasan, M. K., Kaykobad, M., Lee, Y. K., & Lee, S. (2008). A comprehensive analysis of degree based condition for Hamiltonian cycles. In Proceedings of 11th International Conference on Computer and Information Technology, ICCIT 2008 (pp. 464-469). Article 4803067 (Proceedings of 11th International Conference on Computer and Information Technology, ICCIT 2008). IEEE Computer Society. https://doi.org/10.1109/ICCITECHN.2008.4803067

Hasan, Md Kamrul ; Kaykobad, Mohammad ; Lee, Young Koo et al. / A comprehensive analysis of degree based condition for Hamiltonian cycles. Proceedings of 11th International Conference on Computer and Information Technology, ICCIT 2008. IEEE Computer Society, 2008. pp. 464-469 (Proceedings of 11th International Conference on Computer and Information Technology, ICCIT 2008).

@inproceedings{bad33119b0084a05b65f69abec6f24d7,

title = "A comprehensive analysis of degree based condition for Hamiltonian cycles",

abstract = "Rahman and Kaykobad introduced a shortest distance based condition for finding the existence of Hamiltonian paths in graphs as follows: Let G be a connected graph with n vertices, and if d(u) + d(v) + δ(u,v) ≥ n + 1, for each pair of distinct non-adjacent vertices uand v in G, where δ(u, v) is the length of a shortest path between u and v , then G has Hamiltonian path. Rao Li proved that under the same condition, the graph is Hamiltonian or belongs to two different classes of graphs. Recently, Mehedy, Hasan and Kaykobad showed case by casethat under the condition of Rahman and Kaykobad, the graph is Hamiltonian with exceptions for δ(u, v) =2. Shengjia Li et. al. mentions a graph to be Hamiltonian whenever d(u) + d(v) ≥ n - 1 , for all δ(u, v) =2 , otherwise n is odd and the graph falls into a special class. This paper relates the results of Mehedy, Hasan and Kaykobad with the two exceptional classes of graphs introduced by Rao Li and the graph class introduced by Shengjia Li et. al. The paper also provides a thorough analysis of the graph classes and shows the characteristics of a graph when it falls into one of those classes.",

keywords = "Graphs., Hamiltonian cycle, Hamiltonian path",

author = "Hasan, \{Md Kamrul\} and Mohammad Kaykobad and Lee, \{Young Koo\} and Sungyoung Lee",

note = "Funding Information: This research was supported by the MKE (Ministry of Knowledge Economy), Korea, under the ITRC (Information Technology Research Center) support program supervised by the IITA (Institute of Information Technology Advancement){"} (IITA-2009-(C1090-0902-0002)) and was supported by the IT R\&D program of MKE/KEIT, [10032105, Development of Realistic Multiverse Game Engine Technology]. Funding Information: This work also was supported by the Brain Korea 21 projects and Korea Science \& Engineering Foundation (KOSEF) grant funded by the Korea government (MOST) (No. 2008-1342).; 11th International Conference on Computer and Information Technology, ICCIT 2008 ; Conference date: 25-12-2008 Through 27-12-2008",

year = "2008",

doi = "10.1109/ICCITECHN.2008.4803067",

language = "English",

isbn = "9781424421367",

series = "Proceedings of 11th International Conference on Computer and Information Technology, ICCIT 2008",

publisher = "IEEE Computer Society",

pages = "464--469",

booktitle = "Proceedings of 11th International Conference on Computer and Information Technology, ICCIT 2008",

address = "United States",

}

Hasan, MK, Kaykobad, M, Lee, YK & Lee, S 2008, A comprehensive analysis of degree based condition for Hamiltonian cycles. in Proceedings of 11th International Conference on Computer and Information Technology, ICCIT 2008., 4803067, Proceedings of 11th International Conference on Computer and Information Technology, ICCIT 2008, IEEE Computer Society, pp. 464-469, 11th International Conference on Computer and Information Technology, ICCIT 2008, Khulna, Bangladesh, 25/12/08. https://doi.org/10.1109/ICCITECHN.2008.4803067

A comprehensive analysis of degree based condition for Hamiltonian cycles. / Hasan, Md Kamrul; Kaykobad, Mohammad; Lee, Young Koo et al.
Proceedings of 11th International Conference on Computer and Information Technology, ICCIT 2008. IEEE Computer Society, 2008. p. 464-469 4803067 (Proceedings of 11th International Conference on Computer and Information Technology, ICCIT 2008).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A comprehensive analysis of degree based condition for Hamiltonian cycles

AU - Hasan, Md Kamrul

AU - Kaykobad, Mohammad

AU - Lee, Young Koo

AU - Lee, Sungyoung

N1 - Funding Information: This research was supported by the MKE (Ministry of Knowledge Economy), Korea, under the ITRC (Information Technology Research Center) support program supervised by the IITA (Institute of Information Technology Advancement)" (IITA-2009-(C1090-0902-0002)) and was supported by the IT R&D program of MKE/KEIT, [10032105, Development of Realistic Multiverse Game Engine Technology]. Funding Information: This work also was supported by the Brain Korea 21 projects and Korea Science & Engineering Foundation (KOSEF) grant funded by the Korea government (MOST) (No. 2008-1342).

PY - 2008

Y1 - 2008

N2 - Rahman and Kaykobad introduced a shortest distance based condition for finding the existence of Hamiltonian paths in graphs as follows: Let G be a connected graph with n vertices, and if d(u) + d(v) + δ(u,v) ≥ n + 1, for each pair of distinct non-adjacent vertices uand v in G, where δ(u, v) is the length of a shortest path between u and v , then G has Hamiltonian path. Rao Li proved that under the same condition, the graph is Hamiltonian or belongs to two different classes of graphs. Recently, Mehedy, Hasan and Kaykobad showed case by casethat under the condition of Rahman and Kaykobad, the graph is Hamiltonian with exceptions for δ(u, v) =2. Shengjia Li et. al. mentions a graph to be Hamiltonian whenever d(u) + d(v) ≥ n - 1 , for all δ(u, v) =2 , otherwise n is odd and the graph falls into a special class. This paper relates the results of Mehedy, Hasan and Kaykobad with the two exceptional classes of graphs introduced by Rao Li and the graph class introduced by Shengjia Li et. al. The paper also provides a thorough analysis of the graph classes and shows the characteristics of a graph when it falls into one of those classes.

AB - Rahman and Kaykobad introduced a shortest distance based condition for finding the existence of Hamiltonian paths in graphs as follows: Let G be a connected graph with n vertices, and if d(u) + d(v) + δ(u,v) ≥ n + 1, for each pair of distinct non-adjacent vertices uand v in G, where δ(u, v) is the length of a shortest path between u and v , then G has Hamiltonian path. Rao Li proved that under the same condition, the graph is Hamiltonian or belongs to two different classes of graphs. Recently, Mehedy, Hasan and Kaykobad showed case by casethat under the condition of Rahman and Kaykobad, the graph is Hamiltonian with exceptions for δ(u, v) =2. Shengjia Li et. al. mentions a graph to be Hamiltonian whenever d(u) + d(v) ≥ n - 1 , for all δ(u, v) =2 , otherwise n is odd and the graph falls into a special class. This paper relates the results of Mehedy, Hasan and Kaykobad with the two exceptional classes of graphs introduced by Rao Li and the graph class introduced by Shengjia Li et. al. The paper also provides a thorough analysis of the graph classes and shows the characteristics of a graph when it falls into one of those classes.

KW - Graphs.

KW - Hamiltonian cycle

KW - Hamiltonian path

UR - https://www.scopus.com/pages/publications/66149177022

U2 - 10.1109/ICCITECHN.2008.4803067

DO - 10.1109/ICCITECHN.2008.4803067

M3 - Conference contribution

AN - SCOPUS:66149177022

SN - 9781424421367

T3 - Proceedings of 11th International Conference on Computer and Information Technology, ICCIT 2008

SP - 464

EP - 469

BT - Proceedings of 11th International Conference on Computer and Information Technology, ICCIT 2008

PB - IEEE Computer Society

T2 - 11th International Conference on Computer and Information Technology, ICCIT 2008

Y2 - 25 December 2008 through 27 December 2008

ER -

Hasan MK, Kaykobad M, Lee YK, Lee S. A comprehensive analysis of degree based condition for Hamiltonian cycles. In Proceedings of 11th International Conference on Computer and Information Technology, ICCIT 2008. IEEE Computer Society. 2008. p. 464-469. 4803067. (Proceedings of 11th International Conference on Computer and Information Technology, ICCIT 2008). doi: 10.1109/ICCITECHN.2008.4803067

A comprehensive analysis of degree based condition for Hamiltonian cycles

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this