Long Paths Through Specified Vertices In 3-Connected Graphs |
| |
Institution: | 1. Institute of Mathematics, Faculty of Science, Pavol Jozef Šafárik University, Jesenná 5, 040 01 Košice, Slovakia;2. Department of Algebra, Technical University Dresden, Mommsenstrasse 13, D-01062 Dresden, Germany |
| |
Abstract: | Let h ≥ 6 be an integer, let G be a 3-connected graph with ∣V(G)∣ ≥ h − 1, and let x and z be distinct vertices of G. We show that if for any nonadjacent distinct vertices u and v in V(G) − {x, z}, the sum of the degrees of u and v in G is greater than or equal to h, then for any subset Y of V(G) − {x, z} with ∣Y∣ ≤ 2, G contains a path which has x and z as its endvertices, passes through all vertices in Y, and has length at least h − 2. We also show a similar result for cycles in 2-connected graphs. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|