Source author record

Xiaofeng Gu

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics math.GT

Catalog footprint

Research overview

6works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

A unified combinatorial view beyond some spectral properties

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$ vertices is a weakly $(n,β)$ -graph if $\frac{|X| |Y|}{(n-|X|)(n-|Y|)} \le β^2$ holds for every pair of disjoint proper subsets $X, Y$ of $V(G)$ with no edge between $X$ and $Y$ , and it is an $(n,β)$ -graph if in addition $X$ and $Y$ are not necessarily disjoint. Our main results include the following. (i) For any weakly $(n,β)$ -graph $G$ , the matching number $α'(G)\ge \min\left\{\frac{1-β}{1+β},\, \frac{1}{2}\right\}\cdot (n-1).$ If in addition $G$ is a $(U, W)$ -bipartite graph with $|W|\ge t|U|$ where $t\ge 1$ , then $α'(G)\ge \min\{t(1-2β^2),1\}\cdot |U|$ . (ii) For any $(n,β)$ -graph $G$ , $α'(G)\ge \min\left\{\frac{2-β}{2(1+β)},\, \frac{1}{2}\right\}\cdot (n-1).$ If in addition $G$ is a $(U, W)$ -bipartite graph with $|W|\ge |U|$ and no isolated vertices, then $α'(G)\ge \min\{1/β^{2},1\}\cdot |U|$ . (iii) If $G$ is a weakly $(n,β)$ -graph for $0<β\le 1/3$ or an $(n,β)$ -graph for $0<β\le 1/2$ , then $G$ has a fractional perfect matching. In addition, $G$ has a perfect matching when $n$ is even and $G$ is factor-critical when $n$ is odd. (iv) For any connected $(n,β)$ -graph $G$ , the toughness $t(G)\ge \frac{1-β}β$ . For any connected weakly $(n,β)$ -graph $G$ , $t(G)> \frac{5(1-β)}{11β}$ and if $n$ is large enough, then $t(G) >\left(\frac{1}{2}-\varepsilon\right)\frac{1-β}β$ for any $\varepsilon >0$ .

preprint2022arXiv

Spanning tree packing and 2-essential edge-connectivity

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$ -connected) if it has no $r$ -essential edge (resp. vertex) cuts of size less than $k$ . If $r=1$ , we simply call it essential. Recently, Lai and Li proved that every $m$ -edge-connected essentially $h$ -edge-connected graph contains $k$ edge-disjoint spanning trees, where $k,m,h$ are positive integers such that $k+1\le m\le 2k-1$ and $h\ge \frac{m^2}{m-k}-2$ . In this paper, we show that every $m$ -edge-connected and $2$ -essentially $h$ -edge-connected graph that is not a $K_5$ or a fat-triangle with multiplicity less than $k$ has $k$ edge-disjoint spanning trees, where $k+1\le m\le 2k-1$ and $h\ge f(m,k)=\begin{cases} 2m+k-4+\frac{k(2k-1)}{2m-2k-1}, & m< k+\frac{1+\sqrt{8k+1}}{4}, \\ m+3k-4+\frac{k^2}{m-k}, & m\ge k+\frac{1+\sqrt{8k+1}}{4}. \end{cases}$ Extending Zhan's result, we also prove that every 3-edge-connected essentially 5-edge-connected and $2$ -essentially 8-edge-connected graph has two edge-disjoint spanning trees. As an application, this gives a new sufficient condition for Hamilton-connectedness of line graphs. In 2012, Kaiser and Vrána proved that every 5-connected line graph of minimum degree at least 6 is Hamilton-connected. We allow graphs to have minimum degree 5 and prove that every 5-connected essentially 8-connected line graph is Hamilton-connected.

preprint2022arXiv

Spectral radius and edge-disjoint spanning trees

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 classic problems in graph theory. Cioabă and Wong initiated to investigate $τ(G)$ from spectral perspectives in 2012 and since then, $τ(G)$ has been well studied using the second largest eigenvalue of the adjacency matrix in the past decade. In this paper, we further extend the results in terms of the number of edges and the spectral radius, respectively; and prove tight sufficient conditions to guarantee $τ(G)\geq k$ with extremal graphs characterized. Moreover, we confirm a conjecture of Ning, Lu and Wang on characterizing graphs with the maximum spectral radius among all graphs with a given order as well as fixed minimum degree and fixed edge connectivity. Our results have important applications in rigidity and nowhere-zero flows. We conclude with some open problems in the end.

preprint2021arXiv

Spectral conditions for graph rigidity in the Euclidean plane

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 biological sciences. A bar-and-joint framework is a pair $(G,p)$ of graph $G$ together with a map $p$ of the vertices of $G$ into the Euclidean plane. We view the edges of $(G, p)$ as bars and the vertices as universal joints. The vertices can move continuously as long as the distances between pairs of adjacent vertices are preserved. The framework is rigid if any such motion preserves the distances between all pairs of vertices. In 1970, Laman obtained a combinatorial characterization of rigid graphs in the Euclidean plane. In 1982, Lovász and Yemini discovered a new characterization and proved that every $6$ -connected graph is rigid. Combined with a characterization of global rigidity, their proof actually implies that every 6-connected graph is globally rigid. Consequently, if Fiedler's algebraic connectivity is greater than 5, then $G$ is globally rigid. In this paper, we improve this bound and show that for a graph $G$ with minimum degree $δ\geq 6$ , if its algebraic connectivity is greater than $2+\frac{1}{δ-1}$ , then $G$ is rigid and if its algebraic connectivity is greater than $2+\frac{2}{δ-1}$ , then $G$ is globally rigid. Our results imply that every connected regular Ramanujan graph with degree at least $8$ is globally rigid. We also prove a more general result giving a sufficient spectral condition for the existence of $k$ edge-disjoint spanning rigid subgraphs. The same condition implies that a graph contains $k$ edge-disjoint spanning $2$ -connected subgraphs. This result extends previous spectral conditions for packing edge-disjoint spanning trees.

preprint2016arXiv

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

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 trees with bounded degree.

preprint2014arXiv

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

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 been used as measures for reliability and strength in communication networks modeled as graph $G$ (see \cite{Cunn85, Matula87}, among others). Mader \cite{Mader71} and Matula \cite{Matula72} introduced the maximum subgraph edge connectivity $\overline{κ'}(G)=\max \{κ'(H): H \mbox{ is a subgraph of } G \}$. Motivated by their applications in network design and by the established inequalities $\overline{κ'}(G)\ge κ'(G) \ge τ(G),$ we present the following in this paper: (i) For each integer $k>0$ , a characterization for graphs $G$ with the property that $\overline{κ'}(G) \le k$ but for any edge $e$ not in $G$ , $\overline{κ'}(G+e)\ge k+1$ . (ii) For any integer $n > 0$ , a characterization for graphs $G$ with $|V(G)| = n$ such that $κ'(G) = τ(G)$ with $|E(G)|$ minimized.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Xiaofeng Gu

Research overview

Is this your work?

6 publications

A unified combinatorial view beyond some spectral properties

Spanning tree packing and 2-essential edge-connectivity

Spectral radius and edge-disjoint spanning trees

Spectral conditions for graph rigidity in the Euclidean plane

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

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

See the researcher in context

Building this map preview