2025/07/31 by Hartosh Singh Bal, Bal, Hartosh Singh · 1 citation
Computer Science · #05C50 #05C69 #05C75 #68Q17 #68R10 #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Constraint Satisfaction and Optimization #FOS: Mathematics #Model-Driven Software Engineering Techniques
paper · pdf · doi:10.48550/arxiv.2507.23231
openalex publication_date 2025/07/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
We study the doubled edge-stage lift \HL'2(G)=L(G⊗ K2), the line graph of the canonical bipartite double cover of a graph \(G\). The natural involution \((u,v)↔(v,u)\) has quotient isomorphic to \(L(G)\), and induces a sector decomposition \Spec(\HL'2(G))=\Spec(L(G))∪\Spec(\mathcal A(G)), where \(\mathcal A(G)\) is a canonical signed refinement of the line graph. Thus the construction retains substantial edge-space information through its quotient and antisymmetric sector. For every input graph, \(\HL'2(G)\) is perfect, claw-free, and box-perfect. In the regular case we give an explicit spectral formula, together with quantitative control of the second eigenvalue and spectral gap for non-bipartite input. Explicit families, including the complete-graph lifts and the Paley lifts, illustrate the theory; in particular, the Paley lifts furnish an explicit family of regular perfect graphs with controlled adjacency spectrum and spectral gap. The construction may be viewed both intrinsically, via ordered-edge adjacency by one-coordinate agreement, and extrinsically, as the line graph of the canonical double cover. The first viewpoint emphasizes the edge-stage nature of the lift, while the second supplies the structural proofs used here.