Lower bound for the number of edges in [k,l,d]-mixed redundantly rigid graphs

Témavezető:	Király Csaba
	ELTE TTK, Operációkutatási Tsz.
email:	csaba.kiraly@ttk.elte.hu

Projekt leírás

We call a graph [k,l,d]-mixed redundantly rigid if omitting at most k-1 vertices and l-1 edges results in a graph that is (generically) rigid in d-dimensional Euclidean space. The goal of this project is to give lower bounds for the number of edges in [k,l,d]-mixed redundantly rigid graphs for specific values of [k,l,d].

Hivatkozások

T. Jordán. Combinatorial rigidity: Graphs and matroids in the theory of rigid frameworks. In Discrete Geometric Analysis, volume 34 of MSJ Memoirs, pages 33{112. Mathematical Society of Japan, Japan, 2016.

T. Jordán. Extremal problems and results in combinatorial rigidity. In A. Frank, A. Recski, and G. Wiener, editors, Proc. of the 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications May 22-25, 2017, Budapest, Hungary, pages 297{303. Department of Computer Science and Information Theory, Budapest University of Technology and Economics, 2017.

T. Jordán. Minimum size highly redundantly rigid graphs in the plane. Graphs Comb., 37(4):1415 1431, 2021.

T. Jordán. The globally rigid complete bipartite graphs. Technical Report (Quick Proof) QP-2022-02, Egerváry Research Group, Budapest, 2022. egres.elte.hu.

T. Jordán, C. Poston, and R. Roach. Extremal families of redundantly rigid graphs in three dimensions. Discret. Appl. Math., 322:448{464, 2022.

Tibor Jordán. Ear-decompositions, minimally connected matroids and rigid graphs. Journal of Graph Theory, 105(3):451{467, 2024.

Tibor Jordán, Robin Huang, Henry Simmons, Kaylee Weatherspoon, and Zeyu Zheng. Four-regular graphs with extremal rigidity properties. Discrete Mathematics, 347(4):113833, 2024.

V.E. Kaszanitzky and Cs. Király. On minimally highly vertex-redundantly rigid graphs. Graphs Comb., 32(1):225{240, 2016.

Cs. Király. On the size of highly redundantly rigid graphs. Manuscript, 2026.