Hongliang Lu

AcademiClaw: When Students Set Challenges for AI Agents

Benchmarks within the OpenClaw ecosystem have thus far evaluated exclusively assistant-level tasks, leaving the academic-level capabilities of OpenClaw largely unexamined. We introduce AcademiClaw, a bilingual benchmark of 80 complex, long-horizon tasks sourced directly from university students' real academic workflows -- homework, research projects, competitions, and personal projects -- that they found current AI agents unable to solve effectively. Curated from 230 student-submitted candidates through rigorous expert review, the final task set spans 25+ professional domains, ranging from olympiad-level mathematics and linguistics problems to GPU-intensive reinforcement learning and full-stack system debugging, with 16 tasks requiring CUDA GPU execution. Each task executes in an isolated Docker sandbox and is scored on task completion by multi-dimensional rubrics combining six complementary techniques, with an independent five-category safety audit providing additional behavioral analysis. Experiments on six frontier models show that even the best achieves only a 55\% pass rate. Further analysis uncovers sharp capability boundaries across task domains, divergent behavioral strategies among models, and a disconnect between token consumption and output quality, providing fine-grained diagnostic signals beyond what aggregate metrics reveal. We hope that AcademiClaw and its open-sourced data and code can serve as a useful resource for the OpenClaw community, driving progress toward agents that are more capable and versatile across the full breadth of real-world academic demands. All data and code are available at https://github.com/GAIR-NLP/AcademiClaw.

Accelerating Rectified Flow Models via Trajectory-Aware Caching

Diffusion and rectified flow (RF) models generate high-fidelity images and videos, but their iterative velocity-field evaluations are computationally expensive. Existing caching methods accelerate sampling by skipping timesteps, yet their coarse approximations introduce accumulated errors over long skip intervals and degrade quality under aggressive acceleration. We propose TACache (Trajectory-Aware Cache), a training-free acceleration framework following a skip-then-compensate paradigm. TACache performs an orthogonal decomposition of discrete velocity acceleration along the RF trajectory into a parallel component and an orthogonal residual, isolating the magnitude and directional sources of per-step approximation error. The framework operates in two stages: offline, cumulative variation thresholds on the magnitude and direction indicators yield the skip schedule and bound how far each skip interval may extend; online, at each skipped step the offline statistics are combined with the sample's historical orthogonal direction to reconstruct the skipped velocity without additional model evaluations. Experiments on BAGEL, FLUX.1-dev, and Wan2.1-1.3B show that TACache achieves up to 4.14 speedup on text-to-image generation and 2.11 speedup on text-to-video generation, with consistent improvements over prior cache-based methods on all reference-based fidelity metrics. Code will be released soon.

Coordinated Pandemic Control with Large Language Model Agents as Policymaking Assistants

Effective pandemic control requires timely and coordinated policymaking across administrative regions that are intrinsically interdependent. However, human-driven responses are often fragmented and reactive, with policies formulated in isolation and adjusted only after outbreaks escalate, undermining proactive intervention and global pandemic mitigation. To address this challenge, here we propose a large language model (LLM) multi-agent policymaking framework that supports coordinated and proactive pandemic control across regions. Within our framework, each administrative region is assigned an LLM agent as an AI policymaking assistant. The agent reasons over region-specific epidemiological dynamics while communicating with other agents to account for cross-regional interdependencies. By integrating real-world data, a pandemic evolution simulator, and structured inter-agent communication, our framework enables agents to jointly explore counterfactual intervention scenarios and synthesize coordinated policy decisions through a closed-loop simulation process. We validate the proposed framework using state-level COVID-19 data from the United States between April and December 2020, together with real-world mobility records and observed policy interventions. Compared with real-world pandemic outcomes, our approach reduces cumulative infections and deaths by up to 63.7% and 40.1%, respectively, at the individual state level, and by 39.0% and 27.0%, respectively, when aggregated across states. These results demonstrate that LLM multi-agent systems can enable more effective pandemic control with coordinated policymaking...

