آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 118 |
| تعداد مقالات | 1,457 |
| تعداد مشاهده مقاله | 1,574,987 |
| تعداد دریافت فایل اصل مقاله | 1,473,478 |
On maximum tolerant Radon partitions for all-paths convexity in graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 23 اسفند 1403 اصل مقاله (528.82 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2025.29418.1986 | ||
| نویسندگان | ||
| Sreekumar Sreedharan1؛ Manoj Changat* 2؛ Kannan Balakrishnan3 | ||
| 1Department of Mathematics, Government College for Women, Thiruvananthapuram-695014, India | ||
| 2Department of Futures Studies, University of Kerala, Thiruvananthapuram-695581, India | ||
| 3Department of Computer Applications, Cochin University of Science and Technology, Kochi-682022, India | ||
| چکیده | ||
| 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 $(P_t, Q_t)$ of $P$ is called $t$-tolerant Radon partition, if for any set $S\subseteq P$ with $|S|\le t$, the intersection of the convex hulls $\langle P_t\setminus S \rangle \cap \langle Q_t\setminus S \rangle \neq \emptyset$. 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. | ||
| کلیدواژهها | ||
| All-paths convexity؛ Radon partition؛ $(t+1)$-tolerant Radon partition؛ Algorithms for tolerant Radon partitions | ||
| مراجع | ||
|
[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. | ||
|
آمار تعداد مشاهده مقاله: 196 تعداد دریافت فایل اصل مقاله: 133 |
||