Přejít k obsahu


Toughness and Hamiltonicity for special graph classes

Citace:
QI, H., BROERSMA, H., KABELA, A., VUMAR, E. Toughness and Hamiltonicity for special graph classes. Bordeaux, France, 2016.
Druh: PŘEDNÁŠKA, POSTER
Jazyk publikace: eng
Anglický název: Toughness and Hamiltonicity for special graph classes
Rok vydání: 2016
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.
Klíčová slova

Zpět

Patička