The Great March 100: 100 Detail-oriented Tasks for Evaluating Embodied AI Agents

Recently, with the rapid development of robot learning and imitation learning, numerous datasets and methods have emerged. However, these datasets and their task designs often lack systematic consideration and principles. This raises important questions: Do the current datasets and task designs truly advance the capabilities of robotic agents? Do evaluations on a few common tasks accurately reflect the differentiated performance of various methods proposed by different teams and evaluated on different tasks? To address these issues, we introduce the Great March 100 (\textbf{GM-100}) as the first step towards a robot learning Olympics. GM-100 consists of 100 carefully designed tasks that cover a wide range of interactions and long-tail behaviors, aiming to provide a diverse and challenging set of tasks to comprehensively evaluate the capabilities of robotic agents and promote diversity and complexity in robot dataset task designs. These tasks are developed through systematic analysis and expansion of existing task designs, combined with insights from human-object interaction primitives and object affordances. We collect a large amount of trajectory data on different robotic platforms and evaluate several baseline models. Experimental results demonstrate that the GM-100 tasks are 1) feasible to execute and 2) sufficiently challenging to effectively differentiate the performance of current VLA models. Our data and code are available at https://rhos.ai/research/gm-100.

preprint2025arXiv

Active Sensing Shapes Real-World Decision-Making through Dynamic Evidence Accumulation

Human decision-making heavily relies on active sensing, a well-documented cognitive behaviour for evidence gathering to accommodate ever-changing environments. However, its operational mechanism in the real world remains non-trivial. Currently, an in-laboratory paradigm, called evidence accumulation modelling (EAM), points out that human decision-making involves transforming external evidence into internal mental beliefs. However, the gap in evidence affordance between real-world contexts and laboratory settings hinders the effective application of EAM. Here we generalize EAM to the real world and conduct analysis in real-world driving scenarios. A cognitive scheme is proposed to formalize real-world evidence affordance and capture active sensing through eye movements. Empirically, our scheme can plausibly portray the accumulation of drivers' mental beliefs, explaining how active sensing transforms evidence into mental beliefs from the perspective of information utility. Also, our results demonstrate a negative correlation between evidence affordance and attention recruited by individuals, revealing how human drivers adapt their evidence-collection patterns across various contexts. Moreover, we reveal the positive influence of evidence affordance and attention distribution on decision-making propensity. In a nutshell, our computational scheme generalizes EAM to real-world contexts and provides a comprehensive account of how active sensing underlies real-world decision-making, unveiling multifactorial, integrated characteristics in real-world decision-making.

preprint2025arXiv

Automating Traffic Model Enhancement with AI Research Agent

Developing efficient traffic models is crucial for optimizing modern transportation systems. However, current modeling approaches remain labor-intensive and prone to human errors due to their dependence on manual workflows. These processes typically involve extensive literature reviews, formula tuning, and iterative testing, which often lead to inefficiencies. To address this, we propose TR-Agent, an AI-powered framework that autonomously develops and refines traffic models through a closed-loop, iterative process. We structure the research pipeline into four key stages: idea generation, theory formulation, theory evaluation, and iterative optimization, and implement TR-Agent with four corresponding modules. These modules collaborate to retrieve knowledge from external sources, generate novel hypotheses, implement and debug models, and evaluate their performance on evaluation datasets. Through iteratively feedback and refinement, TR-Agent improves both modeling efficiency and effectiveness. We validate the framework on three representative traffic models: the Intelligent Driver Model (IDM) for car-following behavior, the MOBIL model for lane-changing, and the Lighthill-Whitham-Richards (LWR) speed-density relationship for macroscopic traffic flow modeling. Experimental results show substantial performance gains over the original models. To assess the robustness and generalizability of the improvements, we conduct additional evaluations across multiple real-world datasets, demonstrating consistent performance gains beyond the original development data. Furthermore, TR-Agent produces interpretable explanations for each improvement, enabling researchers to easily verify and extend its results. This makes TR-Agent a valuable assistant for traffic modeling refinement and a promising tool for broader applications in transportation research.

