Spanning Rigid Subgraph Packing and Sparse Subgraph Covering

DOI10.1137/17M1134196MaRDI QIDQ4568066zbMATH OpenOpenAlexWikidataFDO

Authors Xiaofeng Gu

Publication date 15 June 2018

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.0247

zbMATH Keywords

coveringpackingrigid graphspanning treesparse graph

Mathematics Subject Classification ID

Trees (05C05) Density (toughness, etc.) (05C42) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Rigidity, arising in discrete geometry, is the property of a structure that does not flex. Laman provides a combinatorial characterization of rigid graphs in the Euclidean plane, and thus rigid graphs in the Euclidean plane have applications in graph theory. We discover a sufficient partition condition of packing spanning rigid subgraphs and spanning trees. As a corollary, we show that a simple graph $G$ contains a packing of $k$ spanning rigid subgraphs and $l$ spanning trees if $G$ is $(4k+2l)$-edge-connected, and $G-Z$ is essentially $(6k+2l-2k|Z|)$-edge-connected for every $ZsubsetV(G)$. Thus every $(4k+2l)$-connected and essentially $(6k+2l)$-connected graph $G$ contains a packing of $k$ spanning rigid subgraphs and $l$ spanning trees. Utilizing this, we show that every $6$-connected and essentially $8$-connected graph $G$ contains a spanning tree $T$ such that $G-E(T)$ is $2$-connected. These improve some previous results. Sparse subgraph covering problems are also studied.

Recommendations

• Packing of rigid spanning subgraphs and spanning trees
• scientific article; zbMATH DE number 15366
• scientific article; zbMATH DE number 1229732
• Packing spanning graphs from separable families
• Packing strong subgraph in digraphs
• Efficient subgraphs packing
• Packing and Squeezing Subgraphs into Planar Graphs
• Covering a graph with densest subgraphs
• A parameterized algorithm for packing overlapping subgraphs
• On spanning tree packings of highly edge connected graphs

Cites work

• A sufficient connectivity condition for generic rigidity in the plane
• Connected rigidity matroids and unique realizations of graphs
• Decomposing a graph into forests
• Decomposing a graph into forests: the nine dragon tree conjecture is true
• Decomposition of Finite Graphs Into Forests
• Decomposition of sparse graphs into forests and a graph with bounded degree
• Edge-Disjoint Spanning Trees of Finite Graphs
• Fractional arboricity, strength, and principal partitions in graphs and matroids
• Graph theory
• Graphes équilibrés et arboricité rationnelle. (Balanced graphs and rational arboricity)
• scientific article; zbMATH DE number 501471 (Why is no real title available?)
• scientific article; zbMATH DE number 952952 (Why is no real title available?)
• scientific article; zbMATH DE number 3313442 (Why is no real title available?)
• Lehmans switching game and a theorem of Tutte and Nash-Williams
• On Generic Rigidity in the Plane
• On graphs and rigidity of plane skeletal structures
• On the existence of \(k\) edge-disjoint 2-connected spanning subgraphs
• On the Problem of Decomposing a Graph into n Connected Factors
• Packing of rigid spanning subgraphs and spanning trees
• Packing spanning trees and spanning 2-connected \(k\)-edge-connected essentially \((2k-1)\)-edge-connected subgraphs
• The 2-dimensional rigidity of certain families of graphs
• The Rigidity of Graphs

Cited in

(9)

• Spectral conditions for graph rigidity in the Euclidean plane
• Extremal graphs for a spectral inequality on edge-disjoint spanning trees
• Graph rigidity for unitarily invariant matrix norms
• Packing spanning trees and spanning 2-connected \(k\)-edge-connected essentially \((2k-1)\)-edge-connected subgraphs
• Packing of rigid spanning subgraphs and spanning trees
• Spectral radius conditions for the rigidity of graphs
• Graph rigidity properties of Ramanujan graphs
• Rigid graphs in cylindrical normed spaces
• Source location with rigidity and tree packing requirements

This page was built for publication: Spanning Rigid Subgraph Packing and Sparse Subgraph Covering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4568066)