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

CREATORJiangdong Ai Bin Chen Ming Chen Tianxiao Zhao
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE21658
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Read the complete text