{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T16:25:50Z","timestamp":1769271950900,"version":"3.49.0"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,12,5]],"date-time":"2024-12-05T00:00:00Z","timestamp":1733356800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,12,5]],"date-time":"2024-12-05T00:00:00Z","timestamp":1733356800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001655","name":"Deutscher Akademischer Austauschdienst","doi-asserted-by":"publisher","award":["57683501"],"award-info":[{"award-number":["57683501"]}],"id":[{"id":"10.13039\/501100001655","id-type":"DOI","asserted-by":"publisher"}]},{"name":"DST, Govt. of India","award":["DST\/INT\/DAAD\/P-03\/ 2023 (G)"],"award-info":[{"award-number":["DST\/INT\/DAAD\/P-03\/ 2023 (G)"]}]},{"name":"CSIR-HRDG","award":["09\/0102(12336)\/2021-EMR-I"],"award-info":[{"award-number":["09\/0102(12336)\/2021-EMR-I"]}]},{"DOI":"10.13039\/501100008678","name":"Universit\u00e4t Leipzig","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100008678","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2025,2]]},"abstract":"Abstract<\/jats:title>\n Transit functions \n \n $$R:V\\times V\\rightarrow 2^V$$<\/jats:tex-math>\n \n \n R<\/mml:mi>\n :<\/mml:mo>\n V<\/mml:mi>\n \u00d7<\/mml:mo>\n V<\/mml:mi>\n \u2192<\/mml:mo>\n \n 2<\/mml:mn>\n V<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> model abstract betweenness as well as binary clustering. Examples are I<\/jats:italic>(u<\/jats:italic>,\u00a0v<\/jats:italic>), the interval between u<\/jats:italic> and v<\/jats:italic>, comprising all points on a shortest path from u<\/jats:italic> to v<\/jats:italic>, and C<\/jats:italic>(u<\/jats:italic>,\u00a0v<\/jats:italic>), the set of all cut vertices separating u<\/jats:italic> and v<\/jats:italic> together with u<\/jats:italic> and v<\/jats:italic>. Here we characterize the cut-vertex transit function of hypergraphs as the monotone transit functions satisfying (x) \n \n $$R(u,v)\\subseteq R(u,x)\\cup R(x,v)$$<\/jats:tex-math>\n \n \n R<\/mml:mi>\n (<\/mml:mo>\n u<\/mml:mi>\n ,<\/mml:mo>\n v<\/mml:mi>\n )<\/mml:mo>\n \u2286<\/mml:mo>\n R<\/mml:mi>\n (<\/mml:mo>\n u<\/mml:mi>\n ,<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n \u222a<\/mml:mo>\n R<\/mml:mi>\n (<\/mml:mo>\n x<\/mml:mi>\n ,<\/mml:mo>\n v<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> for all \n \n $$u,v,x\\in V$$<\/jats:tex-math>\n \n \n u<\/mml:mi>\n ,<\/mml:mo>\n v<\/mml:mi>\n ,<\/mml:mo>\n x<\/mml:mi>\n \u2208<\/mml:mo>\n V<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. We define new hypergraph classes as restrictions and generalizations of linear hypergraphs and describe relevant properties of blocks and Berge cycles. We then show that the cut-vertex transit function coincides with the interval function exactly for linear B\n \n $$^*$$<\/jats:tex-math>\n \n \n \n \n \u2217<\/mml:mo>\n <\/mml:mmultiscripts>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>-hypergraphs, generalizing a similar result for graphs. Moreover, we identify a subclass of block hypergraphs and characterize it using axioms on its interval function and prove a similar characterization for block graphs.<\/jats:p>","DOI":"10.1007\/s00373-024-02864-8","type":"journal-article","created":{"date-parts":[[2024,12,5]],"date-time":"2024-12-05T19:06:21Z","timestamp":1733425581000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the Cut-Vertex and the Interval Transit Functions of Hypergraphs"],"prefix":"10.1007","volume":"41","author":[{"given":"Ameera Vaheeda","family":"Shanavas","sequence":"first","affiliation":[]},{"given":"Manoj","family":"Changat","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5016-5191","authenticated-orcid":false,"given":"Peter F.","family":"Stadler","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,12,5]]},"reference":[{"key":"2864_CR1","unstructured":"Mulder, H.M.: Transit functions on graphs (and posets). In: Changat, M., Klav\u017ear, S., Mulder, H.M., Vijayakumar, A. (eds.) Convexity in Discrete Structures. RMS Lecture Notes Series, pp. 117\u2013130 (2008)"},{"issue":"5","key":"2864_CR2","doi-asserted-by":"publisher","first-page":"1172","DOI":"10.1016\/j.ejc.2008.09.007","volume":"30","author":"HM Mulder","year":"2009","unstructured":"Mulder, H.M., Nebesk\u00fd, L.: Axiomatic characterization of the interval function of a graph. Eur. J. Combin. 30(5), 1172\u20131185 (2009). https:\/\/doi.org\/10.1016\/j.ejc.2008.09.007","journal-title":"Eur. J. Combin."},{"key":"2864_CR3","doi-asserted-by":"publisher","unstructured":"Changat, M., Hossein\u00a0Nezhad, F., Stadler, P.F.: Cut-vertex transit functions of a hypergraphs. In: Mudgal, A., Subramanian, C.R. (eds.) CALDAM\u00a0\u201921. 7th Annual International Conference on Algorithms and Discrete Applied Mathematics. Lecture Notes Comp. Sci., vol. 12601, pp. 222\u2013233. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-67899-9_17","DOI":"10.1007\/978-3-030-67899-9_17"},{"key":"2864_CR4","volume-title":"Hypergraphs","author":"C Berge","year":"1989","unstructured":"Berge, C.: Hypergraphs. North Holland, Amsterdam (1989)"},{"key":"2864_CR5","volume-title":"Introduction to Graph Theory","author":"DB West","year":"2000","unstructured":"West, D.B.: Introduction to Graph Theory. Prentice Hall, Upper Saddle River (2000)"},{"key":"2864_CR6","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1145\/2402.322390","volume":"30","author":"R Fagin","year":"1983","unstructured":"Fagin, R.: Degrees of acyclicity for hypergraphs and relational database schemes. J. ACM 30, 514\u2013550 (1983). https:\/\/doi.org\/10.1145\/2402.322390","journal-title":"J. ACM"},{"key":"2864_CR7","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0304-3975(85)90012-X","volume":"35","author":"G Ausiello","year":"1985","unstructured":"Ausiello, G., d\u2019Atri, A.: On the existence of acyclic views in a database scheme. Theor. Comput. Sci. 35, 165\u2013177 (1985). https:\/\/doi.org\/10.1016\/0304-3975(85)90012-X","journal-title":"Theor. Comput. Sci."},{"key":"2864_CR8","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1016\/j.ipl.2012.05.005","volume":"112","author":"D Duris","year":"2012","unstructured":"Duris, D.: Some characterizations of $$\\gamma $$ and $$\\beta $$-acyclicity of hypergraphs. Inf. Process. Lett. 112, 617\u2013620 (2012). https:\/\/doi.org\/10.1016\/j.ipl.2012.05.005","journal-title":"Inf. Process. Lett."},{"key":"2864_CR9","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1145\/2983573","volume":"49","author":"J Brault-Baron","year":"2017","unstructured":"Brault-Baron, J.: Hypergraph acyclicity revisited. ACM Comput. Surv. 49, 54 (2017). https:\/\/doi.org\/10.1145\/2983573","journal-title":"ACM Comput. Surv."},{"key":"2864_CR10","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0304-3975(84)90030-6","volume":"32","author":"D Maier","year":"1984","unstructured":"Maier, D., Ullman, J.D.: Connections in acyclic hypergraphs. Theor. Comput. Sci. 32, 185\u2013199 (1984). https:\/\/doi.org\/10.1016\/0304-3975(84)90030-6","journal-title":"Theor. Comput. Sci."},{"key":"2864_CR11","doi-asserted-by":"publisher","first-page":"117","DOI":"10.26493\/1855-3974.831.e12","volume":"14","author":"M Changat","year":"2018","unstructured":"Changat, M., Nezhad, F.H., Stadler, P.F.: Axiomatic characterization of transit functions of hierarchies. Ars Math. Contemp. 14, 117\u2013128 (2018). https:\/\/doi.org\/10.26493\/1855-3974.831.e12","journal-title":"Ars Math. Contemp."},{"key":"2864_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.26493\/2590-9770.1260.989","volume":"2","author":"M Changat","year":"2019","unstructured":"Changat, M., Narasimha-Shenoi, P.G., Stadler, P.F.: Axiomatic characterization of transit functions of weak hierarchies. Art Discrete Appl. Math. 2, 1\u201301 (2019). https:\/\/doi.org\/10.26493\/2590-9770.1260.989","journal-title":"Art Discrete Appl. Math."},{"key":"2864_CR13","unstructured":"Changat, M., Shanavas, A.V., Stadler, P.F.: Transit functions and clustering systems. Art Discrete Appl. Math. (2024). arXiv:1048550\/arXiv:2401.15662(in press)"},{"key":"2864_CR14","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/j.dam.2024.06.032","volume":"357","author":"M Changat","year":"2024","unstructured":"Changat, M., Shanavas, A.V., Stadler, P.F.: Transit functions and pyramid-like binary clustering systems. Discrete Appl. Math. 357, 365\u2013384 (2024). https:\/\/doi.org\/10.1016\/j.dam.2024.06.032","journal-title":"Discrete Appl. Math."},{"key":"2864_CR15","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/S0304-0208(08)72924-4","volume":"12","author":"P Duchet","year":"1984","unstructured":"Duchet, P.: Classical perfect graphs\u2014an introduction with emphasis on triangulated and interval graphs. Ann. Discrete Math. 12, 67\u201396 (1984). https:\/\/doi.org\/10.1016\/S0304-0208(08)72924-4","journal-title":"Ann. Discrete Math."},{"key":"2864_CR16","doi-asserted-by":"publisher","unstructured":"Brandes, U., Cornelsen, S., Pampel, B., Sallaberry, A.: Blocks of hypergraphs. In: Iliopoulos, C.S., Smyth, W.F. (eds.) Combinatorial Algorithms. IWOCA 2010. Lect. Notes Computer Sci., vol. 6460, pp. 201\u2013211. Springer, Berlin (2011). https:\/\/doi.org\/10.1007\/978-3-642-19222-7_21","DOI":"10.1007\/978-3-642-19222-7_21"},{"key":"2864_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4153\/cmb-1963-001-x","volume":"6","author":"F Harary","year":"1963","unstructured":"Harary, F.: A characterization of block-graphs. Can. Math. Bull. 6, 1\u20136 (1963). https:\/\/doi.org\/10.4153\/cmb-1963-001-x","journal-title":"Can. Math. Bull."},{"key":"2864_CR18","doi-asserted-by":"publisher","first-page":"885","DOI":"10.1016\/j.disc.2015.01.004","volume":"338","author":"K Balakrishnan","year":"2015","unstructured":"Balakrishnan, K., Changat, M., Lakshmikuttyamma, A.K., Mathew, J., Mulder, H.M., Narasimha-Shenoi, P.G., Narayanan, N.: Axiomatic characterization of the interval function of a block graph. Discrete Math. 338, 885\u2013894 (2015). https:\/\/doi.org\/10.1016\/j.disc.2015.01.004","journal-title":"Discrete Math."},{"key":"2864_CR19","doi-asserted-by":"publisher","first-page":"951","DOI":"10.1016\/j.disc.2013.01.013","volume":"313","author":"M Changat","year":"2013","unstructured":"Changat, M., Lakshmikuttyamma, A.K., Mathews, J., Peterin, I., Narasimha-Shenoi, P.G., Seethakuttyamma, G., \u0160pacapan, S.: A forbidden subgraph characterization of some graph classes using betweenness axioms. Discrete Math. 313, 951\u2013958 (2013). https:\/\/doi.org\/10.1016\/j.disc.2013.01.013","journal-title":"Discrete Math."},{"key":"2864_CR20","doi-asserted-by":"publisher","unstructured":"Le\u00a0Gall, F.: Faster rectangular matrix multiplication by combination loss analysis. In: Woodruff, D.P. (ed.) Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 3765\u20133791 (2024). https:\/\/doi.org\/10.1137\/1.9781611977912.133","DOI":"10.1137\/1.9781611977912.133"},{"issue":"1","key":"2864_CR21","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0167-6423(95)00005-D","volume":"25","author":"K Madhukar","year":"1995","unstructured":"Madhukar, K., Pavan Kumar, D., Pandu Rangan, C., Sundar, R.: Systematic design of an algorithm for biconnected components. Sci. Comput. Program. 25(1), 63\u201377 (1995). https:\/\/doi.org\/10.1016\/0167-6423(95)00005-D","journal-title":"Sci. Comput. Program."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-024-02864-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-024-02864-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-024-02864-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,27]],"date-time":"2025-05-27T04:22:32Z","timestamp":1748319752000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-024-02864-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,5]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,2]]}},"alternative-id":["2864"],"URL":"https:\/\/doi.org\/10.1007\/s00373-024-02864-8","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,5]]},"assertion":[{"value":"13 May 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 November 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 December 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}}],"article-number":"4"}}