arXiv Open Access 2017

Asymptotically Almost Every $2r$-regular Graph has an Internal Partition

Nathan Linial Sria Louis

Lihat Sumber

Abstrak

An internal partition of a graph is a partitioning of the vertex set into two parts such that for every vertex, at least half of its neighbors are on its side. We prove that for every positive integer $r$, asymptotically almost every $2r$-regular graph has an internal partition.

Topik & Kata Kunci

math.CO

Penulis (2)

Nathan Linial

Sria Louis

Format Sitasi

APA MLA BibTeX

Linial, N., Louis, S. (2017). Asymptotically Almost Every $2r$-regular Graph has an Internal Partition. https://arxiv.org/abs/1708.04162

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2017
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