JZJunxue Zhang
Junxue Zhang
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Junxue Zhang has a total of 15 co-authors. Here are the top co-authors by number of shared publications:
- Bin Wang
School of Mathematics and Statistics, Beijing Institute of Technology, Beijing, China
1 shared publication Changxin Wang
Center for Combinatorics and LPMC Nankai University 300071 Tianjin China
1 shared publication- Changxin Wang
Nankai Univ, Ctr Combinator & LPMC, Tianjin 300071, Peoples R China
1 shared publication - Eckhard Steffen
Department of Mathematics, Paderborn University, Paderborn, Germany
1 shared publication - Hui Lei
School of Statistics and Data Science, LPMC and KLMDASR Nankai University Tianjin China
1 shared publication - Isaak H. Wolf
Department of Mathematics, Paderborn University, Paderborn, Germany
1 shared publication
Latest Publications
- Open Access
The minimum spectral radius of $tP_4$-saturated graphs
A graph $G$ is called {\em$F$-saturated} if $G$ does not contain $F$ as a subgraph but adding any missing edge to $G$ creates a copy of $F$. In this paper, we consider the spectral saturation problem for the linear forest $tP_4$, proving that every $n$-vertex $tP_4$-saturated graph $G$ with $t\geq 2$ and $n\ge 4t$ satisfies $ρ(G)\ge \frac{1+\sqrt{17}}{2}$, and characterizing all $tP_4$-saturated graphs for which equality holds. Moreover, we obtain that, for $t=2$ with odd $n\ge 13 $, and for $t\ge 3$ with $n\ge 6t+4$, the set of $n$-vertex $tP_4$-saturated graphs minimizing the spectral radius is disjoint from that minimizing the number of edges.Open AccessThe minimum spectral radius of $tP_4$-saturated graphs
A graph $G$ is called {\em$F$-saturated} if $G$ does not contain $F$ as a subgraph but adding any missing edge to $G$ creates a copy of $F$. In this paper, we consider the spectral saturation problem for the linear forest $tP_4$, proving that every $n$-vertex $tP_4$-saturated graph $G$ with $t\geq 2$ and $n\ge 4t$ satisfies $ρ(G)\ge \frac{1+\sqrt{17}}{2}$, and characterizing all $tP_4$-saturated graphs for which equality holds. Moreover, we obtain that, for $t=2$ with odd $n\ge 13 $, and for $t\ge 3$ with $n\ge 6t+4$, the set of $n$-vertex $tP_4$-saturated graphs minimizing the spectral radius is disjoint from that minimizing the number of edges. - Open Access
Perturbation of dense graphs
In the past two decades, various properties of randomly perturbed/augmented (hyper)graphs have been intensively studied, since the model was introduced by Bohman, Frieze and Martin in 2003. The model usually considers a deterministic graph $G$ with minimum degree condition, perturbed/augmented by a binomial random graph $G(n,p)$ on the same vertex set. In this paper, we show that for many problems of finding spanning subgraphs, one can indeed relax the minimum degree condition to a density condition. This includes the embedding problem for $F$-factors when $F$ is not a forest, graphs with bounded maximum degree, $r$-th power of $k$-uniform tight Hamilton cycles for $r,k\ge 2$, and $k$-uniform Hamilton $\ell$-cycles for $\ell\in[2,k-1]$. These results strengthen the results of Balogh, Treglown, and Wagner, of Böttcher, Montgomery, Parczyk, and Person, and of Chang, Han and Thoma.Open AccessPerturbation of dense graphs
In the past two decades, various properties of randomly perturbed/augmented (hyper)graphs have been intensively studied, since the model was introduced by Bohman, Frieze and Martin in 2003. The model usually considers a deterministic graph $G$ with minimum degree condition, perturbed/augmented by a binomial random graph $G(n,p)$ on the same vertex set. In this paper, we show that for many problems of finding spanning subgraphs, one can indeed relax the minimum degree condition to a density condition. This includes the embedding problem for $F$-factors when $F$ is not a forest, graphs with bounded maximum degree, $r$-th power of $k$-uniform tight Hamilton cycles for $r,k\ge 2$, and $k$-uniform Hamilton $\ell$-cycles for $\ell\in[2,k-1]$. These results strengthen the results of Balogh, Treglown, and Wagner, of Böttcher, Montgomery, Parczyk, and Person, and of Chang, Han and Thoma. - Open Access
- 17 January 2025
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 32 (1) , P1.30
The Minimum Spectral Radius of $tP_3$- or $K_5$-Saturated Graphs via the Number of $2$-Walks
For a given graph $H$, a graph $G$ is $H$-saturated if $G$ does not contain $H$ as a subgraph, but for $e \in E(\overline{G})$, $G+e$ contains $H$ as a subgraph; the spectral saturation number of $H$, written $sat_{\rho}(n,H)$, is the minimum value of $\rho(G)$ in an $n$-vertex $H$-saturated graph $G$. For a vertex $v \in V(G)$, let $l_2(v)$ be the number of $2$-walks starting from $v$. In this paper, when $G$ is an $n$-vertex $tP_3$- or $K_5$-saturated connected graph, for each vertex $v \in V(G)$, we prove the best lower bounds for $l_2(v)$ in terms of $n$ and $d(v)$, implying that $sat_{\rho}(n,tP_3)=\rho(F)$ and $sat_{\rho}(n,K_5)=\rho(S_{n,4})$, where $F$ is the $6$-vertex graph obtained from $K_3$ by attaching a pendant vertex to each vertex in $K_3$ and $S_{n,4}$ is the join of $K_3$ and $(n-3)K_1$.- 17 January 2025
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 32 (1) , P1.30
Open AccessThe Minimum Spectral Radius of $tP_3$- or $K_5$-Saturated Graphs via the Number of $2$-Walks
For a given graph $H$, a graph $G$ is $H$-saturated if $G$ does not contain $H$ as a subgraph, but for $e \in E(\overline{G})$, $G+e$ contains $H$ as a subgraph; the spectral saturation number of $H$, written $sat_{\rho}(n,H)$, is the minimum value of $\rho(G)$ in an $n$-vertex $H$-saturated graph $G$. For a vertex $v \in V(G)$, let $l_2(v)$ be the number of $2$-walks starting from $v$. In this paper, when $G$ is an $n$-vertex $tP_3$- or $K_5$-saturated connected graph, for each vertex $v \in V(G)$, we prove the best lower bounds for $l_2(v)$ in terms of $n$ and $d(v)$, implying that $sat_{\rho}(n,tP_3)=\rho(F)$ and $sat_{\rho}(n,K_5)=\rho(S_{n,4})$, where $F$ is the $6$-vertex graph obtained from $K_3$ by attaching a pendant vertex to each vertex in $K_3$ and $S_{n,4}$ is the join of $K_3$ and $(n-3)K_1$. - Open Access
Some conjectures on $r$-graphs and equivalences
An $r$-regular graph is an $r$-graph, if every odd set of vertices is connected to its complement by at least $r$ edges. Seymour [On multicolourings of cubic graphs, and conjectures of Fulkerson and Tutte.~\emph{Proc.~London Math.~Soc.}~(3), 38(3): 423-460, 1979] conjectured (1) that every planar $r$-graph is $r$-edge colorable and (2) that every $r$-graph has $2r$ perfect matchings such that every edge is contained in precisely two of them. We study several variants of these conjectures. A $(t,r)$-PM is a multiset of $t \cdot r$ perfect matchings of an $r$-graph $G$ such that every edge is in precisely $t$ of them. We show that the following statements are equivalent for every $t, r \geq 1$: 1. Every planar $r$-graph has a $(t,r)$-PM. 2. Every $K_5$-minor-free $r$-graph has a $(t,r)$-PM. 3. Every $K_{3,3}$-minor-free $r$-graph has a $(t,r)$-PM. 4. Every $r$-graph whose underlying simple graph has crossing number at most $1$ has a $(t,r)$-PM.Open AccessSome conjectures on $r$-graphs and equivalences
An $r$-regular graph is an $r$-graph, if every odd set of vertices is connected to its complement by at least $r$ edges. Seymour [On multicolourings of cubic graphs, and conjectures of Fulkerson and Tutte.~\emph{Proc.~London Math.~Soc.}~(3), 38(3): 423-460, 1979] conjectured (1) that every planar $r$-graph is $r$-edge colorable and (2) that every $r$-graph has $2r$ perfect matchings such that every edge is contained in precisely two of them. We study several variants of these conjectures. A $(t,r)$-PM is a multiset of $t \cdot r$ perfect matchings of an $r$-graph $G$ such that every edge is in precisely $t$ of them. We show that the following statements are equivalent for every $t, r \geq 1$: 1. Every planar $r$-graph has a $(t,r)$-PM. 2. Every $K_5$-minor-free $r$-graph has a $(t,r)$-PM. 3. Every $K_{3,3}$-minor-free $r$-graph has a $(t,r)$-PM. 4. Every $r$-graph whose underlying simple graph has crossing number at most $1$ has a $(t,r)$-PM. - 27 March 2024
- Published by Elsevier in Applied Mathematics and Computation
- Vol. 474
Linear saturation numbers of Berge-C3 and Berge-C4
- 27 March 2024
- Published by Elsevier in Applied Mathematics and Computation
- Vol. 474
Linear saturation numbers of Berge-C3 and Berge-C4
- Open Access
Linear saturation numbers of Berge-$C_3$ and Berge-$C_4$
The linear saturation number $sat^{lin}_k(n,\mathcal{F})$ (linear extremal number $ex^{lin}_k(n,\mathcal{F})$) of $\mathcal{F}$ is the minimum (maximum) number of hyperedges of an $n$-vertex linear $k$-uniform hypergraph containing no member of $\mathcal{F}$ as a subgraph, but the addition of any new hyperedge such that the result hypergraph is still a linear $k$-uniform hypergraph creates a copy of some hypergraph in $\mathcal{F}$. Determining $ex_3^{lin}(n$, Berge-$C_3$) is equivalent to the famous (6,3)-problem, which has been settled in 1976. Since then, determining the linear extremal numbers of Berge cycles was extensively studied. As the counterpart of this problem in saturation problems, the problem of determining the linear saturation numbers of Berge cycles is considered. In this paper, we prove that $sat^{lin}_k$($n$, Berge-$C_t)\ge \big\lfloor\frac{n-1}{k-1}\big\rfloor$ for any integers $k\ge3$, $t\ge 3$, and the equality holds if $t=3$. In addition, we provide an upper bound for $sat^{lin}_3(n,$ Berge-$C_4)$ and for any disconnected Berge-$C_4$-saturated linear 3-uniform hypergraph, we give a lower bound for the number of hyperedges of it.Open AccessLinear saturation numbers of Berge-$C_3$ and Berge-$C_4$
The linear saturation number $sat^{lin}_k(n,\mathcal{F})$ (linear extremal number $ex^{lin}_k(n,\mathcal{F})$) of $\mathcal{F}$ is the minimum (maximum) number of hyperedges of an $n$-vertex linear $k$-uniform hypergraph containing no member of $\mathcal{F}$ as a subgraph, but the addition of any new hyperedge such that the result hypergraph is still a linear $k$-uniform hypergraph creates a copy of some hypergraph in $\mathcal{F}$. Determining $ex_3^{lin}(n$, Berge-$C_3$) is equivalent to the famous (6,3)-problem, which has been settled in 1976. Since then, determining the linear extremal numbers of Berge cycles was extensively studied. As the counterpart of this problem in saturation problems, the problem of determining the linear saturation numbers of Berge cycles is considered. In this paper, we prove that $sat^{lin}_k$($n$, Berge-$C_t)\ge \big\lfloor\frac{n-1}{k-1}\big\rfloor$ for any integers $k\ge3$, $t\ge 3$, and the equality holds if $t=3$. In addition, we provide an upper bound for $sat^{lin}_3(n,$ Berge-$C_4)$ and for any disconnected Berge-$C_4$-saturated linear 3-uniform hypergraph, we give a lower bound for the number of hyperedges of it. - 31 May 2023
- Published by Elsevier in Discrete Mathematics
- Vol. 346 (9)
Extremal numbers of disjoint triangles in r-partite graphs
- 31 May 2023
- Published by Elsevier in Discrete Mathematics
- Vol. 346 (9)
Extremal numbers of disjoint triangles in r-partite graphs
- Open AccessThe saturation number of $K_{3,3}$A graph $G$ is called $F$-saturated if $G$ does not contain $F$ as a subgraph (not necessarily induced) but the addition of any missing edge to $G$ creates a copy of $F$. The saturation number of $F$, denoted by $sat(n,F)$, is the minimum number of edges in an $n$-vertex $F$-saturated graph. Determining the saturation number of complete partite graphs is one of the most important problems in the study of saturation number. The value of $sat(n,K_{2,2})$ was shown to be $\lfloor\frac{3n-5}{2}\rfloor$ by Ollmann, and a shorter proof was later given by Tuza. For $K_{2,3}$, there has been a series of study aiming to determine $sat(n,K_{2,3})$ over the years. This was finally achieved by Chen who confirmed a conjecture of Bohman, Fonoberova, and Pikhurko that $sat(n, K_{2,3})= 2n-3$ for all $n\geq 5$. In this paper, we prove a conjecture of Pikhurko and Schmitt that $sat(n, K_{3,3})=3n-9$ when $n \geq 9$.Open AccessThe saturation number of $K_{3,3}$A graph $G$ is called $F$-saturated if $G$ does not contain $F$ as a subgraph (not necessarily induced) but the addition of any missing edge to $G$ creates a copy of $F$. The saturation number of $F$, denoted by $sat(n,F)$, is the minimum number of edges in an $n$-vertex $F$-saturated graph. Determining the saturation number of complete partite graphs is one of the most important problems in the study of saturation number. The value of $sat(n,K_{2,2})$ was shown to be $\lfloor\frac{3n-5}{2}\rfloor$ by Ollmann, and a shorter proof was later given by Tuza. For $K_{2,3}$, there has been a series of study aiming to determine $sat(n,K_{2,3})$ over the years. This was finally achieved by Chen who confirmed a conjecture of Bohman, Fonoberova, and Pikhurko that $sat(n, K_{2,3})= 2n-3$ for all $n\geq 5$. In this paper, we prove a conjecture of Pikhurko and Schmitt that $sat(n, K_{3,3})=3n-9$ when $n \geq 9$.