关于完全可定向图的一个注记＊

许丰伟, 王维凡

(浙江师范大学数理与信息工程学院,浙江金华 321004)

本文仅考虑有限简单图.给定一个图 G,用 V(G),E(G),|G|,‖G‖,Δ(G)和δ(G)分别表示它的顶点集合、边集合、顶点数、边数、最大度和最小度.G的围长是指图 G中最短圈的长度,用 g(G)表示;对于一个顶点 v∈V(G),用 d(v)表示 v在 G中的度,若 d(v)=k,则称 v为 G的一个 k-点;用 N(v)表示 v的所有邻点的集合;对于 S⊆V(G),用 G[S]表示 S在 G中的导出子图;图 G的一个正常 k-染色是指有一个从 V(G)到{1,2,…,k}的映射 f,使得当 x和 y相邻时,有 f(x)≠f(y);G的色数定义为 G的所有正常 k-染色中最小的 k值,记为χ(G).本文其他未加说明的符号和术语见文献[1].

给图 G的每一条边指定一个方向后得到一个有向图,若此有向图不存在有向圈,则称此有向图为 G的一个无圈定向;设 D是 G的一个无圈定向,若改变D中的一条弧的方向会产生有向圈,则称这条弧为D的相依边,用 d(D)表示 D中相依边的条数;给定一条相依边,以 x为尾,y为头,那么 D中必包含一条长度至少为 2的从 x到 y的有向路.用 dmin(G)和 dmax(G)分别表示 G的所有无圈定向中相依边数的最小值和最大值.若对满足 dmin(G)≤k≤dmax(G)的所有 k,都存在 G的无圈定向 D,使得 d(D)=k,则称 G为完全可定向的.

对于图的完全可定向性,目前已有一些研究成果.例如,文献[2]给出了 dmax(G)=‖G‖-|G|+c,其中 c表示 G的连通分支数,同时证明了当χ(G)

给定一个连通图 G,令τ(G)=‖G‖-|G|.如果τ(G)=-1,则 G是一个树;如果τ(G)=0,则 G是一个单圈图.由τ(G)的定义知,dmax(G)=‖G‖-|G|+1=τ(G)+1.综合文献 [2,4]的结果知,当dmin(G)不超过 1时 G是完全可定向的.对照这个结果,人们自然要问:当 dmax(G)至多为何值时 G是完全可定向的?本文完全回答了这个问题:当 dmax(G)≤6时,G是完全可定向的.

在给出主要结果之前,先引入一些有用的引理.

引理 1[7]设 G1,G2,…,Gk是 G的连通分支,若 Gi是完全可定向的 (i=1,2,…,k),则 G也是完全可定向的.

引理 2[8]设 v∈V(G)是 G的一个割点,G-v的连通分支的顶点集为 V1,V2,…,Vm,令 Gi是Vi∪{v}(i=1,2,…,m)的导出子图.若 Gi(i=1,2,…,m)是完全可定向的,则 G也是完全可定向的.

引理 3[7]设 v是图 G的一个度至多为 2的顶点.若 G-v是完全可定向的,则 G也是完全可定向的.

引理 4[8]设 v是图 G的一个 3-点,且 v的邻点中至少有 2个相邻.若 G-v是完全可定向的,则 G也是完全可定向的.

引理 5[8]若Δ(G)≤3,则 G是完全可定向的.

定理 1 若τ(G)≤5,则 G是完全可定向的.

证明 对 G的顶点数进行归纳证明.如果 |G|≤4,那么Δ(G)≤3,由引理 5知,G是完全可定向的.假设 G是一个满足 |G|≥5且τ(G)≤5的图,则由引理 1知,可以考虑 G是连通图.进一步,由引理 2知,可假设 G是 2-连通的,因此δ(G)≥2.首先证明断言 1.

断言 1 G满足下面 2个性质:

(1)若δ(G)≥4,则 G≅ K5;

(2)若 δ(G)=3,则 |G|≤10.

证明 因为τ(G)=‖G‖-|G|,所以‖G‖=τ(G)+|G|.由握手定理得

为了完成定理 1的证明,首先假设δ(G)=2,则 G有一个 2-点 v.设 H=G-v,那么 |H|=|G|-1,且

由归纳假设知,H是完全可定向的.由引理 3知,G也是完全可定向的.

其次,假设δ(G)≥4.由断言 1(1)知,G≅K5.由文献[5]知,G是完全可定向的.

最后,假设δ(G)=3.由断言 1(2)知,|G|≤10.如果Δ(G)=3,亦即 G是一个 3-正则图,则由引理 5可断言 G是完全可定向的.于是,假设Δ(G)≥4.这就隐含着 |G|≠10,否则 30=3|G|≤

如果χ(G)

断言 2 G有一个 3-点 v,使得 v的 3个邻点中至少有 2个是相邻的.

当τ(G)=5时,‖G‖=|G|+τ(G)=7+5=12.假设 V(G)={u1,u2,…,u7}满足 3≤d(u1)≤d(u2)≤…≤d(u7)≤6.此时,注意到 4≤Δ(G)≤6.

