PreprintarXiv licencearXiv
Optimal connectivity of second order iterated line graphs
Abstract
The line graph L(G) of a graph G is defined to be the simple graph whose vertices are the edges of G, where two vertices in L(G) are adjacent if and only if the corresponding edges in G are incident with a common vertex, and define L2(G)=L(L(G)). For positive integers d and k, the function κL2(d,k) = inf{κ(L2(G)): κ'(G) ≥ k and δ(G) ≥ d} has been investigated. Niepel and Knor proved that κL2(d,1)≥ d−1, for any integer d ≥ 3. In this research, it is proved that if d≥ 3 and k≥ 1, then κL2(d,k)= min{f(d,k), 4d−6}, where f(d,k) = { ll k(d−k), & if $1≤ k≤ ⌊d/2⌋$, kd−k2+2k(⌈ d/2⌉)−(⌈d/2⌉)d, & if $⌊d/2⌋< k <(3d−1)/4$, kd−k2+2k⌊ d/2⌋−2(⌊ d/2⌋)2, & if $(3d−1)/4≤ k<d$, d(⌈ d/2⌉), & if d=k. .nonumber
Related
- Second largest eigenvalue thresholds for the vertex-connectivity of regular graphs
- Monadic second-order logic and the domino problem on self-similar graphs
- Near-Optimal Convex Optimization with Lazy Second-Order Oracles
- On quantitative sufficient second-order optimality conditions for elliptic optimal control problems
- Second-Order Cover Time of Random Regular Graphs
BibTeX
@misc{zou2026optimal,
title = {{Optimal connectivity of second order iterated line graphs}},
author = {Run Zou and Wei Xiong and Mingquan Zhan and Hong-Jian Lai},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.26620},
eprint = {2608.26620},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.26620},
}
RIS
TY - UNPB
TI - Optimal connectivity of second order iterated line graphs
AU - Run Zou
AU - Wei Xiong
AU - Mingquan Zhan
AU - Hong-Jian Lai
PY - 2026
DA - 2026/09/11
PB - arXiv
DO - 10.48550/arxiv.2608.26620
UR - https://arxiv.org/abs/2608.26620
AB - The line graph L(G) of a graph G is defined to be the simple graph whose vertices are the edges of G, where two vertices in L(G) are adjacent if and only if the corresponding edges in G are incident with a common vertex, and define L^2(G)=L(L(G)). For positive integers d and k, the function κ_L^2(d,k) = inf{κ(L^2(G)): κ'(G) ≥ k and δ(G) ≥ d} has been investigated. Niepel and Knor proved that κ_L^2(d,1)≥ d−1, for any integer d ≥ 3. In this research, it is proved that if d≥ 3 and k≥ 1, then κ_L^2(d,k)= min{f(d,k), 4d−6}, where f(d,k) = { ll k(d−k), & if $1≤ k≤ ⌊d/2⌋$, kd−k^2+2k(⌈ d/2⌉)−(⌈d/2⌉)d, & if $⌊d/2⌋< k <(3d−1)/4$, kd−k^2+2k⌊ d/2⌋−2(⌊ d/2⌋)^2, & if $(3d−1)/4≤ k<d$, d(⌈ d/2⌉), & if d=k. .nonumber
ER -