2025/02/11 by Li, Chengli, Xu, Leyou
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2502.07534
B. Bollobás and G. Brightwell and independently R. Shi proved the existence of a cycle through all vertices whose degrees at least (n)/(2) in any 2-connected graph of order n. Motivated by this result, we prove the existence of a cycle through all vertices whose degrees at least n-ω in any 2-connected graph G of order n with clique number ω unless G is a specific graph. Moreover, we show that for any pair of vertices whose degrees are at least n-ω+1 in a graph G of order n with clique number ω, there exists a path joining them which contains all vertices of degree at least n-ω+1 unless G belongs to certain graph classes. In doing so, we prove the existence of a (u,v)-path through all vertices whose degrees at least (n+1)/(2) in any graph of order n, where u,v are two distinct vertices of degree at least (n+1)/(2).