Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2606.02271 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917555607699456 |
|---|---|
| author | Li, Peng Long, Yangjing |
| author_facet | Li, Peng Long, Yangjing |
| contents | Exact \(k\)-leaf powers are graphs whose edges are exactly the pairs of leaves at distance \(k\) in a tree. We prove explicit structure theorems for exact leaf powers on several representative graph families that test different exact-distance phenomena. Our most detailed root-classification theorem concerns chordless cycles: all exact \(5\)-leaf roots of \(C_\ell\), \(\ell\ge 8\), are described by a complete terminal block language. We also prove that the \(t\)-square ladder \(L_t\) is an exact \(5\)-leaf power if and only if \(t\le 2\). In contrast, dense bipartite square structures are often representable: among block-complete multipartite graphs, the exact \(5\)-leaf powers are precisely the bipartite members, and every bipartite co-cluster graph, including every crown \(K_{n,n}-M\), is an exact \(k\)-leaf power for every \(k\ge 5\). Finally, we give parity classifications for complete multipartite graphs and multipartite block graphs at larger exact distances, and isolate a sharp fan boundary at exact distance six. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2606_02271 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Exact Leaf Powers on Cycles, Ladders, Crowns, and Multipartite Block Graphs Li, Peng Long, Yangjing Combinatorics Exact \(k\)-leaf powers are graphs whose edges are exactly the pairs of leaves at distance \(k\) in a tree. We prove explicit structure theorems for exact leaf powers on several representative graph families that test different exact-distance phenomena. Our most detailed root-classification theorem concerns chordless cycles: all exact \(5\)-leaf roots of \(C_\ell\), \(\ell\ge 8\), are described by a complete terminal block language. We also prove that the \(t\)-square ladder \(L_t\) is an exact \(5\)-leaf power if and only if \(t\le 2\). In contrast, dense bipartite square structures are often representable: among block-complete multipartite graphs, the exact \(5\)-leaf powers are precisely the bipartite members, and every bipartite co-cluster graph, including every crown \(K_{n,n}-M\), is an exact \(k\)-leaf power for every \(k\ge 5\). Finally, we give parity classifications for complete multipartite graphs and multipartite block graphs at larger exact distances, and isolate a sharp fan boundary at exact distance six. |
| title | Exact Leaf Powers on Cycles, Ladders, Crowns, and Multipartite Block Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2606.02271 |