Generalizations of the classics to spanning connectedness
2021
Abstract Let G = ( V , E ) be a graph and u , v be two arbitrary vertices of V ( G ) . Then G is hamilton-connected if there exists a spanning path between u and v , and G is hamiltonian if there exist two internally disjoint pathes between u and v and the union of these two paths spans V ( G ) . More generally, G is said to be spanning k -connected if there exist k internally disjoint pathes between u and v and the union of these k pathes contains all vertices of G . In the paper, we first generalize a classic theorem of Vergnas on hamiltonian graphs to spanning k -connectedness. Furthermore, we determine extremal number of edges in a spanning k -connected graph by extending an old theorem due to Erdős. Finally, we partially establish spanning k -connected versions of famous Chvatal-Erdős theorem.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
17
References
0
Citations
NaN
KQI