The Property of Hamiltonian Connectedness in Toeplitz Graphs
A spanning path in a graph G is called a Hamiltonian path. To determine which graphs possess such paths is an NP-complete problem. A graph G is called Hamiltonian-connected if any two vertices of G are connected by a Hamiltonian path. We consider here the family of Toeplitz graphs. About them, it is...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2020-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2020/5608720 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850234156544425984 |
|---|---|
| author | Ayesha Shabbir Muhammad Faisal Nadeem Tudor Zamfirescu |
| author_facet | Ayesha Shabbir Muhammad Faisal Nadeem Tudor Zamfirescu |
| author_sort | Ayesha Shabbir |
| collection | DOAJ |
| description | A spanning path in a graph G is called a Hamiltonian path. To determine which graphs possess such paths is an NP-complete problem. A graph G is called Hamiltonian-connected if any two vertices of G are connected by a Hamiltonian path. We consider here the family of Toeplitz graphs. About them, it is known only for n=3 that Tnp,q is Hamiltonian-connected, while some particular cases of Tnp,q,r for p=1 and q=2,3,4 have also been investigated regarding Hamiltonian connectedness. Here, we prove that the nonbipartite Toeplitz graph Tn1,q,r is Hamiltonian-connected for all 1<q<r<n and n≥5r−2. |
| format | Article |
| id | doaj-art-15eb3dc48e054ee4ad6e1ec60c170238 |
| institution | OA Journals |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2020-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-15eb3dc48e054ee4ad6e1ec60c1702382025-08-20T02:02:43ZengWileyComplexity1076-27871099-05262020-01-01202010.1155/2020/56087205608720The Property of Hamiltonian Connectedness in Toeplitz GraphsAyesha Shabbir0Muhammad Faisal Nadeem1Tudor Zamfirescu2Preparatory Year Deanship, King Faisal University, 31982 Hofuf, Al Ahsa, Saudi ArabiaDepartment of Mathematics, COMSATS, University Islamabad Lahore Campus, PakistanFaculty of Mathematics, University of Dortmund, 44221 Dortmund, GermanyA spanning path in a graph G is called a Hamiltonian path. To determine which graphs possess such paths is an NP-complete problem. A graph G is called Hamiltonian-connected if any two vertices of G are connected by a Hamiltonian path. We consider here the family of Toeplitz graphs. About them, it is known only for n=3 that Tnp,q is Hamiltonian-connected, while some particular cases of Tnp,q,r for p=1 and q=2,3,4 have also been investigated regarding Hamiltonian connectedness. Here, we prove that the nonbipartite Toeplitz graph Tn1,q,r is Hamiltonian-connected for all 1<q<r<n and n≥5r−2.http://dx.doi.org/10.1155/2020/5608720 |
| spellingShingle | Ayesha Shabbir Muhammad Faisal Nadeem Tudor Zamfirescu The Property of Hamiltonian Connectedness in Toeplitz Graphs Complexity |
| title | The Property of Hamiltonian Connectedness in Toeplitz Graphs |
| title_full | The Property of Hamiltonian Connectedness in Toeplitz Graphs |
| title_fullStr | The Property of Hamiltonian Connectedness in Toeplitz Graphs |
| title_full_unstemmed | The Property of Hamiltonian Connectedness in Toeplitz Graphs |
| title_short | The Property of Hamiltonian Connectedness in Toeplitz Graphs |
| title_sort | property of hamiltonian connectedness in toeplitz graphs |
| url | http://dx.doi.org/10.1155/2020/5608720 |
| work_keys_str_mv | AT ayeshashabbir thepropertyofhamiltonianconnectednessintoeplitzgraphs AT muhammadfaisalnadeem thepropertyofhamiltonianconnectednessintoeplitzgraphs AT tudorzamfirescu thepropertyofhamiltonianconnectednessintoeplitzgraphs AT ayeshashabbir propertyofhamiltonianconnectednessintoeplitzgraphs AT muhammadfaisalnadeem propertyofhamiltonianconnectednessintoeplitzgraphs AT tudorzamfirescu propertyofhamiltonianconnectednessintoeplitzgraphs |