若Δ(G)=6,则 d(u7)=6,d(ui)=3,i=1,2,…,6.容易看到,u7的邻点中必有 2个是相邻的,故断言 2成立.

若Δ(G)=5,则 d(u7)=5,d(u6)=4,d(ui)=3,i=1,2,…,5.因此断言 u7的邻点中必有 2个是相邻的,否则‖G‖≥5+2·5=15,矛盾.由于在这 2个相邻的顶点中至少有 1个是 3-点,故断言 2成立.

若Δ(G)=4,则 d(u7)=d(u6)=d(u5)=4,d(u4)=d(u3)=d(u2)=d(u1)=3.首先假设 u7有一对邻点相邻.若这对相邻的顶点中至少有 1个是 3-点,则断言 2成立.否则,假设 N(u7)={u3,u4,u5,u6},u5u6∈E(G),u3u4,u3u5,u3u6,u4u5,u4u6∉E(G).因为 d(u5)=d(u6)=4且 d(u3)=d(u4)=3,所以{u3,u4,u5,u6}中的每个点必须分别与 u1和 u2相邻,于是 d(u1)≥4且 d(u2)≥4,与假设矛盾.其次假设 u7的任一对邻点均不相邻.因为δ(G)=3,‖G‖=12,所以容易推出 G是完全二部图 K3,4,与假设矛盾.故断言 2成立.

(3)|G|=8

当τ(G)=5时,显然,‖G‖ =|G|+τ(G)=8+5=13,4≤Δ(G)≤5,G至少有 6个 3-点.假设V(G)={v1,v2,…,v8},使得 3=d(v1)=d(v2)=…=d(v6)≤d(v7)≤d(v8)≤5.若 G含有一个 3-圈 C,则 C上必有一个 3-点满足断言 2.于是,假设 G不含 3-圈,即 g(G)≥4.

如果 d(v8)=5,那么 d(v7)=3.假设 v8的邻点集合为 N(v8)={v3,v4,…,v7}.若{v3,v4,…,v7}中至少有 2个顶点是相邻的,则断言 2成立.否则,{v3,v4,…,v7}中的每个顶点必分别与 v1和 v2相邻,导致‖G‖≥5+5·2=15,矛盾.如果 d(v8)=4,那么 d(v7)=4.假设 N(v8)={v1,v2,v3,vk},其中 k∈{4,5,6,7}.若 v1,v2,v3,vk中至少有 2个顶点相邻,则断言 2成立.于是,假设 v1,v2,v3,vk是互不相邻的,并令 S={v4,v5,v6,v7}{vk}.因为 ‖G‖=13,所以导出子图 G[S]至多包含 1条边,进一步,G[S∪{v8}]至多包含 1条边.用 1,2染 S∪{v8}中的顶点,用 3染 N(v8)中的顶点,得到 G的一个正常3-染色,于是χ(G)≤3,与假设χ(G)≥g(G)≥4矛盾.故断言 2成立.

(4)|G|=9

由断言 2知,G有一个 3-点 v.设 H=G-v,那么 |H|=|G|-1,且

由归纳假设知,H是完全可定向的.由引理 4知,G也是完全可定向的.定理 1证毕.

因为 dmax(G)=‖G‖-|G|+1=τ(G)+1,所以由定理 1可得推论 1.

推论 1 若 dmax(G)≤6,则 G是完全可定向的.

推论 1中的条件 dmax(G)≤6是最好可能的,因为对于满足 dmax(K3(2))=7且 K3(2)不是完全可定向的.这就从相依边数最大值的角度完全刻画出图的完全可定向性.

[1]Bondy J A,MurtyU S R.Graph Theory[M].Berlin:Springer,2008.

[2]FisherD C,Fraughnaugh K,LangleyL,et al.The number of dependent arcs in an acyclic orientation[J].J Combin Theory:B,1997,71(1):73-78.

[3]Grötzsch H.Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel[J].W iss ZMartin-Luther Univ Halle-W ittenbergMath-Nat Reihe,1959(8):109-120.

[4]LaiH H,Lih KW,TongLida.Fullyorientabilityof graphswith atmostone dependentarc[J].DiscteteApplMath,2009,157(13):2969-2972.

[5]WestD B.Acyclic orientations of complete bipartite graphs[J].DiscreteMath,1995,138(1):393-396.

[6]Lih KW,Lin Chenying,TongLida.On an interpolation property of outerplanar graphs[J].Disctete ApplMath,2006,154(1):166-172.

[7]Lai H H,Chang G J,Lih KW.On fully orientability of 2-degenerate graphs[J].Infor m ProcessLett,2008,105(5):177-181.

[8]Lai H H,Lih KW.On preserving full orientability of graphs[J].European J Combin,2010,31(2):598-607.

[9]Chang G J,Lin Chenying,TongLida.Independent arcs of acyclic orientations of completer-partite graphs[J].DiscreteMath,2009,309(13):4280-4286.