preprint2023arXiv

A proof of Frankl-Kupavskii's conjecture on edge-union condition

A 3-graph $\mathcal{F}$ is \emph{ $U(s, 2s+1)$ } if for any $s$ edges $e_1,...,e_s\in E(\mathcal{F})$ , $|e_1\cup...\cup e_s|\leq 2s+1$ . Frankl and Kupavskii (2020) proposed the following conjecture: For any $3$ -graph $\mathcal{F}$ with $n$ vertices, if $\mathcal{F}$ is $U(s, 2s+1)$ , then $e(\mathcal{F})\leq \max\left\{{n-1\choose 2}, (n-s-1){s+1\choose 2}+{s+1\choose 3}, {2s+1\choose 3}\right\}.$ In this paper, we confirm Frankl and Kupavskii's conjecture.

preprint2022arXiv

Spectral radius and rainbow matchings of graphs

Let $n,m$ be integers such that $1\leq m\leq (n-2)/2$ and let $[n]=\{1,\ldots,n\}$ . Let $\mathcal{G}=\{G_1,\ldots,G_{m+1}\}$ be a family of graphs on the same vertex set $[n]$ . In this paper, we prove that if for any $i\in [m+1]$ , the spectral radius of $G_i$ is not less than $\max\{2m,\frac{1}{2}(m-1+\sqrt{(m-1)^2+4m(n-m)})\}$ , then $\mathcal{G}$ admits a rainbow matching, i.e. a choice of disjoint edges $e_i\in G_i$ , unless $G_1=G_2=\ldots=G_{m+1}$ and $G_1\in \{K_{2m+1}\cup (n-2m-1)K_1, K_m\vee (n-m)K_1\}$ .

preprint2022arXiv

Toughness, hamiltonicity and spectral radius in graphs

The study of the existence of hamiltonian cycles in a graph is a classic problem in graph theory. By incorporating toughness and spectral conditions, we can consider Chvátal's conjecture from another perspective: what is the spectral condition to guarantee the existence of a hamiltonian cycle among $t$ -tough graphs? We first give the answer to $1$ -tough graphs, i.e. if $ρ(G)\geqρ(M_{n})$ , then $G$ contains a hamiltonian cycle, unless $G\cong M_{n}$ , where $M_{n}=K_{1}\nabla K_{n-4}^{+3}$ and $K_{n-4}^{+3}$ is the graph obtained from $3K_{1}\cup K_{n-4}$ by adding three independent edges between $3K_{1}$ and $K_{n-4}$ . The Brouwer's toughness theorem states that every $d$ -regular connected graph always has $t(G)>\frac{d}λ-1$ where $λ$ is the second largest absolute eigenvalue of the adjacency matrix. In this paper, we extend the result in terms of its spectral radius, i.e. we provide a spectral condition for a graph to be 1-tough with minimum degree $δ$ and to be $t$ -tough, respectively.

preprint2021arXiv

A better bound on the size of rainbow matchings

Aharoni and Howard conjectured that, for positive integers $n,k,t$ with $n\ge k$ and $n\ge t$ , if $F_1,\ldots, F_t\subseteq {[n]\choose k}$ such that $|F_i|>{n\choose k}-{n-t+1\choose k}$ for $i\in [t]$ then there exist $e_i\in F_i$ for $i\in [t]$ such that $e_1,\ldots,e_t$ are pairwise disjoint. Huang, Loh, and Sudakov proved this conjecture for $t<n/(3k^2)$ . In this paper, we show that this conjecture holds for $t\le n/(2k)$ and $n$ sufficiently large.

A Degree Condition for Graphs Having All $(a,b)$ -Parity Factors

