×

The \(H\)-force set of a hypertournament. (English) Zbl 1288.05118

Summary: Let \(G=(V,E)\) be a Hamiltonian undirected graph. A nonempty vertex set \(X\subseteq V(G)\) is called a Hamiltonian cycle enforcing set (in short, an \(H\)-force set) of \(G\) if every \(X\)-cycle of \(G\) (i.e., a cycle of \(G\) containing all vertices of \(X\)) is Hamiltonian. For the graph \(G\), \(h(G)\) is the smallest cardinality of an \(H\)-force set of \(G\) and call it the \(H\)-force number of \(G\). In this paper, the definitions of the \(H\)-force set and the \(H\)-force number are extended on hypertournaments by using cycles of hypertournaments instead of the cycles of undirected graphs and, the smallest possible \(H\)-force set of a \(k\)-hypertournament with \(n\geq k+3\) vertices is characterized and its \(H\)-force number is given unless it belongs to the exceptional classes of \(k\)-hypertournaments.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C45 Eulerian and Hamiltonian graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barbut, E.; Bialostocki, A., A generalisation of rotational tournaments, Discrete Math., 76, 81-87 (1989) · Zbl 0672.05034
[2] Barbut, E.; Bialostocki, A., On regular \(r\)-tournaments, Combinatorica, 34, 97-106 (1992) · Zbl 0772.05046
[3] Bialostocki, A., An application of the Ramsey theorem to ordered \(r\)-tournaments, Discrete Math., 61, 325-328 (1986) · Zbl 0595.05053
[4] Brcanov, D.; Petrovic, V.; Treml, M., Kings in hypertournaments, Graphs Combin., 29, 3, 349-357 (2013) · Zbl 1267.05130
[5] Fabrici, I.; Hexel, E.; Jendrol’, S., On vertices enforcing a hamiltonian cycle, Discuss. Math. Graph Theory, 33, 71-89 (2013) · Zbl 1293.05205
[6] Gutin, G.; Yeo, A., Hamiltonian paths and cycles in hypertournaments, J. Graph Theory, 25, 277-286 (1997) · Zbl 0879.05041
[7] Li, H.; Li, S.; Guo, Y.; Surmacs, M., On the vertex-pancyclicity of hypertournaments, Discrete Appl. Math., 161, 16-17, 2749-2752 (2013) · Zbl 1285.05079
[8] Marshall, S., On the existence of \(k\)-tournaments with given automorphism group, Discrete Math., 152, 259-268 (1996) · Zbl 0864.05043
[9] Petrovicl, V.; Thomassen, C., Edge-disjoint Hamiltonian cycles in hypertournaments, J. Graph Theory, 51, 49-52 (2006) · Zbl 1086.05046
[10] Reid, K. B., Tournaments: scores, kings, generalizations and special topics, Congressus Nummerantium., 115, 171-211 (1996) · Zbl 0899.05024
[11] Wang, C.; Zhou, G., Note on the degree sequences of \(k\)-hypertournaments, Discrete Math., 308, 2292-2296 (2008) · Zbl 1140.05044
[12] Yang, J., Vertex-pancyclicity of hypertournaments, J. Graph Theory, 63, 338-348 (2010) · Zbl 1248.05096
[13] Zhang, X.; Li, R.; Li, S., \(H\)-force sets of locally semicomplete digraphs, Discrete Appl. Math., 160, 2491-2496 (2012) · Zbl 1251.05068
[14] Zhou, G.; Yao, T.; Zhang, K., On score sequences of \(k\)-hypertournaments, European J. Combin., 21, 993-1000 (2000) · Zbl 0966.05037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.