|Table of Contents|

k-Regular Graphic Degree Sequence Variant of JudiciousBalanced Bipartition Problem of Graphs(PDF)

《南京师大学报（自然科学版）》[ISSN:1001-4616/CN:32-1239/N]

Issue:
2018年02期
Page:
1-
Research Field:
·数学与计算机科学·
Publishing date:

Info

Title:
k-Regular Graphic Degree Sequence Variant of JudiciousBalanced Bipartition Problem of Graphs
Author(s):
Li Haiyan; Guo Jin
College of Information Science and Technology,Hainan University,Haikou 570228,China
Keywords:
graph; degree sequence; k-graphic sequence; balanced bipartition; judicious balanced bipartition
PACS:
O157.5
DOI:
10.3969/j.issn.1001-4616.2018.02.001
Abstract:
Let π=(d1,d2,…,dn) be a graphic sequence of nonnegative integers and π1,π2 be two sequences that are obtained by partitioning the elements of π into two sets. A balanced bipartition of π is a bipartition π1,π2 such that -1≤|π1|-|π2|≤1,where |πi|(i=1,2) denote the number of elements of |πi|. In this paper,let k and n be positive integers,we determine the values ψmax(π) and ψmin(π) of k-regular graphic sequence π=(kn

References:

[1] BONDY J A,MURTY U S R. Graphy theory with applications[M]. NewYork:Macmillan Ltd Press,1976.
[2]GAREY M R,JOHNSON D S,STOCKMEYER L J. Some simplified NP-completet graph proble-ms[J]. Theor Comput Sci,1976,1:237-267.
[3]KARPINSKI M. On approximability of minimum bisection problem[C]//Electronic Colloquium on Computational Complexity. Trier,Germany,2002.
[4]BOLLOBS B,SCOTT A D. Problems and results on judicious partitions[J]. Random Struct and Alg,2002,21:414-430.
[5]BOLLOBS B,SCOTT A D. Judicious partitions of graph[J]. Period Math Hungar,1993,26:125-137.[6]BOLLOBS B,SCOTT A D. Exact bounds for judicious partitions of graphs[J]. Combinatorica,1999,19:73-486.
[7]BOLLOBS B,SCOTT A D. Judicious partitions of bounded-degree graphs[J]. J graph theory,2004,46:131-143.
[8]XU B G,YAN J,YU X X. Balanced judicious bipartitions of graphs[J]. J graph theory,2010,63:210-225.
[9]XU B G,YAN J,YU X X. A note on balanced bipartitions[J]. Discrete Math,2010,310:2613-2617.
[10]XU B G,YU X X. Judicious k-partitions of graphs[J]. J combin theory Ser B,2009,99:324-337.
[11]XU B G,YU X X. Better bounds for k-partitions of graphs[J]. J combin theory Ser B,2009,99:324-337.
[11]XU B G,YU X X. Better bounds for rtitions of graphs[J]. Combinatorics,probability and computing,2011,20:631-640.
[12]XU B G,YU X X. On judicious bisections of graphs[J]. J combin theory Ser B,2014,106:30-69.
[13]ERD?S P,GALLAI T. Graphs with prescribed degrees of vertices[J]. Mat Lapok,1960,11:264-274.
[14]GALE D. A theorem on flows in networks[J]. Pacific J Math,1957,7:1073-1082.
[15]RYSER H J. Combinatorial properties of matrices of zeros and ones[J]. Canad J Math,1957,9:371-377.
[16]YIN J H,LI J S. Two sufficient conditions for a graphic sequence to have a realization with prescribed clique size[J]. Discrete Math,2005,301:218-227.

Memo

Memo:
-
Last Update: 2018-11-06