具有A-连通实现二部可图对的一个注记

关晶欣，尹建华

(海南大学 信息科学技术学院，海南 海口 570228)

具有A-连通实现二部可图对的一个注记

关晶欣，尹建华

(海南大学 信息科学技术学院，海南 海口 570228)

设S=(a1，…,am；b1，…，bn)，其中a1，…,am和b1,…,bn是2个非增的非负整数序列．如果存在一个简单二部图G=(X∪Y,E)，使得a1，…，am和b1,…,bn分别是X和Y中顶点的度，则称S=(a1，…,am;b1,…,bn)为一个二部可图对．设A是一个阿贝尔群(以“0”为单位元的加法群),定义σ(A，m,n)是最小的正整数k使得每一个二部可图对S=(a1,…,am;b1,…,bn)满足am,bn≥2且σ(S)=a1+…+am≥k时都有一个A-连通实现，确定了当|A|=4且m≥n≥3时，σ(A,m,n)的下界和当|A|=6且m≥n≥2时，σ(A,m,n)的下界．

二部可图对； A-连通实现； 群连通

猜想1[2]每个5-边连通图都是Z3-连通的．

猜想2[2]每个3-边连通图都是Z5-连通的．

定理2若|A|=4且m≥n≥3，则σ(A,m,n)≥2m+n-1．

1 定理2和定理3的证明

为了证明定理2和定理3，需要以下引理．

引理1 设A是一个阿贝尔群．则

2)[7]如果|A|=4，则当s≥t≥3时，Ks,t是A-连通的且当s≥2时，Ks,2不是A-连通的．

3)[2]一个连通图是A-连通的当且仅当它的每一个块是A-连通的．

我是一个狂热的雪茄爱好者，所以古巴必然是我最喜欢的地方之一。我去过古巴14次，在哈瓦那的感觉像回家了一样。我总是带着高希霸雪茄，和我遇到的人一起分享。有时我一天能抽5根雪茄，不过还是不及丘吉尔抽得多。

定理2证毕．

定理3证毕．

[1] Bondy J A,Murty U S R.Graph Theory with Applications[M].New York:American Elsevier, 1976.

[2] Jaeger F, Linial N, Payan C, et al. Group connectivity of graphs-A nonhomogeneous analogue of nowhere zero flow properties[J]. J. Combin. Theory Ser. B, 1992, 56(2): 165-182.

[3] Gale D. A theorem on flows in networks[J]. Pac.J.Math, 1957，7(2): 1 073-1 082.

[4] Ryser H J. Combinatorial properties of matrices of zeros and ones[J]. Canad. J. Math, 1957，9: 371-377.

[5] Yin J H.An extremal problem on bigraphic pairs with an A-connected realization[J]. DiscreteMathematics,2016,339(8):2 018-2 026.

[6] Chen J J,Eschen E,Lai H J. Group connectivity of certain graphs[J]. Ars Combin, 2008, 89(2): 141-158.

[7] Lai H J. Group connectivity of 3-edge-connected chordal graphs[J]. Graphs Combin, 2000,16(2): 165-176.

[8] Luo R, Xu R,Yu G X. An extremal problem on group connectivity of graphs[J]. European J.Combin,2012,33(6):1 078-1 085.

A Note on Bigraphic Pairs with A-connected Realization

Guan Jingxin, Yin Jianhua

(College of Information Science and Technology, Hainan University, Haikou 570228, China)

In the report, let S=(a1，…,am；b1，……，bn)，in which a1，…,bnand b1,…,bnare two nonincreasing sequences of nonnegative integers．If there is a simple bipartite graph G=(X∪Y,E), a1，…，amand b1,…,bnand are the degrees of the vertices in X and Y ，respectively, the pair S=(a1,…,am;b1,…,bn) is a bigraphic pair. Let A be an (additive) Abelian group, σ(A，m,n) was defined to be the minimum integer k , and every bigraphic pair S=(a1,…,am;b1,…,bn) with am,bn≥2 and σ(S)=a1+…,+am≥k has an A-connected realization．When |A|=4 and m≥n≥3 and |A|=6 and m≥n≥2 , the lower bounds of σ(A,m,n) were determined.

bigraphic pairs; A-connected realization; group connectivity

2016-06-17

国家自然科学基金(11561017)；海南省自然科学基金(2016CXTD004)

关晶欣(1993-)，女，黑龙江哈尔滨人，海南大学2015级硕士研究生，研究方向：图论及其应用，E-mail：15799032340@163.com

尹建华(1970-)，男，湖南祁阳人，教授，研究方向：图论及其应用，E-mail：yinjh@hainu.edu.cn

1004-1729(2016)04-0303-04

O 157.5

A DOl：10.15886/j.cnki.hdxbzkb.2016.0045