Perfecting the Line Graph
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917414626656256 |
|---|---|
| author | Bal, Hartosh Singh |
| author_facet | Bal, Hartosh Singh |
| contents | We study the doubled edge-stage lift \[ \HL'_2(G)=L(G\otimes K_2), \] the line graph of the canonical bipartite double cover of a graph \(G\). The natural involution \((u,v)\leftrightarrow(v,u)\) has quotient isomorphic to \(L(G)\), and induces a sector decomposition \[ \Spec(\HL'_2(G))=\Spec(L(G))\cup\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_23231 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Perfecting the Line Graph Bal, Hartosh Singh Combinatorics 05C75, 05C50, 05C69, 68Q17, 68R10 We study the doubled edge-stage lift \[ \HL'_2(G)=L(G\otimes K_2), \] the line graph of the canonical bipartite double cover of a graph \(G\). The natural involution \((u,v)\leftrightarrow(v,u)\) has quotient isomorphic to \(L(G)\), and induces a sector decomposition \[ \Spec(\HL'_2(G))=\Spec(L(G))\cup\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. |
| title | Perfecting the Line Graph |
| topic | Combinatorics 05C75, 05C50, 05C69, 68Q17, 68R10 |
| url | https://arxiv.org/abs/2507.23231 |