Let $a$ and $b$ be positive integers such that $a\leq b$ and $a\equiv b\pmod 2$ . We say that $G$ has all $(a, b)$ -parity factors if $G$ has an $h$ -factor for every function $h: V(G) \rightarrow \{a,a+2,\ldots,b-2,b\}$ with $b|V(G)|$ even and $h(v)\equiv b\pmod 2$ for all $v\in V(G)$ . In this paper, we prove that every graph $G$ with $n\geq 3(b+1)(a+b)$ vertices has all $(a,b)$ -parity factors if $δ(G)\geq (b^2-b)/a$ , and for any two nonadjacent vertices $u,v \in V(G)$ , $\max\{d_G(u),d_G(v)\}\geq \frac{bn}{a+b}$ . Moreover, we show that this result is best possible in some sense.

An Ore-type Condition for Large $k$ -factor and Disjoint Perfect Matchings

Win [\emph{J. Graph Theory} {\bf 6}(1982), 489--492] conjectured that a graph $G$ on $n$ vertices contains $k$ disjoint perfect matchings, if the degree sum of any two nonadjacent vertices is at least $n+k-2$ , where $n$ is even and $n\geq k+2$ . In this paper, we prove that Win's conjecture is true for $k\geq n/2$ , where $n$ is sufficiently large. To show this result, we prove a theorem on $k$ -factor in a graph under some Ore-type condition. Our main tools include Tutte's $k$ -factor theorem, the Karush-Kuhn-Tucker theorem on convex optimization, and the solution to the longstanding 1-factor decomposition conjecture.

Rainbow matchings for 3-uniform hypergraphs

Kühn, Osthus, and Treglown and, independently, Khan proved that if $H$ is a $3$ -uniform hypergraph with $n$ vertices such that $n\in 3\mathbb{Z}$ and large, and $δ_1(H)>{n-1\choose 2}-{2n/3\choose 2}$ , then $H$ contains a perfect matching. In this paper, we show that for $n\in 3\mathbb{Z}$ sufficiently large, if $F_1, \ldots, F_{n/3}$ are 3-uniform hypergrapghs with a common vertex set and $δ_1(F_i)>{n-1\choose 2}-{2n/3\choose 2}$ for $i\in [n/3]$ , then $\{F_1,\dots, F_{n/3}\}$ admits a rainbow matching, i.e., a matching consisting of one edge from each $F_i$ . This is done by converting the rainbow matching problem to a perfect matching problem in a special class of uniform hypergraphs.

Regular graphs with equal matching number and independence number

Let $r\geq 3$ be an integer and $G$ be a graph. Let $δ(G), Δ(G)$ , $α(G)$ and $μ(G)$ denotes minimum degree, maximum degree, independence number and matching number of $G$ , respectively. Recently, Caro, Davila and Pepper proved $δ(G)α(G)\leq Δ(G)μ(G)$ . Mohr and Rautenbach characterized the extremal graphs for non-regular graphs and 3-regular graphs. In this note, we characterize the extremal graphs for all $r$ -regular graphs in term of Gallai-Edmonds Structure Theorem, which extends Mohr and Rautenbach's result.

preprint2016arXiv

A Degree Condition for a Graph to have $(a,b)$ -Parity Factors

Let $a,b,n$ be three positive integers such that $a\equiv b\pmod 2$ and $n\geq b(a+b)(a+b+2)/(2a)$ . Let $G$ be a graph of order $n$ with minimum degree at least $a+b/a-1$ . We show that $G$ has an $(a,b)$ -parity factor, if $max\{d_G(u),d_G(v)\}\geq \frac{an}{a+b}$ for any two nonadjacent vertices $u,v$ of $G$ . It is an extension of Nishimura's results for the existence of $k$ -factors (\emph{J. Graph Theory}, \textbf{16} (1992), 141--151) and generalizes Li and Cai's result in some senses (\emph{J. Graph Theory}, \textbf{27} (1998), 1--6). These conditions are tight.

preprint2016arXiv

On rainbow matchings for hypergraphs

For any posotive integer $m$ , let $[m]:=\{1,\ldots,m\}$ . Let $n,k,t$ be positive integers. Aharoni and Howard conjectured that if, for $i\in [t]$ , $\mathcal{F}_i\subset[n]^k:= \{(a_1,\ldots,a_k): a_j\in [n] \mbox{ for } j\in [k]\}$ and $|\mathcal{F}_i|>(t-1)n^{k-1}$ , then there exist $M\subseteq [n]^k$ such that $|M|=t$ and $|M\cap \mathcal{F}_i|=1$ for $i\in [t]$ We show that this conjecture holds when $n\geq 3(k-1)(t-1)$ . Let $n, t, k_1\ge k_2\geq \ldots\geq k_t$ be positive integers. Huang, Loh and Sudakov asked for the maximum $Π_{i=1}^t |{\cal R}_i|$ over all ${\cal R}=\{{\cal R}_1, \ldots ,{\cal R}_t\}$ such that each ${\cal R}_i$ is a collection of $k_i$ -subsets of $[n]$ for which there does not exist a collection $M$ of subsets of $[n]$ such that $|M|=t$ and $|M\cap \mathcal{R}_i|=1$ for $i\in [t]$ %and ${\cal R}$ does not admit a rainbow matching. We show that for sufficiently large $n$ with $\sum_{i=1}^t k_i\leq n(1-(4k\ln n/n)^{1/k})$ , $\prod_{i=1}^t |\mathcal{R}_i|\leq {n-1\choose k_1-1}{n-1\choose k_2-1}\prod_{i=3}^{t}{n\choose k_i}$ . This bound is tight.

preprint2015arXiv

A Tutte-type characterization for graph factors

Let $G$ be a connected general graph. Let $f\colon V(G)\to \Z^+$ be a function. We show that $G$ satisfies the Tutte-type condition $o(G-S)\le f(S)\qquad\text{for all vertex subsets $S$},$ if and only if it contains a colored $J_f^*$ -factor for any $2$ -end-coloring, where $J_f^*(v)$ is the union of all odd integers smaller than $f(v)$ and the integer $f(v)$ itself. This is a generalization of the $(1,f)$ -odd factor characterization theorem, and answers a problem of Cui and Kano. We also derive an analogous characterization for graphs of odd orders, which addresses a problem of Akiyama and Kano.

preprint2015arXiv

Surface embedding of non-bipartite $k$ -extendable graphs

We find the minimum number $k=μ'(Σ)$ for any surface $Σ$ , such that every $Σ$ -embeddable non-bipartite graph is not $k$ -extendable. In particular, we construct the so-called bow-tie graphs $C_6\bowtie P_n$ , and show that they are $3$ -extendable. This confirms the existence of an infinite number of $3$ -extendable non-bipartite graphs which can be embedded in the Klein bottle.

preprint2015arXiv

The maximum number of perfect matchings of semi-regular graphs

Let $n\ge 34$ be an even integer, and $D_n=2\lceil n/4 \rceil-1$ . In this paper, we prove that every $\{D_n,\,D_n+1\}$ -graph of order $n$ contains $\lceil n/4 \rceil$ disjoint perfect matchings. This result is sharp in the sense that (i) there exists a $\{D_n,\,D_n+1\}$ -graph containing exactly $\lceil n/4 \rceil$ disjoint perfect matchings, and that (ii) there exists a $\{D_n-1,\,D_n\}$ -graph without perfect matchings for each $n$ . As a consequence, for any integer $D\ge D_n$ , every $\{D,\,D+1\}$ -graph of order $n$ contains $\lceil (D+1)/2 \rceil$ disjoint perfect matchings. This extends Csaba et~al.'s breathe-taking result that every $D$ -regular graph of sufficiently large order is $1$ -factorizable, generalizes Zhang and Zhu's result that every $D_n$ -regular graph of order $n$ contains $\lceil n/4 \rceil$ disjoint perfect matchings, and improves Hou's result that for all $k\ge n/2$ , every $\{k,\,k+1\}$ -graph of order $n$ contains $(\lfloor n/3\rfloor+1+k-n/2)$ disjoint perfect matchings.

