A weighted cycle-localization inequality
Jiangdong Ai Bin Chen Ming Chen Tianxiao Zhao · 2026
Read A weighted cycle-localization inequality by Jiangdong Ai Bin Chen Ming Chen Tianxiao Zhao (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-18536.txt.
Introduction
Ai, Chen, Chen, and Zhao prove a weighted form of a recent cycle inequality for graphs. For each edge, they look at the heaviest cycle that passes through it. If an edge is a bridge, its weight counts twice instead. Summing edge weight over that cycle weight stays below half the vertex count minus one half. The result mirrors a classic global bound at the local level. The authors also describe graph families where equality holds and give conditions that equality requires.
Catalog record
| CREATOR | Jiangdong Ai Bin Chen Ming Chen Tianxiao Zhao |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 21658 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.18536
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A weighted cycle-localization inequality Jiangdong Ai Bin Chen Ming Chen Tianxiao Zhao Abstract In 1959, Erdős and Gallai showed that every 2 2 -connected graph G G contains a cycle of length at least 2 | E ( G ) | | V ( G ) | − 1 \frac{2|E(G)|}{|V(G)|-1} . This result was subsequently extended to weighted graphs by Bondy and Fan in 1991. A natural local variant of this problem arises by considering, for each edge e ∈ E ( G ) e\in E(G) , the quantity c ( e ) c(e) , defined as the length of the longest cycle in G G containing e e (with c ( e ) = 2 c(e)=2 if e e is a bridge). Zhao and Zhang recently proved that for every graph G G on n n vertices satisfies ∑ e ∈ E ( G ) 1 c ( e ) ≤ n − 1 2 . \sum_{e\in E(G)}\frac{1}{c(e)}\leq\frac{n-1}{2}. In this note, we establish a weighted generalization of this inequality. For a weighted graph ( G , w ) (G,w) with positive edge weights, let C w ( e ) C_{w}(e) denote the maximum weight of a cycle containing e e (setting C w ( e ) = 2 w ( e ) C_{w}(e)=2w(e) if e e is a bridge). We prove that ∑ e ∈ E ( G ) w ( e ) C w ( e ) ≤ n − 1 2 . \sum_{e\in E(G)}\frac{w(e)}{C_{w}(e)}\leq\frac{n-1}{2}. Our result can be viewed as a weighted local analogue of the Bondy-Fan theorem, thereby establishing a correspondence between the global and local perspectives. Furthermore, we present a broad class of graphs attaining equality and derive necessary conditions for equality. 1 Introduction Determining the length of the longest cycle is one of the most important lines of research in graph theory. From a global perspective (i.e., the number of edges), Erdős and Gallai [ 3 ] obtained the following result. Theorem 1 ( [ 3 ] ) . Every 2 -edge-connected graph with n vertices and m edges contains a cycle of length at least \frac{2m}{n-1} . Let G be a weighted graph if each of edge e\in E(G) is assigned a nonnegative number \phi(e) . When \phi(e)=1 for each e\in E(G) , G is a simple graph. For any subgraph H\subseteq G , the weight of H is defined by \phi(H)=\sum\limits_{e\in E(H)}\phi(e). In 1991, Bondy and Fan [ 2 ] resolved a conjecture from [ 1 ] , thereby generalizing Theorem 1 to weighted graphs. Concretely, their result reads as follows. Theorem 2 ( [ 2 ] ) . Let G be a 2-edge-connected weighted graph on n vertices. Then G contains a cycle of weight at least \frac{2\phi(G)}{n-1} . In the same paper, Bondy and Fan [ 2 ] further characterized the 2-edge-connected weighted graphs on n vertices that contain no cycle of weight more than \frac{2\phi(G)}{n-1} . The aforementioned two results suggest that a suitably chosen global condition can yield a good lower bound on the length of the longest cycle in graphs. A natural question then arises: Is there a local condition that yields a good lower bound on the length of the longest cycle in graphs? Recently, Zhao and Zhang [ 5 ] introduced a localized perspective for long cycles. For a simple graph G and any e\in E(G) , let c(e) be the length of a longest cycle containing e (and set c(e)=2 if e is a bridge). They provided the following result. Theorem 3 ( [ 5 ] ) . Let G be a graph on n vertices. Then \sum_{e\in E(G)}\frac{1}{c(e)}\leq\frac{n-1}{2}, (1) with equality if and only if G is connected, and each block of G is a clique. Here, we want to remark that Theorem 3 can be viewed as a generalization of Theorem 1 as illustrated by the following inequalities: \sum_{e\in E(G)}\frac{1}{L}\leq\sum_{e\in E(G)}\frac{1}{c(e)}\leq\frac{n-1}{2}\Longrightarrow{\frac{e(G)}{L}\leq\frac{n-1}{2}}\Longrightarrow\frac{2e(G)}{n-1}\leq L, (2) where L is denoted to be the length of the longest cycle in G . Very recently, Li and Ning [ 4 ] observed that ( 1 ) admits an elegant proof by applying Theorem 2 to an auxiliary weighting of the form e\mapsto\frac{1}{c(e)} . This is already a useful viewpoint, but it remains essentially unweighted: the input graph has no edge-weights, and the weighting is introduced only as a proof device. Inspired by Theorems 1 and 2 , it is natural to ask the following question. Question 1 . Can we generalize Theorem 3 to weighted graphs? In our view, the key to this question is how to choose a suitable local parameter for each edge, and such a choice is far from obvious. A natural requirement of this parameter is that the inequality should depend on the given weights w and should localize the heaviest cycle through each edge . This leads to the parameter C_{w}(e) , which means the maximum weight of a cycle containing e . The point is that C_{w}(e) is defined using the same weighting w that we want to control, and it varies edge-by-edge in a highly non-linear way. The central observation of this note is that the self-normalization \phi(e):=\frac{w(e)}{C_{w}(e)} forces every cycle C to satisfy \phi(C)\leq 1 , despite the denominators C_{w}(e) depending on global maximal. This makes the weighted problem tractable and produces a sharp analogue of Theorem 3 . In particular, the weighted equality theory is strictly richer than the unweighted one: even on K_{n} , equality can hold for many non-uniform weightings (see Proposition 8 ). At the same time, equality is not “free”: on K_{r} with r\geq 4 we show that equality forces the original weights themselves to be vertex-induced (see Proposition 15 ). Before stating our main result, we formally introduce several necessary definitions. Throughout, G is a finite simple graph on n vertices and w:E(G)\to\mathbb{R}_{>0} . For a subgraph H\subseteq G , write w(H)=\sum_{e\in E(H)}w(e) . Definition 4 . For any e\in E(G) , let C_{w}(e):=\begin{cases}\max\{w(C):\ C\subseteq G\text{ is a cycle and }e\in E(C)\},&\text{if $e$ lies on a cycle},\\[2.0pt] 2w(e),&\text{if $e$ is a bridge}.\end{cases} Note that C_{w}(e) generalizes c(e) from [ 5 ] by Zhao and Zhang in the sense that the latter corresponds to the special case where w\equiv 1 . Definition 5 . Let K_{r} be a clique on vertex set U . An edge-weighting w on K_{r} is vertex-induced if there exists a function a:U\to\mathbb{R}_{\geq 0} such that w(uv)=\frac{a(u)+a(v)}{2}\qquad\text{for all }uv\in E(K_{r}). (3) In this case, every cycle C\subseteq K_{r} satisfies w(C)=\sum_{v\in V(C)}a(v) . 2 Main theorem Equipped with the former definitions, we are ready to state our main result. As mentioned previously, Theorem 6 is a generalization of Theorem 3 by taking w\equiv 1 . Theorem 6 . Let (G,w) be a connected weighted graph on n vertices, with C_{w}(e) defined as above. Then \sum_{e\in E(G)}\frac{w(e)}{C_{w}(e)}\leq\frac{n-1}{2}. (4) Proof. Define an auxiliary weight function \phi:E(G)\to\mathbb{R}_{>0} by \phi(e):=\frac{w(e)}{C_{w}(e)}. If C is a cycle, then C_{w}(e)\geq w(C) for each e\in E(C) , so \phi(C)=\sum_{e\in E(C)}\frac{w(e)}{C_{w}(e)}\leq\sum_{e\in E(C)}\frac{w(e)}{w(C)}=1. (5) Let B be the set of bridges of G and let H_{1},\dots,H_{k} be the components of G-B . Then each H_{i} is