TY - JOUR AU - Katona, Gyula Y. AU - Varga, Kitti Katalin TI - Minimal toughness in special graph classes JF - DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE J2 - DISCRETE MATH THEOR VL - 25 PY - 2023 IS - 3 SP - 1 EP - 17 PG - 17 SN - 1462-7264 DO - 10.46298/dmtcs.10180 UR - https://m2.mtmt.hu/api/publication/34396591 ID - 34396591 N1 - Department of Computer Science and Information Theory, Budapest University of Technology and Economics, Hungary Alfréd Rényi Institute of Mathematics, Hungary ELKH-ELTE Egerváry Research Group, Hungary Export Date: 14 December 2023 Correspondence Address: Katona, G.Y.; Department of Computer Science and Information Theory, Hungary AB - Let be a positive real number. A graph is called -tough if the removalof any vertex set that disconnects the graph leaves at most components, and all graphs are considered 0-tough. The toughness of a graph isthe largest for which the graph is -tough, whereby the toughness ofcomplete graphs is defined as infinity. A graph is minimally -tough if thetoughness of the graph is , and the deletion of any edge from the graphdecreases the toughness. In this paper, we investigate the minimum degree andthe recognizability of minimally -tough graphs in the classes of chordalgraphs, split graphs, claw-free graphs, and -free graphs. LA - English DB - MTMT ER - TY - JOUR AU - Katona, Gyula Y. AU - Khan, Humara TI - Minimally tough chordal graphs with toughness at most 1/2 JF - DISCRETE MATHEMATICS J2 - DISCRETE MATH PY - 2023 SN - 0012-365X DO - 10.1016/j.disc.2023.113491 UR - https://m2.mtmt.hu/api/publication/33879849 ID - 33879849 N1 - Export Date: 26 May 2023 CODEN: DSMHA Correspondence Address: Katona, G.Y.; Department of Computer Science and Information Theory, Műegyetem rkp. 3, Hungary; email: katona.gyula@vik.bme.hu LA - English DB - MTMT ER - TY - CHAP AU - Katona, Gyula Y. AU - Khan, Humara ED - Jordán, Tibor ED - Katona, Gyula Y. ED - Király, Csaba ED - Wiener, Gábor TI - A polynomial-time algorithm to compute the toughness of graphs with bounded treewidth T2 - Proceedings of the 12th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications PB - BME VIK Számítástudományi és Információelméleti Tanszék CY - Budapest SN - 9789634219033 PY - 2023 SP - 259 EP - 262 PG - 4 UR - https://m2.mtmt.hu/api/publication/33741303 ID - 33741303 LA - English DB - MTMT ER - TY - BOOK ED - Jordán, Tibor ED - Katona, Gyula Y. ED - Király, Csaba ED - Wiener, Gábor TI - Proceedings of the 12th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications PB - BME VIK Számítástudományi és Információelméleti Tanszék CY - Budapest PY - 2023 SP - 613 SN - 9789634219033 UR - https://m2.mtmt.hu/api/publication/33716748 ID - 33716748 LA - English DB - MTMT ER - TY - JOUR AU - Katona, Gyula Y. AU - Varga, Kitti Katalin TI - Strengthening some complexity results on toughness of graphs JF - DISCUSSIONES MATHEMATICAE GRAPH THEORY J2 - DISCUSS MATH GRAPH T VL - 43 PY - 2023 IS - 2 SP - 401 EP - 419 PG - 19 SN - 1234-3099 DO - 10.7151/dmgt.2372 UR - https://m2.mtmt.hu/api/publication/31798950 ID - 31798950 N1 - Export Date: 20 June 2022 LA - English DB - MTMT ER - TY - GEN AU - Clément, Dallard AU - Blas, Fernández AU - Katona, Gyula Y. AU - Martin, Milanič AU - Varga, Kitti Katalin TI - Conditions for minimally tough graphs PY - 2022 SP - & UR - https://m2.mtmt.hu/api/publication/33127461 ID - 33127461 AB - Katona, Soltész, and Varga showed that no induced subgraph can be excluded from the class of minimally tough graphs. In this paper, we consider the opposite question, namely which induced subgraphs, if any, must necessarily be present in each minimally t-tough graph. Katona and Varga showed that for any rational number t∈(1/2,1], every minimally t-tough graph contains a hole. We complement this result by showing that for any rational number t>1, every minimally t-tough graph must contain either a hole or an induced subgraph isomorphic to the k-sun for some integer k≥3. We also show that for any rational number t>1/2, every minimally t-tough graph must contain either an induced 4-cycle, an induced 5-cycle, or two independent edges as an induced subgraph. LA - English DB - MTMT ER - TY - JOUR AU - Katona, Gyula Y. AU - Kovács, István AU - Varga, Kitti Katalin TI - The complexity of recognizing minimally tough graphs JF - DISCRETE APPLIED MATHEMATICS J2 - DISCRETE APPL MATH VL - 294 PY - 2021 SP - 55 EP - 84 PG - 30 SN - 0166-218X DO - 10.1016/j.dam.2021.01.022 UR - https://m2.mtmt.hu/api/publication/31881046 ID - 31881046 LA - English DB - MTMT ER - TY - JOUR AU - Győri, Ervin AU - Katona, Gyula Y. AU - Papp, László F. TI - Optimal Pebbling Number of the Square Grid JF - GRAPHS AND COMBINATORICS J2 - GRAPH COMBINATOR VL - 36 PY - 2020 IS - 3 SP - 803 EP - 829 PG - 27 SN - 0911-0119 DO - 10.1007/s00373-020-02154-z UR - https://m2.mtmt.hu/api/publication/31293349 ID - 31293349 N1 - Funding Agency and Grant Number: Budapest University of Technology and Economics (BME); National Research, Development and Innovation Office NKFIH [K124171, K132696]; National Research, Development and Innovation Fund (Thematic Excellence Program) [TUDFO/51757/2019-ITM]; Higher Education Excellence Program of the Ministry of Human Capacities Funding text: Open access funding provided by Budapest University of Technology and Economics (BME). The authors would like to thank Casey Tompkins for his generous reading of an early draft of this paper, and for his invaluable comments. The research of Ervin Gyri and Gyula Y. Katona is partially supported by National Research, Development and Innovation Office NKFIH, Grant K132696. The research of Gyula Y. Katona and Laszlo F. Papp is partially supported by National Research, Development and Innovation Office NKFIH, Grant K124171. The research reported in this paper has been supported by the National Research, Development and Innovation Fund (TUDFO/51757/2019-ITM, Thematic Excellence Program), and by the Higher Education Excellence Program of the Ministry of Human Capacities in the frame of Artificial Intelligence research area of Budapest University of Technology and Economics (BME FIKP-MI/SC). Department of Mathematics, Central European University, Budapest, Hungary Alfréd Rényi Institute of Mathematics, Budapest, Hungary Department of Computer Science and Information Theory, Budapest University of Technology and Economics, Budapest, Hungary MTA-ELTE Numerical Analysis and Large Networks Research Group, Budapest, Hungary Export Date: 1 February 2021 Correspondence Address: Papp, L.F.; MTA-ELTE Numerical Analysis and Large Networks Research GroupHungary; email: lazsa@cs.bme.hu Funding details: Nemzeti Kutatási, Fejlesztési és Innovaciós Alap, NKFIA, TUDFO/51757/2019-ITM Funding details: Emberi Eroforrások Minisztériuma, EMMI Funding details: Budapesti Műszaki és Gazdaságtudományi Egyetem, BME, BME FIKP-MI/SC Funding details: National Research, Development and Innovation Office, K132696, K124171 Funding text 1: Open access funding provided by Budapest University of Technology and Economics (BME). The authors would like to thank Casey Tompkins for his generous reading of an early draft of this paper, and for his invaluable comments. The research of Ervin Győri and Gyula Y. Katona is partially supported by National Research, Development and Innovation Office NKFIH, Grant K132696. The research of Gyula Y. Katona and László F. Papp is partially supported by National Research, Development and Innovation Office NKFIH, Grant K124171. The research reported in this paper has been supported by the National Research, Development and Innovation Fund (TUDFO/51757/2019-ITM, Thematic Excellence Program), and by the Higher Education Excellence Program of the Ministry of Human Capacities in the frame of Artificial Intelligence research area of Budapest University of Technology and Economics (BME FIKP-MI/SC). Department of Mathematics, Central European University, Budapest, Hungary Alfréd Rényi Institute of Mathematics, Budapest, Hungary Department of Computer Science and Information Theory, Budapest University of Technology and Economics, Budapest, Hungary MTA-ELTE Numerical Analysis and Large Networks Research Group, Budapest, Hungary Export Date: 29 July 2021 Correspondence Address: Papp, L.F.; MTA-ELTE Numerical Analysis and Large Networks Research GroupHungary; email: lazsa@cs.bme.hu Funding details: Budapesti Műszaki és Gazdaságtudományi Egyetem, BME, BME FIKP-MI/SC Funding details: Emberi Eroforrások Minisztériuma, EMMI Funding details: Nemzeti Kutatási, Fejlesztési és Innovaciós Alap, NKFIA, TUDFO/51757/2019-ITM Funding details: National Research, Development and Innovation Office, K124171, K132696 Funding text 1: Open access funding provided by Budapest University of Technology and Economics (BME). The authors would like to thank Casey Tompkins for his generous reading of an early draft of this paper, and for his invaluable comments. The research of Ervin Gy?ri and Gyula Y. Katona is partially supported by National Research, Development and Innovation Office NKFIH, Grant K132696. The research of Gyula Y. Katona and L?szl? F. Papp is partially supported by National Research, Development and Innovation Office NKFIH, Grant K124171. The research reported in this paper has been supported by the National Research, Development and Innovation Fund (TUDFO/51757/2019-ITM, Thematic Excellence Program), and by the Higher Education Excellence Program of the Ministry of Human Capacities in the frame of Artificial Intelligence research area of Budapest University of Technology and Economics (BME FIKP-MI/SC). Funding text 2: Open access funding provided by Budapest University of Technology and Economics (BME). The authors would like to thank Casey Tompkins for his generous reading of an early draft of this paper, and for his invaluable comments. The research of Ervin Győri and Gyula Y. Katona is partially supported by National Research, Development and Innovation Office NKFIH, Grant K132696. The research of Gyula Y. Katona and László F. Papp is partially supported by National Research, Development and Innovation Office NKFIH, Grant K124171. The research reported in this paper has been supported by the National Research, Development and Innovation Fund (TUDFO/51757/2019-ITM, Thematic Excellence Program), and by the Higher Education Excellence Program of the Ministry of Human Capacities in the frame of Artificial Intelligence research area of Budapest University of Technology and Economics (BME FIKP-MI/SC). LA - English DB - MTMT ER - TY - CHAP AU - Katona, Gyula Y. AU - Kovács, István AU - Varga, Kitti Katalin ED - Hirai, Hiroshi ED - Iwata, Satoru ED - Tanigawa, Shin-ichi TI - The complexity of recognizing minimally tough graphs T2 - Proceedings of the 11th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications PB - Department of Mathematical Informatics, University of Tokyo CY - Tokió SN - 9784600001599 PY - 2019 SP - 456 EP - 465 PG - 10 UR - https://m2.mtmt.hu/api/publication/30820406 ID - 30820406 LA - English DB - MTMT ER - TY - CHAP AU - Katona, Gyula Y. AU - Mikio, Kano AU - Varga, Kitti Katalin ED - Hirai, Hiroshi ED - Iwata, Satoru ED - Tanigawa, Shin-ichi TI - Decomposition of a graph into two disjoint odd subgraphs T2 - Proceedings of the 11th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications PB - Department of Mathematical Informatics, University of Tokyo CY - Tokió SN - 9784600001599 PY - 2019 SP - 233 EP - 239 PG - 7 UR - https://m2.mtmt.hu/api/publication/30758729 ID - 30758729 LA - English DB - MTMT ER -