preprint2014arXiv

Surface embedding of $(n,k)$ -extendable graphs

This paper is concerned with the surface embedding of matching extendable graphs. There are two directions extending the theory of perfect matchings, that is, matching extendability and factor-criticality. In solving a problem posed by Plummer, Dean (The matching extendability of surfaces, J. Combin. Theory Ser. B 54 (1992), 133--141) established the fascinating formula for the minimum number $k= μ(Σ)$ such that every $Σ$ -embeddable graph is not $k$ -extendable. Su and Zhang, Plummer and Zha found the minimum number $n=ρ(Σ)$ such that every $Σ$ -embeddable graph is not $n$ -factor-critical. Based on the notion of $(n,k)$ -graphs which associates these two parameters, we found the formula for the minimum number $k=μ(n,Σ)$ such that every $Σ$ -embeddable graph is not an $(n,k)$ -graph. To access this two-parameter-problem, we consider its dual problem and find out $μ(n,Σ)$ conversely. The same approach works for rediscovering the formula of the number $ρ(Σ)$ .

preprint2013arXiv

A Note On Edge Connectivity and Parity Factor

In this paper, we investigate some parity factors by using Lovász's (g,f)-parity theorem. Let $m>0$ be an integer. Firstly, we obtain a sufficient and necessary condition for some graphs to have a parity factor with restricted minimum degree. Secondly, we obtain some sufficient conditions for a graph to have a parity factor with minimum degree $m$ in term of edge connectivity.

preprint2013arXiv

An Extension of Cui-Kano's Characterization Problem on Graph Factors

Let $G$ be a graph with vertex set $V(G)$ and let $H:V(G)\rightarrow 2^N$ be a set function associating with $G$ . An $H$ -factor of graph $G$ is a spanning subgraphs $F$ such that $d_F(v)\in H(v){4em}\hbox{for every}v\in V(G).$ Let $f:V(G)\rightarrow N$ be an even integer-valued function such that $f\geq 4$ and let $H_f(v)=\{1,3,...,f(v)-1, f(v)\}$ for $v\in V(G)$ . In this paper, we investigate $H_f$ -factors of graphs $G$ by using Lovász's structural descriptions. Let $o(G)$ denote the number of odd components of $G$ . We show that if one of the following conditions holds, then $G$ contains an $H_f$ -factor. [ $(i)$ ] $o(G-S)\leq f(S)$ for all $S\subseteq V(G)$ ; [ $(ii)$ ] $|V(G)|$ is odd, $d_G(v)\geq f(v)-1$ for all $v\in V(G)$ and $o(G-S)\leq f(S)$ for all $\emptyset\neq S\subseteq V(G)$ . As a corollary, we show that if a graph $G$ with odd order and minimum degree $2n-1$ satisfies $o(G-S)\leq 2n|S|{4em}{for all} \emptyset\neq S\subseteq V(G),$ then $G$ contains an $H_n$ -factor. In particular, we make progress on the characterization problem for a special family of graphs proposed by Akiyama and Kano.

preprint2013arXiv

Vertex-Coloring Edge-Weighting of Bipartite Graphs with Two Edge Weights

