|
|||||
|
|
Removable Edges and Chords of Longest Cycles in 3-Connected Graphs |
|
| Authors: | Jichang Wu Hajo Broersma Haiyan Kang |
| Affiliation: | 1. School of Mathematics, Shandong University, Shandong, 250100, Jinan, China 2. Faculty of EEMCS, University of Twente, P.O. Box 217, 7500 AE, Enschede, The Netherlands 3. College of Science China, University of Mining and Technology, Jiangsu, 221116, Xuzhou, China |
| Abstract: | We verify two special cases of Thomassen’s conjecture of 1976 stating that every longest cycle in a 3-connected graph contains a chord.We prove that Thomassen’s conjecture is true for two classes of 3-connected graphs that have a bounded number of removable edges on or off a longest cycle. Here an edge e of a 3-connected graph G is said to be removable if G – e is still 3-connected or a subdivision of a 3-connected (multi)graph.We give examples to showthat these classes are not covered by previous results. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |