Xiaofeng Gu

activity

20142022

most citedA proof of Brouwer's toughness conjecture

22 citations · 40 across the 13 of their papers we have counts for

collaborators

13 papers

math.CO2022

Spanning tree packing and 2-essential edge-connectivity

Xiaofeng Gu, Runrun Liu, Gexin Yu

An edge (vertex) cut $X$ of $G$ is $r$ -essential if $G - X$ has two components each of which has at least $r$ edges. A graph $G$ is $r$ -essentially $k$ -edge-connected (resp. $k$ -conn…

math.CO2022

Spectral radius and edge-disjoint spanning trees

Dandan Fan, Xiaofeng Gu, Huiqiu Lin

The spanning tree packing number of a graph $G$ , denoted by $τ (G)$ , is the maximum number of edge-disjoint spanning trees contained in $G$ . The study of $τ (G)$ is one of the classi…

math.CO2022★ 1 cited

Graph rigidity properties of Ramanujan graphs

Sebastian M. Cioabă, Sean Dewar, Georg Grasegger +1

A recent result of Cioabă, Dewar and Gu implies that any $k$ -regular Ramanujan graph with $k \geq 8$ is globally rigid in $R^{2}$ . In this paper, we extend these results and…

math.CO2022

A unified combinatorial view beyond some spectral properties

Xiaofeng Gu, Muhuo Liu

Let $β > 0$ . Motivated by jumbled graphs defined by Thomason, the celebrated expander mixing lemma and Haemers's vertex separation inequality, we define that a graph $G$ with $n$ ver…

math.CO2021

Sufficient conditions for 2-dimensional global rigidity

Xiaofeng Gu, Wei Meng, Martin Rolek +2

The 2-dimensional global rigidity has been shown to be equivalent to 3-connectedness and redundant rigidity by a combination of two results due to Jackson and Jordán, and Connelly,…

math.CO2021

Graph toughness from Laplacian eigenvalues

Xiaofeng Gu, Willem H. Haemers

The toughness $t (G)$ of a graph $G = (V, E)$ is defined as $t (G) = min {\frac{∣ S ∣}{c ( G - S )}}$ , in which the minimum is taken over all $S \subset V$ such that $G - S$ is disconnected, wher…

math.CO2021

A tight lower bound on the matching number of graphs via Laplacian eigenvalues

Xiaofeng Gu, Muhuo Liu

Let $α^{'}$ and $μ_{i}$ denote the matching number of a non-empty simple graph $G$ with $n$ vertices and the $i$ -th smallest eigenvalue of its Laplacian matrix, respectively. In this pa…

math.CO2020★ 22 cited

A proof of Brouwer's toughness conjecture

Xiaofeng Gu

The toughness $t (G)$ of a connected graph $G$ is defined as $t (G) = min {\frac{∣ S ∣}{c ( G - S )}}$ , in which the minimum is taken over all proper subsets $S \subset V (G)$ such that $c(G-…

math.CO2020

Spectral strengthening of a theorem on transversal critical graphs

Muhuo Liu, Xiaofeng Gu

A transversal set of a graph $G$ is a set of vertices incident to all edges of $G$ . The transversal number of $G$ , denoted by $τ (G)$ , is the minimum cardinality of a transversal se…

math.CO2020★ 4 cited

Spectral conditions for graph rigidity in the Euclidean plane

Sebastian M. Cioabă, Sean Dewar, Xiaofeng Gu

Rigidity is the property of a structure that does not flex. It is well studied in discrete geometry and mechanics, and has applications in material science, engineering and biologi…

math.CO2016★ 1 cited

Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs

Sebastian M. Cioabă, Xiaofeng Gu

In this paper, we present some new results describing connections between the spectrum of a regular graph and its generalized connectivity, toughness, and the existence of spanning…

math.CO2014★ 2 cited

Characterizations of minimal graphs with equal edge connectivity and spanning tree packing number

Xiaofeng Gu, Hong-Jian Lai, Ping Li +1

With graphs considered as natural models for many network design problems, edge connectivity $κ^{'} (G)$ and maximum number of edge-disjoint spanning trees $τ (G)$ of a graph $G$ have b…

math.CO2014★ 10 cited

Spanning rigid subgraph packing and sparse subgraph covering

Xiaofeng Gu

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, a…