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

Abstract

top
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.

How to cite

top

Darren 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. [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. [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. [3] G. Chartrand and P. Zhang, Convex sets in graphs, Cong. Numer. 136 (1999) 19-32. Zbl0967.05031
  4. [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. [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. [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. [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. [8] F. Harary and J. Nieminen, Convexity in graphs, J. Differential Geometry 16 (1981) 185-190. Zbl0493.05037
  9. [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. [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. [11] J. Nieminen, On path- and geodesic-convexity in digraphs, Glasnik Matematicki 16 (1981) 193-197. Zbl0487.05031
  12. [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. [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. [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. [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. [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. [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. [18] J.C. Varlet, Convexity in Tournaments, Bull. Societe Royale des Sciences de Liege 45 (1976) 570-586. Zbl0351.05113
  19. [19] M.L.J van de Vel, Theory of Convex Structures (North Holland, Amsterdam, 1993). Zbl0785.52001

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.