Solution to an Extremal Problem on Bigraphic Pairs with a Z3-connected Realization  

作　　者：Jian Hua YIN Xiang Yu DAI 

机构地区：[1]Department of Mathematics,College of Information Science and Technology,Hainan University,Haikou 570228,P.R.China

出　　处：《Acta Mathematica Sinica,English Series》2017年第8期1131-1153,共23页数学学报（英文版）

基　　金：Supported by National Natural Science Foundation of China(Grant No.11561017);Natural Science Foundation of Hainan Province(Grant No.2016CXTD004)

摘　　要：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 ∪ Y, E） such that a1,…, am and b1,..., bn are the degrees of the vertices in X and Y, respectively. Let Z3 be the cyclic group of order 3. Define σ（Z3, m, n） to be the minimum integer k such that every bigraphic pair S = （a1,..., am; b1,..., bn） with am, b ≥ 2 and σ（S） = a1 ＋ ... ＋ am ≥ k has a Z3-connected realization. For n = m, Yin [Discrete Math., 339, 2018-2026 （2016）] recently determined the values of σ（Z3,m,m） for m ≥ 4. In this paper, we completely determine the values of σ（Z3, m, n） for m ≥ n ≥4.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 ∪ Y, E） such that a1,…, am and b1,..., bn are the degrees of the vertices in X and Y, respectively. Let Z3 be the cyclic group of order 3. Define σ（Z3, m, n） to be the minimum integer k such that every bigraphic pair S = （a1,..., am; b1,..., bn） with am, b ≥ 2 and σ（S） = a1 ＋ ... ＋ am ≥ k has a Z3-connected realization. For n = m, Yin [Discrete Math., 339, 2018-2026 （2016）] recently determined the values of σ（Z3,m,m） for m ≥ 4. In this paper, we completely determine the values of σ（Z3, m, n） for m ≥ n ≥4.

关 键 词：Bigraphic pair Z3-connected realization group connectivity 

分 类 号：O157.5[理学—数学] O156.1[理学—基础数学]