具有A-連通實(shí)現(xiàn)二部可圖對(duì)的一個(gè)注記

關(guān)晶欣，尹建華

(海南大學(xué) 信息科學(xué)技術(shù)學(xué)院，海南 ?？?570228)

具有A-連通實(shí)現(xiàn)二部可圖對(duì)的一個(gè)注記

關(guān)晶欣，尹建華

(海南大學(xué) 信息科學(xué)技術(shù)學(xué)院，海南 ?？?570228)

設(shè)S=(a1，…,am；b1，…，bn)，其中a1，…,am和b1,…,bn是2個(gè)非增的非負(fù)整數(shù)序列．如果存在一個(gè)簡(jiǎn)單二部圖G=(X∪Y,E)，使得a1，…，am和b1,…,bn分別是X和Y中頂點(diǎn)的度，則稱S=(a1，…,am;b1,…,bn)為一個(gè)二部可圖對(duì)．設(shè)A是一個(gè)阿貝爾群(以“0”為單位元的加法群),定義σ(A，m,n)是最小的正整數(shù)k使得每一個(gè)二部可圖對(duì)S=(a1,…,am;b1,…,bn)滿足am,bn≥2且σ(S)=a1+…+am≥k時(shí)都有一個(gè)A-連通實(shí)現(xiàn)，確定了當(dāng)|A|=4且m≥n≥3時(shí)，σ(A,m,n)的下界和當(dāng)|A|=6且m≥n≥2時(shí)，σ(A,m,n)的下界．

二部可圖對(duì)； A-連通實(shí)現(xiàn)； 群連通

猜想1[2]每個(gè)5-邊連通圖都是Z3-連通的．

猜想2[2]每個(gè)3-邊連通圖都是Z5-連通的．

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

1 定理2和定理3的證明

為了證明定理2和定理3，需要以下引理．

引理1 設(shè)A是一個(gè)阿貝爾群．則

2)[7]如果|A|=4，則當(dāng)s≥t≥3時(shí)，Ks,t是A-連通的且當(dāng)s≥2時(shí)，Ks,2不是A-連通的．

3)[2]一個(gè)連通圖是A-連通的當(dāng)且僅當(dāng)它的每一個(gè)塊是A-連通的．

我是一個(gè)狂熱的雪茄愛(ài)好者，所以古巴必然是我最喜歡的地方之一。我去過(guò)古巴14次，在哈瓦那的感覺(jué)像回家了一樣。我總是帶著高希霸雪茄，和我遇到的人一起分享。有時(shí)我一天能抽5根雪茄，不過(guò)還是不及丘吉爾抽得多。

定理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

國(guó)家自然科學(xué)基金(11561017)；海南省自然科學(xué)基金(2016CXTD004)

關(guān)晶欣(1993-)，女，黑龍江哈爾濱人，海南大學(xué)2015級(jí)碩士研究生，研究方向：圖論及其應(yīng)用，E-mail：15799032340@163.com

尹建華(1970-)，男，湖南祁陽(yáng)人，教授，研究方向：圖論及其應(yīng)用，E-mail：yinjh@hainu.edu.cn

1004-1729(2016)04-0303-04

O 157.5

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