Toughness and Hamiltonicity for special graph classes
QI, H., BROERSMA, H., KABELA, A., VUMAR, E. Toughness and Hamiltonicity for special graph classes. Bordeaux, France, 2016.
|Anglický název:||Toughness and Hamiltonicity for special graph classes|
|Autoři:||Hao Qi , Hajo Broersma , Mgr. Adam Kabela , Elkin Vumar|
|Abstrakt EN:||The toughness of a (non-complete) graph G is the minimum value of t for which there is a vertex cut S whose removal yields |S|/t components. Determining the toughness is an NP-hard problem for general input graphs. The toughness conjecture of Chvátal, which states that there exists a constant t such that every graph on at least 3 vertices with toughness at least t is hamiltonian, is still open for general graphs. We extend some known toughness results for split graphs to the more general class of multisplit graphs, i.e. graphs whose vertex set can be partitioned into an independent set and a set that induces a complete k-partite subgraph. We prove that, for any ﬁxed k ≥ 2, determining the toughness of a k-multisplit graph is an NP-hard problem, and that 2-tough multisplit graphs are hamiltonian. We also extend recent results on the toughness and hamiltonicity of C5*-graphs to the more general class of Cp*-graphs.|