极大外平面图中树的 Anti-Ramsey 数.pdf

Advances in Applied Mathematics 应用数学进展,2024,13(1),169-175Published Online January 2024 in Hans.https:/www.hanspub.org/journal/aamhttps:/doi.org/10.12677/aam.2024.131020极大外平面图中树的 Anti-Ramsey 数周韦佳周韦佳*，马华玮，马华玮浙江师范大学数学科学学院，浙江 金华收稿日期：2023 年 12 月 17 日；录用日期：2024 年 1 月 11 日；发布日期：2024 年 1 月 17 日摘 要对给定的边染色图 G，如果图 G 的每条边颜色都不一样，则称图 G 是彩虹的。Anti-Ramsey数 AR(K,F)是最大的正整数 k，使得图 K 的任意 k-边染色中，图 K 不包含族F中任意的彩虹图。近些年来，图的 anti-Ramsey 数吸引了很多图论学者的关注，其中平面图中图的 anti-Ramsey 数得到了深入的研究。Jiang 和 West 研究了 k 条边的树在完全图上的 anti-Ramsey数，而 k 条边的树在平面图中的 anti-Ramsey 数的结论不多。在本文中，我们研究了 k 条边的树在极大外平面图中的 anti-Ramsey 数，得到了它的上下界。关键词Anti-Ramsey 数，树，极大外平面图The Anti-Ramsey Number of Trees inMaximal Out-Planar GraphWeijia Zhou,Huawei MaSchool of Mathematical Sciences,Zhejiang Normal University,Jinhua ZhejiangReceived:Dec.17th,2023;accepted:Jan.11th,2024;published:Jan.17th,2024*通讯作者。文章引用:周韦佳,马华玮.极大外平面图中树的 Anti-Ramsey 数 J.应用数学进展,2024,13(1):169-175.DOI:10.12677/aam.2024.131020周韦佳，马华玮AbstractGiven a edge-colored graph G,if each edge of G is unique in color,then the graph G isa rainbow graph.The Anti-Ramsey number AR(K,F)is the largest positive integerk such that in any k-edge-colored graph K,the graph K contains no rainbow graphin the familyF.In recent years,the anti-Ramsey number of graph has attracted theattention of many scholars,and the anti-Ramsey numbers for graphs in planar graphhas been deeply studied.Jiang and West studied the anti-Ramsey number of treeswith k edges in complete graph,while few conclusions were drawn on the anti-Ramseynumber of trees with k edges in planar graph.In this paper,we study the anti-Ramseynumber of trees with k edges in maximal out-planar graph and get its upper and lowerbounds.KeywordsAnti-Ramsey Number,Tree,Maximal Out-Planar GraphCopyright 2024 by author(s)and Hans Publishers Inc.This work is licensed under the Creative Commons Attribution International License(CC BY 4.0).http:/creativecommons.org/licenses/by/4.0/1.引言如果一个边染色图 G 的每一条边的颜色是不同的,那么我们称图 G 是彩虹的.对于给定的图K 和图族F,使得边染色图 G 中不存在族F中的彩虹子图的最大颜色数,定义为F在图 G 中的 anti-Ramsey 数,记作 AR(K,F).Anti-Ramsey 数最早由 Erds 等人 1 在 20 世纪 70 年代提出,揭示了图在完全图中的anti-Ramsey 数与图的 Turn 数密切相关,并考虑了当 k 6 时,圈在完全图中的 anti-Ramsey数的结论.后来,该问题由 Montellano-Ballesteros 等人 2 完全解决.之后,以完全图为母图的anti-Ramsey 数被广泛研究,如路 3,团 4,圈 57,匹配 4,79,森林 10,11 等图在完全图中的anti-Ramsey 数.近二十年来,对于 anti-Ramsey 数的研究开始以一些特殊的图类作为母图,比如:完全二部图 1214,平面图 1517 等.关于 k 条边的树的 anti-Ramsey 数的研究并不多.最早出现在 Jiang 和 West 18 的结论中,DOI:10.12677/aam.2024.131020170应用数学进展周韦佳，马华玮他们确定了 k 条边的树在完全图 Kn中的 anti-Ramsey 数.之后,Jin 和 Li 14 考虑了其在完全二部图中的 anti-Ramsey 数.最近,Zhang 和 Dong 19 给出了一个公式来刻画 k 条边的树在完全多部图上的值.同时给出了当 max2,n3 k n1 以及4n25 k n1 时具体的值,当 k 很小的时候,很难计算出其具体的值.在本文中,我们考虑母图是极大外平面,给出了 k 条边的树在其上的 anti-Ramsey 数的范围.为了方便叙述本文的主要结论,下面给出需要用到的定义和符号.给定一个图 G,V(G)表示图G 的顶点集,E(G)表示图 G 的边集.对于任意两个顶点 u,v V(G),边 e E(G),若 e=uv,则称顶点 u 和 v 是相邻的,并称顶点 u 或 v 与边 e 是关联的.对于图 G 和 H,若满足 V(H)V(G)和 E(H)E(G),则称 H 是图 G 的一个子图,记作 H G.若 V(H)=V(G),则称 H 是 G 的生成子图.此外,若 H 是图 G 的一个子图,F1,F2分别是图 H 的两个分支,其中点 x F1,y F2,如果 xy G,那么称 F1与 F2在 G 中是相邻的.Tk表示 k 条边的树,F表示为所有 k 条边的树的集合.图 G 的分支匹配是指:令图 G 为极大外平面图 Mn的生成子图,且 F1,F2,Fs分别是 G 的分支.构造图 G,使得 V(G)=F1,F2,Fs,其中 FiFj E(G)当且仅当存在点 u V(Fi),v V(Fj),满足 uv E(Mn).给定图 G的最大匹配 I.若 FiFj I,称分支 Fi与 Fj匹配成功.若 Fi是 I 未饱和的,则称分支 Fi为孤立分支.接着上述定义,我们进一步给出如下定义.假设 Fi与 Fj匹配成功.若 Fi与 Fj在 G中均为孤立点,则称 Fi与 Fj为孤立点匹配分支.否则称为非孤立点匹配分支.2.极大外平面图中 k 条边的数的范围令 Mn是一个阶数为 n 的极大外平面图.Theorem 2.1.?k 4,n c(mod k),?f(k)=(2k 5)n/k+1,0 c 2,2n 5n/k 4,3 c k 1.?f(k)AR(Mn,Fk)2n 6n2k1.证明:首先我们证明下界.令 Mn是一个阶数为 n 的极大外平面图且对 Mn进行如下边染色,情形 1.c=0.令 Mn是一个阶数为 n 的极大外平面图,设边集 E(Mn)=E(Cn)xixi+2,xixi+3,xixi+k2|i=(t 1)k+1,t n/k xnxj1,xnxj,xnxj+1|j=tk,t n/k 1.将 xixi+2,xixi+3,xixi+k2染不同的颜色,其中 i=(t1)k+1,t n/k.将 xjxj+1xj+k2染新的不同的颜色,其中 j=(t 1)k+1,t n/k.剩下的边用新的同一种颜色染.以上构造了 Mn的(2k 5)n/k+1)-边染色,且这种边染色不包含彩虹的 k 条边的树,因此下界成立.情形 2.1 c 2.令 Mn是一个阶数为 n 的极大外平面图,设边集 E(Mn)=E(Cn)xixi+2,xixi+3,xixi+k2|i=(t1)k+1,t n/kxnxj1,xnxj,xnxj+1|j=tk,t n/k1DOI:10.12677/aam.2024.131020171应用数学进展周韦佳，马华玮xnxkn/k1,xnxkn/k.将 xixi+2,xixi+3,xixi+k2染不同的颜色,其中 i=(t1)k+1,t n/k.将 xjxj+1xj+k2染新的不同的颜色,其中 j=(t 1)k+1,t n/k.剩下的边用新的同一种颜色染.以上构造了 Mn的(2k 5)n/k+1)-边染色,且这种边染色不包含彩虹的 k 条边的树,因此下界成立.情形 3.3 c k 1.令 Mn是一个阶数为 n 的极大外平面图,设边集 E(Mn)=E(Cn)xixi+2,xixi+3,xixi+k2|i=(t 1)k+1,t n/k xnxj1,xnxj,xnxj+1|j=tk,t n/k xkn/k+1xkn/k+3,xkn/k+1xkn/k+4,xkn/k+1xn1.将 xixi+2,xixi+3,xixi+k2染不同的颜色,其中 i=(t1)k+1,t=n/k.将 xjxj+1xj+k2染新的不同的颜色,其中 j=(t 1)k+1,t=n/k.同时将 xkn/k+1xkn/k+3,xkn/k+1xkn/k+4,xkn/k+1xn1以及 xkn/k+1xkn/k+2xn1染不同的颜色.剩下的边用新的同一种颜色染.以上构造了 Mn的(2n 5n/k 4)-边染色,且这种边染色不包含彩虹的 k 条边的树,因此下界成立.为了证明上界，我们只需证明 Mn的任意(2n 6n2k1+1)-边染色都包含彩虹的 k 条边的树.假设存在一个边染色 c 使得 Mn不包含彩虹的 k 条边的树且|c|=2n 6n2k1+1.设 G 是 Mn的一个代表子图,显然|V(G)|=n,|E(G)|=2n 6n2k1+1.我们令 F1,F2,Fs为 G 的分支,s 为 G 的分支数.因为 G 中不存在 k 条边的树,则 G 的每一个分支的阶数小于等于 k.对于任意在 Mn中相邻的两个分支 Fi,Fj,设|V(Fi)|=n1,|V(Fj)|=n2.假设 n1=n2=k.由于 Fi,Fj是两个在 Mn中相邻的分支,则存在 x V(Fi),y V(Fj),有xy E(Mn).由于 xy/E(G),那么一定存在一条边 e E(G)且 c(xy)=c(e).我们发现G e+xy中存在 k 条边的树,矛盾.因此 n1+n2 2k 1.接下来我们将图 G 进行分支匹配.假设:(1)存在 m1对是孤立点匹配分支.(2)存在 m2对非孤立点匹配分支,且每对匹配的分支的顶点数之和小于等于 k,我们设 m2对非孤立点匹配分支顶点数之和是 n2.(3)存在 m3对非孤立点匹配分支,且每对匹配的分支的顶点数之和大于等于 k+1,我们设 m3对非孤立点匹配分支顶点数之和是 n3.(4)存在 m4个孤立分支 Fi1,Fi2,Fil没有匹配,且|V(Fi1)|+|Fi2|+|Fil|=n4.我们容易得到 s=2m1+2m2+2m3+m4,n=2m1+n2+n3+n4,m2 n2/k,m3n3/(2k 1).Claim 1 任意两个在 Mn中相邻的分支 Fi,Fj,令|V(Fi)|=n1,|V(Fj)|=n2.如果 3 n1+n2 k,那么|E(Fi)|+|E(Fj)|2(n1+n2)5.因为 Fi,Fj是极大外平面图 Mn的分支,若 n1=1,即 Fi为孤立点分支,则|E(Fi)|=2n1 2=0.因为 3 n1+n2 k,所以 2 n2 k 1.由于 Fj是极大外平面图上的分支,我们有|E(Fj)|2n2 3.因此|E(Fi)|+|E(Fj)|2n2 3=2(n1+n2)5.若 n1 2,由于 Fi是极大外平面图 Mn的分支,则|E(Fi)|2n1 3.假设 n2=1.那么此时与 n1=1 时的情况相同,所以 n2 2,因此|E(Fi)|+|E(Fj)|2n13+2n23=2(n1+n2)6.DOI:10.12677/aam.2024.131020172应用数学进展周韦佳，马华玮综上,我们有|E(Fi)|+|E(Fj)|2(n1+n2)5.Claim 2 任意两个在 Mn中相邻的分支 Fi,Fj,|V(Fi)|=n1,|V(Fj)|=n2.如果 k+1 n1+n22k 1,那么|E(Fi)|+|E(Fj)|2(n1+n2)6.由于 Fi,Fj是两个在 Mn中相邻的分支,则存在 x V(Fi),y V(Fj),有 xy E(Mn).假设Fi,Fj中不存在割边.由于 xy/E(G),那么一定存在一条边 e E(G)且 c(xy)=c(e).我们发现在 G e+xy 中存在 k 条边的树,矛盾.因此 Fi,Fj中至少存在一条割边.假设 Fi,Fj中存在一个孤立点分支 Fi.因为 k+1 n1+n2 2k 1 且|V(Fj)|k,所以|V(Fj)|=n2=k.根据断言 1,我们可以得到|E(Fj)|2k 4.因此|E(Fi)|+|E(Fj)|2(n1+n2)6=2k 4.假设 Fi,Fj中不存在一个孤立点分支.假设 n1=2.因为 k+1 n1+n2 2k 1,所以k 1 n2 k.假设 n2=k.假设 Fj中不存在割边.由于 Fi,Fj是两个在 Mn中相邻的分支,存在 x1 V(Fi),y1 V(Fj),有 x1y1 E(Mn).由于 x1y1/E(G),那么一定存在一条边 e1 E(G)且 c(x1y1)=c(e1).我们发现在 G e1+x1y1中存在 k 条边的树,矛盾.所以 Fj中至少存在一条割边.根据断言 1,我们有|E(Fj)|2k 4.因此|E(Fi)|+|E(Fj)|2(n1+n2)7=2k 3.当n2=k 1 时,我们可以得到|E(Fi)|+|E(Fj)|2(n1+n2)6=2k 4.假设 3 n1 k.因为 k+1 n1+n2 2k 1,所以 3 n2 k.由于 Fi,Fj中至少存在一条割边.假设割边在 Fi中.我们得到|E(Fi)|2n1 4,|E(Fj)|2n2 3.因此我们有|E(Fi)|+|E(Fj)|2(n1+n2)7.综上所述,我们有|E(Fi)|+|E(Fj)|2(n1+n2)6.根据上述的分析,我们可以知道|E(G)|2n2 5m2+2n3 6m3+2n4 2m42n2 5n2/k+2n3 6n3/(2k 1)+2n4 2m4=2(n 2m1)5n2/k 6n3/(2k 1)2m42n 5n2/k 6n3/(2k 1)2n 6n/(2k 1)2n 6n/(2k 1)+1,矛盾.因此上界成立.综上所述,定理 2.1 证明完毕.3.总结本论文在 14,19 的基础上深入研究了边染色图中 k 条边的树的 anti-Ramsey 数的问题,考虑了其在极大外平面图中的 anti-Ramsey 数.本论文先通过极值染色的方法得到以极大外平面图为母图的 k 条边的树的 anti-Ramsey 数的上界,接着采用一种方法对图的分支进行配对,通过分支的配对以及极大外平面图的性质来计算图的边数,从而得到矛盾证明上界,最终得到定理成立.由于 kDOI:10.12677/aam.2024.131020173应用数学进展周韦佳，马华玮条边的树在不同母图上的 anti-Ramsey 数的结论较少,本论文的研究也为今后继续研究其它母图中k 条边的树的 anti-Ramsey 数提供思路.对于今后的研究方向主要是继续缩小 k 条边的树在极大外平面图中 anti-Ramsey 数的范围,以及其它母图中 k 条边的树的 anti-Ramsey 数.参考文献1 Erds,P.,Simonovits,M.,and Ss,V.T.(1975)Anti-Ramsey Theorems.In:Hajnal,A.,Rado,R.and Ss,V.T.,Eds.,Infinite and Finite Sets:To Paul Erds on His 60th Birthday,North-Holland,Amsterdam,633-643.2 Montellano-Ballesteros,J.J.and Neumann-Lara,V.(2002)An Anti-Ramsey Theorem.Com-binatorica,22,445-449.https:/doi.org/10.1007/s0049302000233 Simonovits,M.and Ss,V.T.(1984)On Restricting Colorings of Kn.Combinatorica,4,101-110.https:/doi.org/10.1007/BF025791624 Schiermeyer,I.(2004)Rainbow Numbers for Matchings and Complete Graphs.Discrete Math-ematics,286,157-162.https:/doi.org/10.1016/j.disc.2003.11.0575 Axenovich,M.,Jiang,T.and Kndgen,A.(2004)Bipartite Anti-Ramsey Numbers of Cycles.Journal of Graph Theory,47,9-28.https:/doi.org/10.1002/jgt.200126 Jiang,T.and West,D.B.(2003)On the Erds-Simonovits-Ss Conjecture on the Anti-RamseyNumber of a Cycle.Combinatorics,Probability and Computing,12,585-598.https:/doi.org/10.1017/S096354830300590X7 Jahanbekam,S.and West,D.B.(2016)Anti-Ramsey Problems for t Edge-Disjoint RainbowSpanning Subgraphs:Cycles,Matchings,or Trees.Journal of Graph Theory,82,75-89.https:/doi.org/10.1002/jgt.218888 Alon,N.(1983)On a Conjecture of Erds Simonovits and Ss Concerning Anti-Ramsey The-orems.Journal of Graph Theory,7,91-94.https:/doi.org/10.1002/jgt.31900701129 Chen,H.,Li,X.L.and Tu,J.H.(2009)Complete Solution for the Rainbow Numbers of Match-ings.Discrete Mathematics,309,3370-3380.https:/doi.org/10.1016/j.disc.2008.10.00210 Xie,T.Y.and Yuan,L.T.(2020)On the Anti-Ramsey Numbers of Linear Forests.DiscreteMathematics,343,Article 112130.https:/doi.org/10.1016/j.disc.2020.11213011 Fang,C.Q.,Gyri,E.,Lu,M.and Xiao,J.M.(2021)On the Anti-Ramsey Number of Forests.Discrete Applied Mathematics,291,129-142.https:/doi.org/10.1016/j.dam.2020.08.02712 Jia,Y.X.,Lu,M.and Zhang,Y.(2019)Anti-Ramsey Problems in Complete Bipartite Graphsfor t Edge-Disjoint Rainbow Spanning Subgraphs:Cycles and Matchings.Graphs and Combi-natorics,35,1011-1021.https:/doi.org/10.1007/s00373-019-02053-yDOI:10.12677/aam.2024.131020174应用数学进展周韦佳，马华玮13 Jin,Z.M.and Zang,Y.P.(2017)Anti-Ramsey Coloring for Matchings in Complete BipartiteGraphs.Journal of Combinatorial Optimization,33,1-12.14 Jin,Z.M.and Li,L.F.(2013)Edge-Colorings of Complete Bipartite Graphs without LargeRainbow Trees.Ars Combinatoria,111,75-84.15 Jendrol,S.(2019)On Rainbow Matchings in Plane Triangulations.Discrete Mathematics,342,Article 111624.https:/doi.org/10.1016/j.disc.2019.11162416 Hork,M.,Jendrol,S.,Schiermeyer,I.and Sotk,R.(2015)Rainbow Numbers for Cyclesin Plane Triangulations.Journal of Graph Theory,78,248-257.https:/doi.org/10.1002/jgt.2180317 Jendrol,S.,Schiermeyer,I.and Tu,J.H.(2014)Rainbow Numbers for Matchings in PlaneTriangulations.Discrete Mathematics,331,158-164.https:/doi.org/10.1016/j.disc.2014.05.01218 Jiang,T.and West,D.B.(2004)Edge-Colorings of Complete Graphs That Avoid Polychro-matic Trees.Discrete Mathematics,274,137-145.https:/doi.org/10.1016/j.disc.2003.09.00219 Zhang,M.Q.and Dong,F.M.(2022)Anti-Ramsey Numbers for Trees in Complete Multi-Partite Graphs.Discrete Mathematics,345,Article 113100.https:/doi.org/10.1016/j.disc.2022.113100DOI:10.12677/aam.2024.131020175应用数学进展