TY - JOUR AU - Bujtás, Csilla AU - Rote, Günter AU - Tuza, Zsolt TI - Optimal strategies in fractional games: vertex cover and domination JF - ARS MATHEMATICA CONTEMPORANEA J2 - ARS MATH CONTEMPOR VL - 2024 PY - 2024 SN - 1855-3966 DO - 10.26493/1855-3974.2771.4df UR - https://m2.mtmt.hu/api/publication/34820138 ID - 34820138 LA - English DB - MTMT ER - TY - JOUR AU - Patkós, Balázs AU - Tuza, Zsolt AU - Vizer, Máté TI - Extremal Graph Theoretic Questions for q-Ary Vectors JF - GRAPHS AND COMBINATORICS J2 - GRAPH COMBINATOR VL - 40 PY - 2024 IS - 3 PG - 21 SN - 0911-0119 DO - 10.1007/s00373-024-02787-4 UR - https://m2.mtmt.hu/api/publication/34818984 ID - 34818984 N1 - Export Date: 3 May 2024 Correspondence Address: Vizer, M.; Department of Computer Science and Information Theory, Hungary; email: vizermate@gmail.com AB - A q -graph H on n vertices is a set of vectors of length n with all entries from \{0,1,\dots ,q\} { 0 , 1 , ⋯ , q } and every vector (that we call a q -edge) having exactly two non-zero entries. The support of a q -edge {\textbf{x}} x is the pair S_{\textbf{x}} S x of indices of non-zero entries. We say that H is an s -copy of an ordinary graph F if |H|=|E(F)| | H | = | E ( F ) | , F is isomorphic to the graph with edge set \{S_{\textbf{x}}:{\textbf{x}}\in H\} { S x : x ∈ H } , and whenever v\in e,e'\in E(F) v ∈ e , e ′ ∈ E ( F ) , the entries with index corresponding to v in the q -edges corresponding to e and e' e ′ sum up to at least s . E.g., the q -edges (1, 3, 0, 0, 0), (0, 1, 0, 0, 3), and (3, 0, 0, 0, 1) form a 4-triangle. The Turán number \mathop {}\!\textrm{ex}(n,F,q,s) ex ( n , F , q , s ) is the maximum number of q -edges that a q -graph H on n vertices can have if it does not contain any s -copies of F . In the present paper, we determine the asymptotics of \mathop {}\!\textrm{ex}(n,F,q,q+1) ex ( n , F , q , q + 1 ) for many graphs F . LA - English DB - MTMT ER - TY - JOUR AU - Caro, Yair AU - Patkós, Balázs AU - Tuza, Zsolt TI - Connected Turán number of trees JF - ARS MATHEMATICA CONTEMPORANEA J2 - ARS MATH CONTEMPOR VL - Manuscript Published 2023-10-03 PY - 2024 SP - & SN - 1855-3966 DO - 10.26493/1855-3974.3109.e4b UR - https://m2.mtmt.hu/api/publication/34760346 ID - 34760346 AB - As a variant of the much studied Turán number, ex(n,F), the largest number of edges that an n-vertex F-free graph may contain, we introduce the connected Turán number exc(n,F), the largest number of edges that an n-vertex connected F-free graph may contain. We focus on the case where the forbidden graph is a tree. The celebrated conjecture of Erdős and Sós states that for any tree T, we have ex(n,T)≤(|T|−2)n2. We address the problem how much smaller exc(n,T) can be, what is the smallest possible ratio of exc(n,T) and (|T|−2)n2 as |T| grows. We also determine the exact value of exc(n,T) for small trees, in particular for all trees with at most six vertices. We introduce general constructions of connected T-free graphs based on graph parameters as longest path, matching number, branching number, etc. LA - English DB - MTMT ER - TY - JOUR AU - Keszler, Anita AU - Tuza, Zsolt TI - Spectrum of 3-uniform 6- and 9-cycle systems over K (3) v − I JF - DISCRETE MATHEMATICS J2 - DISCRETE MATH VL - 347 PY - 2024 IS - 3 PG - 10 SN - 0012-365X DO - 10.1016/j.disc.2023.113782 UR - https://m2.mtmt.hu/api/publication/34397551 ID - 34397551 N1 - Machine Perception Research Laboratory, Institute for Computer Science and Control (SZTAKI), Kende u. 13–17, Budapest, 1111, Hungary Alfred Renyi Institute of Mathematics, Realtanoda u. 13–15, Budapest, 1053, Hungary Department of Computer Science and Systems Technology, University of Pannonia, Egyetem u. 10, Veszprem, 8200, Hungary Export Date: 7 December 2023 CODEN: DSMHA Correspondence Address: Tuza, Z.; Alfred Renyi Institute of Mathematics, Realtanoda u. 13–15, Hungary; email: tuza.zsolt@mik.uni-pannon.hu LA - English DB - MTMT ER - TY - JOUR AU - Gerbner, Dániel AU - Patkós, Balázs AU - Tuza, Zsolt AU - Vizer, Máté TI - Some exact results for regular Turán problems for all large orders JF - EUROPEAN JOURNAL OF COMBINATORICS J2 - EUR J COMBIN VL - 117 PY - 2024 SN - 0195-6698 DO - 10.1016/j.ejc.2023.103828 UR - https://m2.mtmt.hu/api/publication/34162027 ID - 34162027 N1 - Alfréd Rényi Institute of Mathematics, Hungary Lab. of Combinatorial and Geometric Structures, Moscow Inst. of Physics and Technology, Russian Federation Department of Computer Science and Systems Technology, University of Pannonia, Hungary Export Date: 14 February 2024 CODEN: EJOCD Funding details: Government Council on Grants, Russian Federation, N 075-15-2019-1926 Funding details: Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, NKFI, FK 132060, KH130371, SNN 129364, ÚNKP-19-4-BME-287 Funding details: National Research, Development and Innovation Office Funding text 1: Research was supported by the National Research, Development and Innovation Office, Hungary – NKFIH under the grants FK 132060 , KH130371 and SNN 129364 . Research of Vizer was supported by the János Bolyai Research Fellowship and the New National Excellence Program under the grant number ÚNKP-19-4-BME-287 . Research of Patkós was supported by the grant of Russian Government N 075-15-2019-1926 . LA - English DB - MTMT ER - TY - JOUR AU - Tuza, Zsolt TI - Gregarious Decompositions of Complete Equipartite Graphs and Related Structures JF - SYMMETRY (BASEL) J2 - SYMMETRY-BASEL VL - 15 PY - 2023 IS - 12 SP - 2097 SN - 2073-8994 DO - 10.3390/sym15122097 UR - https://m2.mtmt.hu/api/publication/34397516 ID - 34397516 AB - In a finite mathematical structure with a given partition, a substructure is said to be gregarious if either it meets each partition class or it shares at most one element with each partition class. In this paper, we considered edge decompositions of graphs and hypergraphs into gregarious subgraphs and subhypergraphs. We mostly dealt with “complete equipartite” graphs and hypergraphs, where the vertex classes have the same size and precisely those edges or hyperedges of a fixed cardinality are present that do not contain more than one element from any class. Some related graph classes generated by product operations were also considered. The generalization to hypergraphs offers a wide open area for further research. LA - English DB - MTMT ER - TY - CONF AU - Ábrahám, Gyula AU - Dósa, György AU - Olaj, Tomas Attila AU - Tuza, Zsolt AU - Lars, Magnus Hvattum TI - Egy téglalap-pakolási feladat, és megoldása különféle módszerekkel T2 - XXXV. Magyar Operációkutatás Konferencia PB - Budapesti Corvinus Egyetem PY - 2023 SP - 10 UR - https://m2.mtmt.hu/api/publication/34202465 ID - 34202465 LA - Hungarian DB - MTMT ER - TY - JOUR AU - Patkós, Balázs AU - Tuza, Zsolt AU - Vizer, Máté TI - Vector sum-intersection theorems JF - DISCRETE MATHEMATICS J2 - DISCRETE MATH VL - 346 PY - 2023 IS - 10 SN - 0012-365X DO - 10.1016/j.disc.2023.113506 UR - https://m2.mtmt.hu/api/publication/34023034 ID - 34023034 N1 - Alfréd Rényi Institute of Mathematics, Hungary University of Pannónia, Hungary Export Date: 2 August 2023 CODEN: DSMHA Correspondence Address: Vizer, M.; Alfréd Rényi Institute of MathematicsHungary; email: vizermate@gmail.com Funding details: Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, NKFIH, FK 132060, KH130371, SNN 129364, ÚNKP-21-5-BME-361 Funding text 1: Patkós's research is partially supported by NKFIH grants SNN 129364 and FK 132060.Tuza's research is partially supported by NKFIH grant SNN 129364.Vizer's research is partially supported by NKFIH grants SNN 129364, FK 132060, KH130371, by the János Bolyai Research Fellowship and by the New National Excellence Program under the grant number ÚNKP-21-5-BME-361. LA - English DB - MTMT ER - TY - JOUR AU - Czaun, Péter Bence AU - Pusztai, Pál AU - Sebők, Levente AU - Tuza, Zsolt TI - Minimal Non-C-Perfect Hypergraphs with Circular Symmetry JF - SYMMETRY (BASEL) J2 - SYMMETRY-BASEL VL - 15 PY - 2023 IS - 5 SN - 2073-8994 DO - 10.3390/sym15051114 UR - https://m2.mtmt.hu/api/publication/33843688 ID - 33843688 N1 - Faculty of Information Technology, University of Pannonia, Egyetem Street 10, Veszprém, 8200, Hungary Department of Mathematics and Computer Science, Széchenyi István University, Egyetem Square 1, Győr, 9026, Hungary Alfréd Rényi Institute of Mathematics, Reáltanoda Street 13–15, Budapest, 1053, Hungary Export Date: 4 October 2023 Correspondence Address: Tuza, Z.; Faculty of Information Technology, Egyetem Street 10, Hungary; email: tuza.zsolt@mik.uni-pannon.hu AB - In this research paper, we study 3-uniform hypergraphs H=(X,E) with circular symmetry. Two parameters are considered: the largest size α(H) of a set S⊂X not containing any edge E∈E, and the maximum number χ¯(H) of colors in a vertex coloring of H such that each E∈E contains two vertices of the same color. The problem considered here is to characterize those H in which the equality χ¯(H′)=α(H′) holds for every induced subhypergraph H′=(X′,E′) of H. A well-known objection against χ¯(H′)=α(H′) is where ∩E∈E′E=1, termed “monostar”. Steps toward a solution to this approach is to investigate the properties of monostar-free structures. All such H are completely identified up to 16 vertices, with the aid of a computer. Most of them can be shown to satisfy χ¯(H)=α(H), and the few exceptions contain one or both of two specific induced subhypergraphs H5⥁, H6⥁ on five and six vertices, respectively, both with χ¯=2 and α=3. Furthermore, a general conjecture is raised for hypergraphs of prime orders. LA - English DB - MTMT ER - TY - JOUR AU - Ábrahám, Gyula AU - Dósa, György AU - Lars, Magnus Hvattum AU - Olaj, Tomas Attila AU - Tuza, Zsolt TI - The board packing problem JF - EUROPEAN JOURNAL OF OPERATIONAL RESEARCH J2 - EJOR VL - 308 PY - 2023 IS - 3 SP - 1056 EP - 1073 PG - 18 SN - 0377-2217 DO - 10.1016/j.ejor.2023.01.030 UR - https://m2.mtmt.hu/api/publication/33569160 ID - 33569160 N1 - University of Pannonia, Veszprém, Hungary Faculty of Logistics, Molde University College, Norway Alfréd Rényi Institute of Mathematics, Budapest, 1053, Hungary Export Date: 20 February 2023 CODEN: EJORD Correspondence Address: Dosa, G.; University of PannoniaHungary; email: dosagy@almos.uni-pannon.hu Funding details: Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, NKFIH, 2019-2.1.11-TÉT-2020-00113, SNN 129364 Funding text 1: The authors would like to thank three anonymous reviewers, whose useful ideas and comments helped to improve this paper significantly. The research of Gyorgy Dosa and Zsolt Tuza is supported in part by the National Research, Development and Innovation Office – NKFIH under the grant SNN 129364 . Gyula Abraham and Gyorgy Dosa acknowledge financial support also from the Slovenian – Hungarian bilateral project, “Optimization and fault forecasting in port logistics processes using artificial intelligence, process mining and operations research”, grant 2019-2.1.11-TÉT-2020-00113. AB - We introduce the board packing problem (BoPP). In this problem we are given a rectangular board with a given number of rows and columns. Each position of the board has an integer value representing a gain, or revenue, that is obtained if the position is covered. A set of rectangles is also given, each with a given size and cost. The objective is to purchase some rectangles to place on the board so as to maximize the profit, which is the sum of the gain values of the covered cells minus the total cost of purchased rectangles. This problem subsumes several natural optimization problems that arise in practice. A mixedinteger programming model for the BoPP problem is provided, along with a proof that BoPP is NP -hard by reduction from the satisfiability problem. An evolutionary algorithm is also developed that can solve large instances of BoPP. We introduce benchmark instances and make extensive computer examinations.(c) 2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license ( http://creativecommons.org/licenses/by-nc-nd/4.0/ ) LA - English DB - MTMT ER -