Bipartite-Splittance Of A Bipartite Graph And Bigraphic Pairs With An A-Connected Realization

A bipartite-split graph is a bipartite graph whose vertex set can be partitioned into a complete bipartite set and an independent set.The bipartite-splittance of an arbitrary bipartite graph is the minimum number of edges to be added or removed in order to produce a bipartite-split graph.In this paper,we show that the bipartite-splittance of a bipartite graph depends only on the degree sequence pair of the bipartite graph,and an easily computable formula for it is derived.As a corollary,a simple characterization of the degree sequence pair of bipartite-split graphs is also given.Let S =(a1,...,am,b1,...,bn),where a1,...,am and b1,...,bn are two nonincreasing sequences of nonnegative integers.The pair S =(a1,...,am;b1,...,bn)is said to be a bigraphic pair if there is a simple bipartite graph G =(X uY,E)such that a1,...,am and b1,...,bn are the degrees of the vertices in X and Y,respectively.Let A be an(additive)Abelian group.We define σ(A,m,n)to be the minimum integer k such that every bigraphic pair S =(a1,...,am;b1,...,bn)with am,bn≥2 and σ(S)= a1 + …+am≥k has an A-connected realization.In this paper,we determine the values of σ(A,m,n)for |A|=k ≥ 5 and m≥n≥2.