Let $G$ be a graph and $\mathcal {S}$ be a subset of $Z$ . A vertex-coloring $\mathcal {S}$ -edge-weighting of $G$ is an assignment of weight $s$ by the elements of $\mathcal {S}$ to each edge of $G$ so that adjacent vertices have different sums of incident edges weights. It was proved that every 3-connected bipartite graph admits a vertex-coloring $\{1,2\}$ -edge-weighting (Lu, Yu and Zhang, (2011) \cite{LYZ}). In this paper, we show that the following result: if a 3-edge-connected bipartite graph $G$ with minimum degree $δ$ contains a vertex $u\in V(G)$ such that $d_G(u)=δ$ and $G-u$ is connected, then $G$ admits a vertex-coloring $\mathcal {S}$ -edge-weighting for $\mathcal {S}\in \{\{0,1\},\{1,2\}\}$ . In particular, we show that every 2-connected and 3-edge-connected bipartite graph admits a vertex-coloring $\mathcal {S}$ -edge-weighting for $\mathcal {S}\in \{\{0,1\},\{1,2\}\}$ . The bound is sharp, since there exists a family of infinite bipartite graphs which are 2-connected and do not admit vertex-coloring $\{1,2\}$ -edge-weightings or vertex-coloring $\{0,1\}$ -edge-weightings.

preprint2012arXiv

On the Existence of General Factors in Regular Graphs

Let $G$ be a graph, and $H\colon V(G)\to 2^\mathbb{N}$ a set function associated with $G$ . A spanning subgraph $F$ of $G$ is called an $H$ -factor if the degree of any vertex $v$ in $F$ belongs to the set $H(v)$ . This paper contains two results on the existence of $H$ -factors in regular graphs. First, we construct an $r$ -regular graph without some given $H^*$ -factor. In particular, this gives a negative answer to a problem recently posed by Akbari and Kano. Second, by using Lovász's characterization theorem on the existence of $(g, f)$ -factors, we find a sharp condition for the existence of general $H$ -factors in $\{r, r+1\}$ -graphs, in terms of the maximum and minimum of $H$ . The result reduces to Thomassen's theorem for the case that $H(v)$ consists of the same two consecutive integers for all vertices $v$ , and to Tutte's theorem if the graph is regular in addition.

preprint2012arXiv

Simplified existence theorems on all fractional [a,b]-factors

Let $G$ be a graph with order $n$ and let $g, f : V (G)\rightarrow N$ such that $g(v)\leq f(v)$ for all $v\in V(G)$ . We say that $G$ has all fractional $(g, f)$ -factors if $G$ has a fractional $p$ -factor for every $p: V (G)\rightarrow N$ such that $g(v)\leq p(v)\leq f (v)$ for every $v\in V(G)$ . Let $a<b$ be two positive integers. %and $G$ \textbf{a graph} of order $n$ sufficiently large %for $a$ and $b$ . If $g\equiv a$ , $f\equiv b$ and $G$ has all fractional $(g,f)$ -factors, then we say that $G$ has all fractional $[a,b]$ -factors. Suppose that $n$ is sufficiently large for $a$ and $b$ . This paper contains two results on the existence of all $(g,f)$ -factors of graphs. First, we derive from Anstee's fractional $(g,f)$ -factor theorem a similar characterization for the property of all fractional $(g,f)$ -factors. Second, we show that $G$ has all fractional $[a, b]$ -factors if the minimum degree is at least $\frac{1}{4a}((a+b-1)^2+4b)$ and every pair of nonadjacent vertices has cardinality of the neighborhood union at least $bn/(a + b)$ . These lower bounds are sharp.

A Note on $\{k,n-k\}$ -Factors of Regular Graphs

Let $r$ be an odd integer, and $k$ an even integer. In this note, we present $r$ -regular graphs which have no $\{k,r-k\}$ -factors for all $1\le k\le {r\over2}-1$ . This gives a negative answer to a problem posed by Akbari and Kano recently.

An Alternative Proof of the $H$ -Factor Theorem

Let $H: V(G) \rightarrow 2^{\mathbb{N}}$ be a set mapping for a graph $G$ . Given a spanning subgraph $F$ of $G$ , $F$ is called a {\it general factor} or an $H$ -{\it factor} of $G$ if $d_{F}(x)\in H(x)$ for every vertex $x\in V(G)$ . $H$ -factor problems are, in general, $NP$ -complete problems and imply many well-known factor problems (e.g., perfect matchings, $f$ -factor problems and $(g, f)$ -factor problems) as special cases. Lovász [The factorization of graphs (II), Acta Math. Hungar., 23 (1972), 223--246] gave a structure description and obtained a deficiency formula for $H$ -optimal subgraphs. In this note, we use a generalized alternating path method to give a structural characterization and provide an alternative and shorter proof of Lovász's deficiency formula.

