On maximum tolerant Radon partitions for all-paths convexity in graphs

Articles in Press

Document Type : Original paper

Authors

1 Department of Mathematics, Government College for Women, Thiruvananthapuram-695014, India

2 Department of Futures Studies, University of Kerala, Thiruvananthapuram-695581, India

3 Department of Computer Applications, Cochin University of Science and Technology, Kochi-682022, India

Abstract

In a connected graph G, the all-paths transit function A(u,v), consists of the set of all vertices in the graph G which lies on some path connecting u and v.  Convexity obtained by the all-paths transit function is called all-paths convexity.  A Radon partition of a set P of vertices of a graph G is a partition of P into two disjoint non-empty subsets such that their convex hulls intersect.  A Radon partition (Pt,Qt) of P is called t-tolerant Radon partition, if for any set S⊆P with |S|≤t,  the intersection of the convex hulls  ⟨Pt∖S⟩∩⟨Qt∖S⟩≠∅.  This paper is devoted to t-tolerant Radon partitions for the all-paths convexity of connected simple undirected graphs.  It is proved that the minimum number of vertices needed for t-tolerant Radon partition is 2t+4. But, some selection of 2t+4 vertices of G has a (t+1)-tolerant Radon partition.  In this paper, we discuss the necessary and sufficient condition to the existence of (t+1)-tolerant Radon partition for 2t+4 vertices of G.  We also develop algorithms to construct the Radon partition, t-tolerant Radon partition, and (t+1)-tolerant Radon partition of a set of 2t+4 vertices, if it exists.

Keywords

Main Subjects

References

[1] K. Balakrishnan and M. Changat, Hull numbers of path convexities on graphs, no. 5, pp. 11–23, Ramanujan Mathematical Society, 2008.
[2] S. Bereg and M. Haghpanah, Algorithms for Radon partitions with tolerance, Discrete Appl. Math. 319 (2022), 207–215.
https://doi.org/10.1016/j.dam.2021.09.014
[3] F. Buckley and F. Harary, Distance in Graphs, Addison-Wesley Publishing Company, 1990.
[4] M. Changat, S. Klavzar, and H.M. Mulder, The all-paths transit function of a graph, Czechoslovak Math. J. 51 (2001), no. 2, 439–448.  https://doi.org/10.1023/A:1013715518448
[5] M. Changat and J. Mathew, On triangle path convexity in graphs, Discrete Math. 206 (1999), no. 1-3, 91–95. https://doi.org/10.1016/S0012-365X(98)00394-X
[6] M. Changat, H.M. Mulder, and G. Sierksma, Convexities related to path properties on graphs, Discrete Math. 290 (2005), no. 2-3, 117–131.  https://doi.org/10.1016/j.disc.2003.07.014
[7] G.N. Colin, Applying Tverberg Type Theorems to Geometric Problems, University of London, University College London (United Kingdom), 2007.
[8] T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms, MIT press, 2022.
[9] P. Duchet, Convex sets in graphs, II. Minimal path convexity, J. Combin. Theory  Ser. B 44 (1988), no. 3, 307–316. https://doi.org/10.1016/0095-8956(88)90039-1
[10] Pierre Duchet, Convexity in combinatorial structures, Proceedings of the 14th Winter School on Abstract Analysis, Circolo Matematico di Palermo, 1987,  pp. 261–293.
[11] J. Hopcroft and R. Tarjan, Algorithm 447: efficient algorithms for graph manipulation, Commun. ACM 16 (1973), no. 6, 372–378.  https://doi.org/10.1145/362248.362272
[12] D.G. Larman, On sets projectively equivalent to the vertices of a convex polytope, Bull. Lond. Math. Soc. 4 (1972), no. 1, 6–12.  https://doi.org/10.1112/blms/4.1.6
[13] H.M. Mulder, Transit functions on graphs(and posets), no. 5, pp. 117–130, Ramanujan Mathematical Society, 2008.
[14] J. Radon, Mengen konvexer körper, die einen gemeinsamen punkt enthalten, Math. Ann. 83 (1921), no. 1, 113–115.
https://doi.org/10.1007/BF01464231
[15] E. Sampathkumar, Convex sets in graphs, Indian J. Pure Appl. Math. 15 (1984), no. 10, 1065–1071.
[16] G. Sierksma, Carathéodory and Helly-numbers of convex-product-structures, Pacific J. Math. 61 (1975), no. 1, 275–282.  http://dx.doi.org/10.2140/pjm.1975.61.275.
[17] G. Sierksma, Axiomatic theory and convex product space, PhD dissertation, University of Groningen, 1976.
[18] G. Sierksma, Relationships between Carathéodory, Helly, Radon and exchange numbers of convexity spaces, Nieuw Arch. Wiskd. 25 (1977), no. 3, 115–132.
[19] P. Soberón and R. Strausz, A generalisation of Tverberg’s theorem, Discrete Comput. Geom. 47 (2012), no. 3, 455–460.  https://doi.org/10.1007/s00454-011-9379-z
[20] S. Sreedharan and M. Changat, Tolerant radon partitions on the all-paths convexity in graphs, AKCE Int. J. Graphs Comb. 21 (2024), no. 1, 11–15.  https://doi.org/10.1080/09728600.2023.2234010
[21] H. Tverberg, A generalization of Radon’s theorem, J. Lond. Math. Soc. 1 (1966), no. 1, 123–128.
[22] M.L.J. van De Vel, Theory of Convex Structures, Elsevier, 1993.
[23] D.B. West, Introduction to Graph Theory, Prentice hall Upper Saddle River, 2001.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 13 March 2025

Files

Share

How to cite

Statistics