Abstract | ||
---|---|---|
Let pi = (d(1), d(2), . . . , d(n)) be a graphic sequence of nonnegative integers. A balanced bipartition of pi is a bipartition pi(1) and pi(2) such that - 1 <= vertical bar pi(1)vertical bar - vertical bar pi(2)vertical bar <= 1, where vertical bar pi(i)vertical bar (i = 1, 2) is denoted to the number of elements of pi(i). In this paper, we determine that every k-regular graphic sequence admits a maximum balanced bipartition pi(1), pi(2) which values about left perpendicular n/2 right perpendicular . min{inverted right perpendicular n/2 inverted left perpendicular, k}. We also show that every graphic sequence pi = (d(1), d(2), . . . , d (inverted right perpendicular n/2 inverted left perpendicular), d (inverted right perpendicular n/2 inverted left perpendicular +) (1) , . . ., d(n)) with d (inverted right perpendicular n/2 inverted left perpendicular) >= left perpendicular n/2 right perpendicular has a balanced bipartition no less than Sigma(n)(i) (=) (inverted right perpendicular n/2 inverted left perpendicular +) (1) d(i) if d (inverted right perpendicular n/2 inverted left perpendicular +) (1) <= inverted right perpendicular n/2 inverted left perpendicular - 1 and d(1) - d (inverted right perpendicular n/2 inverted left perpendicular) <= 2. |
Year | Venue | Keywords |
---|---|---|
2018 | ARS COMBINATORIA | graphic sequence,balanced bipartition,lower bound |
Field | DocType | Volume |
Graph,Discrete mathematics,Combinatorics,Degree (graph theory),Mathematics | Journal | 141 |
ISSN | Citations | PageRank |
0381-7032 | 0 | 0.34 |
References | Authors | |
0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Haiyan Li | 1 | 8 | 6.32 |
Jianhua Yin | 2 | 122 | 7.34 |
Jin Guo | 3 | 0 | 1.69 |