Open AccessBisection of Hamilton Plane Graphs under Girth Constraints
Author(s) -
Tao Chen
Publication year - 2021
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1769/1/012043
Subject(s) - algorithm , computer science
A bisection of a graph G is a bipartition V 1 and V 2 of V ( G ) such that ‖ V 1 | – | V 2 ‖ ≤ 1. The minimum bisection problem asks for a bisection minimizing e ( V 1 , V 2 ), where e ( V 1 , V 2 ) is the number of edges joining V 1 and V 2 . In this paper, we prove that every Hamilton plane graph G with girth at least 4, | V ( G )|= n , admits a bisection V 1 , V 2 such that e ( V 1 , V 2 ) ≤ n 2 + 1 .