PreprintCC BY 4.0arXiv
Regular Graphs Without Isomorphic Bisections
Abstract
A graph is bisectable if its vertex set can be split into two sets inducing isomorphic subgraphs. Ando conjectured that every cubic graph is bisectable, and Das, Pokrovskiy, and Sudakov proved it for large enough connected cubic graphs. We give a constructive proof that, for every d≥5, there exists a non-bisectable d-regular graph of even order.
Related
- Circular flows and bisections of random regular graphs
- Exact extremizers for ℓp-judicious bisections of triangle-free graphs
- Sharp lower bounds for bisections of graphs with bounded maximum degree
- A study on Type-2 isomorphic circulant graphs. Part 3: 384 pairs of Type-2 isomorphic circulant graphs C32(R)
- A study on Type-2 isomorphic circulant graphs. Part 4: 960 triples of Type-2 isomorphic circulant graphs C54(R)
BibTeX
@misc{feinsilber2026regular,
title = {{Regular Graphs Without Isomorphic Bisections}},
author = {Elie Feinsilber},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.35274},
eprint = {2610.35274},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.35274},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Regular Graphs Without Isomorphic Bisections
AU - Elie Feinsilber
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.35274
UR - https://arxiv.org/abs/2610.35274
AB - A graph is bisectable if its vertex set can be split into two sets inducing isomorphic subgraphs. Ando conjectured that every cubic graph is bisectable, and Das, Pokrovskiy, and Sudakov proved it for large enough connected cubic graphs. We give a constructive proof that, for every d≥5, there exists a non-bisectable d-regular graph of even order.
ER -