|
A graph $G=(V,E)$ is called $k$-edge rigid ($k$-edge globally rigid, resp.), if it stays rigid (globally rigid, resp.) after the deletion of at most $k-1$ edges. We can define $k$-vertex rigidity and $k$-vertex global rigidity in a similar manner. It is known that if $G$ is $3$-edge rigid ($2$-edge globally rigid, $2$-vertex globally rigid) with $|V|\geq 5$ then $|E|\geq 2|V|$ holds. Furthermore, the graphs that satisfy the edge count with equality are all $4$-regular.
In this paper we show that for a $4$-regular graph $G$ the properties of $3$-edge rigidity, $2$-edge global rigidity, and essential $6$-edge connectivity are equivalent. By sharpening a result of H. Fleischner, F. Genest, and B. Jackson we give a new inductive construction for the family of $4$-regular and essentially $6$-edge connected graphs (and hence also for the $4$-regular graphs with these rigidity properties). We prove that $G$ is $2$-vertex globally rigid if and only if it is $4$-vertex connected and essentially $6$-edge connected.
We also consider $2$-vertex rigid graphs $G=(V,E)$ with minimum size $|E|=2|V|-1$ as well as with $|E|=2|V|$.
In the former case we use our results on essentially $6$-edge connected graphs to
develop a new inductive construction, complementing an earlier, different construction of
B. Servatius. In the latter case we characterize the edge pairs of $G$ whose deletion preserves rigidity,
and use this result to verify the correctness of a construction of $3$-vertex rigid graphs on $|V|\geq 6$
vertices and with $|E|=2|V|+2$ edges, proposed by S.A. Motevallian, C. Yu, and B.D.O. Anderson.
Bibtex entry:
| AUTHOR | = | {Jord{\'a}n, Tibor and Huang, Robin and Simmons, Henry and Weatherspoon, Kaylee and Zheng, Zeyu}, |
| TITLE | = | {Four-regular graphs with extremal rigidity properties}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2022}, |
| NUMBER | = | {TR-2022-13} |