# Convex independence and the structure of clone-free multipartite tournaments

Darren B. Parker; Randy F. Westhoff; Marty J. Wolf

Discussiones Mathematicae Graph Theory (2009)

- Volume: 29, Issue: 1, page 51-69
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topDarren B. Parker, Randy F. Westhoff, and Marty J. Wolf. "Convex independence and the structure of clone-free multipartite tournaments." Discussiones Mathematicae Graph Theory 29.1 (2009): 51-69. <http://eudml.org/doc/270650>.

@article{DarrenB2009,

abstract = {We investigate the convex invariants associated with two-path convexity in clone-free multipartite tournaments. Specifically, we explore the relationship between the Helly number, Radon number and rank of such digraphs. The main result is a structural theorem that describes the arc relationships among certain vertices associated with vertices of a given convexly independent set. We use this to prove that the Helly number, Radon number, and rank coincide in any clone-free bipartite tournament. We then study the relationship between Helly independence and Radon independence in clone-free multipartite tournaments. We show that if the rank is at least 4 or the Helly number is at least 3, then the Helly number and the Radon number are equal.},

author = {Darren B. Parker, Randy F. Westhoff, Marty J. Wolf},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {convex sets; rank; Helly number; Radon number; multipartite tournaments},

language = {eng},

number = {1},

pages = {51-69},

title = {Convex independence and the structure of clone-free multipartite tournaments},

url = {http://eudml.org/doc/270650},

volume = {29},

year = {2009},

}

TY - JOUR

AU - Darren B. Parker

AU - Randy F. Westhoff

AU - Marty J. Wolf

TI - Convex independence and the structure of clone-free multipartite tournaments

JO - Discussiones Mathematicae Graph Theory

PY - 2009

VL - 29

IS - 1

SP - 51

EP - 69

AB - We investigate the convex invariants associated with two-path convexity in clone-free multipartite tournaments. Specifically, we explore the relationship between the Helly number, Radon number and rank of such digraphs. The main result is a structural theorem that describes the arc relationships among certain vertices associated with vertices of a given convexly independent set. We use this to prove that the Helly number, Radon number, and rank coincide in any clone-free bipartite tournament. We then study the relationship between Helly independence and Radon independence in clone-free multipartite tournaments. We show that if the rank is at least 4 or the Helly number is at least 3, then the Helly number and the Radon number are equal.

LA - eng

KW - convex sets; rank; Helly number; Radon number; multipartite tournaments

UR - http://eudml.org/doc/270650

ER -

## References

top- [1] M. Changat and J. Mathew, On triangle path convexity in graphs, Discrete Math. 206 (1999) 91-95, doi: 10.1016/S0012-365X(98)00394-X. Zbl0929.05046
- [2] G. Chartrand and J.F. Fink and P. Zhang, Convexity in oriented graphs, Discrete Applied Math. 116 (2002) 115-126, doi: 10.1016/S0166-218X(00)00382-6. Zbl1001.05050
- [3] G. Chartrand and P. Zhang, Convex sets in graphs, Cong. Numer. 136 (1999) 19-32. Zbl0967.05031
- [4] P. Duchet, Convexity in graphs II. Minimal path convexity, J. Combin. Theory (B) 44 (1988) 307-316, doi: 10.1016/0095-8956(88)90039-1. Zbl0672.52001
- [5] P. Erdös, E. Fried, A. Hajnal and E.C. Milner, Some remarks on simple tournaments, Algebra Universalis 2 (1972) 238-245, doi: 10.1007/BF02945032. Zbl0267.05104
- [6] M.G. Everett and S.B. Seidman, The hull number of a graph, Discrete Math. 57 (1985) 217-223, doi: 10.1016/0012-365X(85)90174-8. Zbl0584.05044
- [7] D.J. Haglin and M.J. Wolf, On convex subsets in tournaments, SIAM Journal on Discrete Mathematics 9 (1996) 63-70, doi: 10.1137/S0895480193251234. Zbl0858.05050
- [8] F. Harary and J. Nieminen, Convexity in graphs, J. Differential Geometry 16 (1981) 185-190. Zbl0493.05037
- [9] R.E. Jamison and R. Nowakowski, A Helly theorem for convexity in graphs, Discrete Math. 51 (1984) 35-39, doi: 10.1016/0012-365X(84)90021-9. Zbl0548.05052
- [10] J.W. Moon, Embedding tournaments in simple tournaments, Discrete Math. 2 (1972) 389-395, doi: 10.1016/0012-365X(72)90016-7. Zbl0236.05108
- [11] J. Nieminen, On path- and geodesic-convexity in digraphs, Glasnik Matematicki 16 (1981) 193-197. Zbl0487.05031
- [12] D.B. Parker, R.F. Westhoff and M.J. Wolf, On two-path convexity in multipartite tournaments, European J. Combin. 29 (2008) 641-651, doi: 10.1016/j.ejc.2007.03.009. Zbl1141.05039
- [13] D.B. Parker, R.F. Westhoff and M.J. Wolf, Two-path convexity in clone-free regular multipartite tournaments, Australas. J. Combin. 36 (2006) 177-196. Zbl1109.05047
- [14] A. Abueida, W.S. Diestelkamp, S.P. Edwards and D.B. Parker, Determining properties of a multipartite tournament from its lattice of convex subsets, Australas. J. Combin. 31 (2005) 217-230. Zbl1064.05066
- [15] D.B. Parker, R.F. Westhoff and M.J. Wolf, Two-path convexity and bipartite tournaments of small rank, to appear in Ars Combin. Zbl1249.05170
- [16] J.L. Pfaltz, Convexity in directed graphs, J. Combin. Theory 10 (1971) 143-152, doi: 10.1016/0095-8956(71)90074-8. Zbl0174.26803
- [17] N. Polat, A Helly theorem for geodesic convexity in strongly dismantlable graphs, Discrete Math. 140 (1995) 119-127, doi: 10.1016/0012-365X(93)E0178-7. Zbl0828.05062
- [18] J.C. Varlet, Convexity in Tournaments, Bull. Societe Royale des Sciences de Liege 45 (1976) 570-586. Zbl0351.05113
- [19] M.L.J van de Vel, Theory of Convex Structures (North Holland, Amsterdam, 1993). Zbl0785.52001

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.