Maximum spectral radius of graphs with given connectivity and minimum degree

Shiu, Chan and Chang [On the spectral radius of graphs with connectivity at most $k$ , J. Math. Chem., 46 (2009), 340-346] studied the spectral radius of graphs of order $n$ with $κ(G) \leq k$ and showed that among those graphs, the maximum spectral radius is obtained uniquely at $K_k^n$ , which is the graph obtained by joining $k$ edges from $k$ vertices of $K_{n-1}$ to an isolated vertex. In this paper, we study the spectral radius of graphs of order $n$ with $κ(G)\leq k$ and minimum degree $δ(G)\geq k$ . We show that among those graphs, the maximum spectral radius is obtained uniquely at $K_{k}+(K_{δ-k+1}\cup K_{n-δ-1})$ .

Note on parity factors of regular graphs

In this paper, we obtain a sufficient condition for the existence of parity factors in a regular graph in terms of edge-connectivity. Moreover, we also show that our condition is sharp.

L-factors and adjacent vertex-distinguishing edge-weighting

An edge weighting problem of a graph G is an assignment of an integer weight to each edge e. Based on edge weighting problem, several types of vertex-coloring problems are put forward. A simple observation illuminates that edge weighting problem has a close relationship with special factors of graphs. In this paper, we obtain several results on the existence of factors with the pre-specified degrees, which generalizes earlier results in [2, 3]. Using these results, we investigate edge-weighting problem. In particular, we prove that every 4-colorable graph admits a vertex-coloring 4-edge-weighting.

On perfect k-matchings

In this paper, we generalize the notions of perfect matchings, perfect 2-matchings to perfect k-matchings and give a necessary and sufficient condition for existence of perfect k-matchings. For bipartite graphs, we show that this k-matching problem is equivalent to that matching question. Moreover, for regular graphs, we provide a sufficient condition of perfect k-matching in terms of edge connectivity.

Regular factors of regular graphs from eigenvalues

Let m and r be two integers. Let G be a connected r-regular graph of order n and k an integer depending on m and r. For even kn, we find a best upper bound (in terms of r and m) on the third largest eigenvalue that is sufficient to guarantee that G has a k-factor. When nk is odd, we give a best upper bound (in terms of r and m) on the second largest eigenvalue that is sufficient to guarantee that G is k-critical.

Vertex-Coloring 2-Edge-Weighting of Graphs

A $k$ -{\it edge-weighting} $w$ of a graph $G$ is an assignment of an integer weight, $w(e)\in \{1,\dots, k\}$ , to each edge $e$ . An edge weighting naturally induces a vertex coloring $c$ by defining $c(u)=\sum_{u\sim e} w(e)$ for every $u \in V(G)$ . A $k$ -edge-weighting of a graph $G$ is \emph{vertex-coloring} if the induced coloring $c$ is proper, i.e., $c(u) \neq c(v)$ for any edge $uv \in E(G)$ . Given a graph $G$ and a vertex coloring $c_0$ , does there exist an edge-weighting such that the induced vertex coloring is $c_0$ ? We investigate this problem by considering edge-weightings defined on an abelian group. It was proved that every 3-colorable graph admits a vertex-coloring $3$ -edge-weighting \cite{KLT}. Does every 2-colorable graph (i.e., bipartite graphs) admit a vertex-coloring 2-edge-weighting? We obtain several simple sufficient conditions for graphs to be vertex-coloring 2-edge-weighting. In particular, we show that 3-connected bipartite graphs admit vertex-coloring 2-edge-weighting.