段春燕,苗連英(.華中農(nóng)業(yè)大學楚天學院,武漢43005;.中國礦業(yè)大學理學院,江蘇徐州008)

一類極小連通圖的Anti-Ramsey數(shù)

段春燕1,苗連英2
(1.華中農(nóng)業(yè)大學楚天學院,武漢430205;2.中國礦業(yè)大學理學院,江蘇徐州221008)

摘要:給定一個正整數(shù)n和一個圖族F。Kn的邊染色中使得Kn不含有F中任意一個圖的多色圖的最大的顏色數(shù)為F的Anti-Ramsey數(shù),記作AR(n,F)。本文給出了任意一條邊都在三角形中的極小連通圖的Anti-Ramsey數(shù)。

關(guān)鍵詞:Anti-Ramsey數(shù);邊染色;雙邊-p-臨界圖;極小連通圖

0　引言

Anti-Ramsey數(shù)最早由Erd¨os等[1]于20世紀70年代提出并進行了研究。Erd¨os等在Anti-Ramsey理論中,研究了Kn的不含polychromatic子圖的邊染色至多用多少種顏色,即固定n,求k(k是顏色數(shù))。他們提出Anti-Ramsey數(shù)與Tur′an數(shù)非常接近,得出并證明了當n→∞時,

AR(n,H)?ex(n,H)=o(n2)

其中,H={H?e:e∈E(H)}。并利用關(guān)于Tur′an數(shù)漸進性的一個較早的結(jié)論,進而得到當n→∞時,

其中,d+1=m in{χ(H?e):e∈E(H)}。

Anti-Ramsey理論從提出到現(xiàn)在,經(jīng)歷了近40年的時間。在這期間,對于典型圖,如圈、路、星、完全圖等的Anti-Ramsey數(shù)都得到了相關(guān)結(jié)論,已基本解決。本文給出了任意一條邊都在三角形中的極小連通圖的Anti-Ramsey數(shù)。

1　基本符號及定義

本文中所出現(xiàn)的圖均是非空、簡單、無向、有限圖,G?Kn。涉及的符號及說明見表1。

表1　圖的相關(guān)符號Tab.1　The symbolof graph

定義1多色圖:若存在Kn的一個邊染色c,使得G的所有邊都染不同顏色,則稱G是邊染色c下的多色(polychromatic或rainbow)圖。

定義2F-free圖:若G的任一子圖都不屬于圖族F,則稱G是F-free圖。

定義3Anti-Ramsey數(shù):Kn的所有F-free邊染色中所用的最多的顏色數(shù),記為AR(n,F)。圖族F中只有一個圖H時,AR(n,{H})=AR(n,H)。

定義4表示圖:令c是Kn的AR(n,H)-邊染色,若c中的每一種顏色在子圖L中出現(xiàn)且僅出現(xiàn)一次,則子圖L稱為Kn在染色c下的表示圖。

定義5雙邊-p-臨界:對于任意的一個圖族F,Ψ(F?)≥p,若?H ∈F且e1,e2∈E(H)使得χ(H?e1?e2)=p,則稱圖族F是雙邊-p-臨界的。其中F?={H?e:H∈F,e∈E(H)},Ψ(F?)是子色數(shù),

Ψ(F?)=m in{χ(F):F∈F?}?1

定義6 j型:若對于每個n來說,j≥1都是[p]中使得Tnj,p是F-free的最大的數(shù),則稱雙邊-p-臨界圖F有j型。

Jiang等[2]研究了雙邊-p-臨界圖族F的Anti-Ramsey數(shù)。

2　引理

引理1[2]若Kn的一個t(n,p)+j-邊染色c如下:H?Kn且H～=Tnp,H是c下的rainbow圖; E(Kn?H)染不同于E(H)的j種新顏色,使得H的每一部中的邊都染相同顏色,且這j種新顏色中的任意一種至少出現(xiàn)在一部里,則c是F-free染色。

引理2[2]令正整數(shù)p≥2,對于任意一個雙邊-p-臨界有j型的圖族F,都存在一個正整數(shù)n0,使得對于所有的n,n≥n0,都有

AR(n,F)=t(n,p)+j

成立,并且,Kn的所有達到這個界的F-free邊染色都是引理1中所描述的邊染色。

引理3[3]對于正整數(shù)n,k,若n≥k≥4,則有

rb(n,Kk)=ex(n,Kk?1)+2

引理4[4]給定一個正整數(shù)n和一個圖H,有

ex(n,H)≤AR(n,H)≤ex(n,H)

其中,H={H?e:e∈E(H)}。

3　主要結(jié)果

構(gòu)造1令k是一個正整數(shù),且k≥4。下面構(gòu)造k階圖Gk3:

當k是偶數(shù)時,

(1)Gk3只有一個k?1-度點;

(2)Gk3只有一個3-度點;

(3)其余點均為2-度點。

當k是奇數(shù)時,

(1)Gk3只有一個k?1-度點;

(2)其余點均為2-度點。

本文證明了Gk3是任意一條邊都在三角形中的連通圖的一個極小圖,并給出了圖G53的Anti-Ramsey數(shù)。

定理1 Hk={H:H是一個k階連通圖,且H的任意一條邊都在三角形中},則對于所有的正整數(shù)k≥4,Gk3是Hk的一個極小圖。

