Soma Villányi

activity

20232026

collaborators

7 papers

math.CO2026

Rank Contributions of Vertices in Rigidity Matroids of Clique Covered Graphs

Bill Jackson, Tibor Jordán, Soma Villányi

The problems of characterizing the graphs $G$ which are generically rigid in $R^{d}$ , or more generally, determining the rank function of the $d$ -dimensional rigidity matro…

math.CO2025

Sufficient conditions for bipartite rigidity, symmetric completability and hyperconnectivity of graphs

Dániel Garamvölgyi, Bill Jackson, Tibor Jordán +1

We consider three matroids defined by Kalai in 1985: the symmetric completion matroid $S_{d}$ on the edge set of a looped complete graph; the hyperconnectivity matroid $\ma…

math.CO2025

Degree Sum Conditions for Graph Rigidity

Tibor Jordán, Xuemei Liu, Soma Villányi

We study sufficient conditions for the generic rigidity of a graph $G$ expressed in terms of (i) its minimum degree $δ (G)$ , or (ii) the parameter $η(G)=\min_{uv\notin E}(°(u)+°(v))…

math.CO2024

Globally linked pairs and cheapest globally rigid supergraphs

Tibor Jordán, Soma Villányi

Given a graph $G$ , a cost function on the non-edges of $G$ , and an integer $d$ , the problem of finding a cheapest globally rigid supergraph of $G$ in $R^{d}$ is NP-hard for…

math.CO2024

Highly connected orientations from edge-disjoint rigid subgraphs

Dániel Garamvölgyi, Tibor Jordán, Csaba Király +1

We give an affirmative answer to a long-standing conjecture of Thomassen, stating that every sufficiently highly connected graph has a $k$ -vertex-connected orientation. We prove th…

math.CO2023

Every $d (d + 1)$ -connected graph is globally rigid in $R^{d}$