證明當k是偶數(shù)時,對k用歸納法證明。當k=4時,結(jié)論顯然成立。假設(shè)對于大于4小于k的偶數(shù),結(jié)論均成立。下面,證明結(jié)論對于k也成立。

由構(gòu)造1可知,Gk3至少有兩個相鄰2-度點,設(shè)為u,v。因此,Gk3?u?v只有一個k?3-度點和一個3-度點,其余均為2-度點。根據(jù)假設(shè),Gk3?u?v 是Hk?2的一個極小圖,顯然

e(Gk3)=e(Gk3?u?v)+3

若任意的H∈Hk,則有

e(Gk3)≥e(Gk3?u?v)+3

根據(jù)歸納假設(shè),結(jié)論成立。

當k是奇數(shù)時,同理可證。

定理2若正整數(shù)n,n≥5,則G53是一個雙邊-2-臨界有Type1的圖,

AR(n,G53)=t(n,2)+1

并且,Kn的所有達到這個界的G53-free邊染色都是引理1中所描述的邊染色。

證明定義

G?={G53?e:e∈G53}

則有ψ(G?)=2,且存在兩條邊e1,e2∈E(G53),使得

χ(G53?e1?e2)=2

即G53是一個雙邊-2-臨界圖。顯然,G53有1型。因此,由引理1得

AR(n,G53)≥t(n,2)+1

由引理2,存在正整數(shù)n0,使得對于所有的n, n≥n0,都有

AR(n,G53)=t(n,2)+1

接下來,我們對n運用歸納法證明當5≤n≤n0時,

AR(n,G53)≤t(n,2)+1

若n=5,令V(K5)={u,v,w,x,y}。我們來用反證法證明在E(K5)的任意一個G53-free染色中至多有7種顏色。假設(shè)AR(5,G53)≥8,令c是E(K5)的一個8-染色,圖L是表示圖。因為q(K5)=10, q(L)=8,顯然,可以去掉完全圖K5的兩條邊得到圖L。只需考慮兩種去邊的方法:①去掉一個2K2; ② 去掉一個P3。但是,無論用哪種方法去邊,結(jié)果圖L都含有G53的一個copy。所以,

AR(5,G53)≤7

結(jié)論成立。下面,假設(shè)對于所有大于5,且小于n的正整數(shù),結(jié)論均成立?，F(xiàn)在只需證明結(jié)論對于n也成立。

令c1是E(Kn)的任意一個G53-free AR(n,G53)-染色。如果Kn在染色c1下不含有K4的rainbow copy,則由引理3、引理4可知AR(n,G53)≤t(n,2)+1。如果Kn在染色c1下含有K4的rainbow copy H,令T=V(Kn)V(H)。顯然c1是E(Kn?4)的一個G53-free染色(否則,若Kn?4含有G53的rainbow copy,則Kn必含有G53的rainbow copy,與c1是E(Kn)的G53-free染色矛盾)。由歸納假設(shè),有

AR(n?4,G53)≤t(n?4,2)+1

我們斷定E(H,T)中與KT的同一頂點相關(guān)聯(lián)的邊(定義E(H,T))至多有一種不同于E(H)和E(KT)上的顏色。否則,若c(1),c(2)是兩種不同于E(H) 和E(KT)上的顏色,不妨分別設(shè)c(u1v)=c(1), c(u2v)=c(2),其中v∈V(KT),u1,u2∈V(H),則H+vu1+vu2為G53的rainbow copy,矛盾。因此,

AR(n,G53)≤AR(n?4,G53)+6+(n?4)≤

t(n?4,2)+1+6+(n?4)≤

t(n,2)+1(因為n≥6)

綜上,可得

AR(n,G53)=t(n,2)+1

證畢。

參考文獻:

[1]ERD¨OSP,SIMONOVITSM,S’OSV T.Anti-Ram sey theorems[J].Graphsand Combinatorics,1985,1(1):23-28.

[2]JIANG T,PIKHURKO O.Anti-Ramsey numbers of doubly edge critical graphs[J].Graph Theory,2009,61(3): 210-218.

[3]SCHIERMEYER I.Rainbow numbers formatchings and complete graphs[J].Discrete Mathematics,2004,286(1-2):157-162.

[4]JIANG T.Anti-Ramsey numbers of subdivide graphs[J]. Combin Theory(B),2002,85(2):361-366.

中圖分類號:O157.5

文獻標志碼:A

文章編號:1001-4543(2015)01-0060-03

收稿日期:2015-01-05

通訊作者:段春燕(1984–),女,河北保定人,講師,碩士,主要研究方向為圖論及其應用、組合數(shù)學。電子郵箱duanchunyan339@126.com。

Anti-Ram sey Number of a Minimal Graphs

DUAN Chun-yan1,M IAO Lian-ying2
(1.Chutian College,Huazhong Agricultural University,Wuhan 430205,P.R.China;2.Schoolof Science,China University ofM ining and Technology,Xuzhou 221008,Jiangsu,P.R.China)

Abstract:For given a positive integer n and a family F of graphs,theanti-Ramsey number AR(n,F)denotes themaximum number of colors in an edge-coloring of Knsuch that no subgraph of Knbelonging to F has distinct colors on its edges.The Anti-Ramsey numbersof a special classofgraphsaregiven.

Keywords:Anti-Ramsey number;edge-coloring;doubly edge-p-criticalgraph;m inimalgraph