路与路及路与圈笛卡尔积图的树核度

关于循环图及一些特殊图与路、星、树和圈的笛卡尔积的
交叉数研究的开题报告
循环图是一类特殊的图，其特点在于除了一些特殊情况外，每个节点都与相邻的两个节点相连。

循环图在数学、物理、生物等领域都有着广泛的应用，因此其研究具有重要意义。

在循环图的研究中，一个重要的概念是交叉数。

交叉数描述了循环图中边相互穿过的次数。

我们可以通过计算循环图中所有边的交叉数来得到循环图的交叉数。

交叉数可以用于解决多个问题，例如，染色问题、计算拓扑图中的曲线和面积等。

除了循环图之外，还有一些特殊图形，例如路、星、树和圈。

这些图形在具体应用中也有重要作用。

在图论研究中，这些特殊图形的研究可以帮助我们更好地理解图论的基础概念和结论。

为了更深入地研究这些特殊图形，我们需要探索它们之间的关系。

这可以通过它们的笛卡尔积得到。

笛卡尔积是一种将两个集合中的元素组合起来形成的新集合，其中每个元素都由两个集合中的一个元素组成。

通过计算特殊图形之间的笛卡尔积，我们可以了解它们之间的关系，例如它们的交叉数等。

在这个研究中，我们将探讨循环图及一些特殊图形与它们的笛卡尔积之间的交叉数关系。

我们会尝试通过数学证明和计算实例来得到一些结论，这些结论将有助于更好地理解图论中的基础概念和应用。

笛卡尔积路径问题
路径问题是计算机科学中经常遇到的一类问题。

当我们需要找到从起点到终点的最短路径或者枚举所有可能的路径时，常常需要借助笛卡尔积来解决。

笛卡尔积是集合论中的一个概念，它由两个集合的所有可能的有序对组成。

在路径问题中，我们可以将路径看作是一系列的节点组成的序列。

假设我们有两个集合A和B，分别表示起点可能的位置和终点可能的位置。

我们希望找到从任意起点到任意终点的路径。

这时，我们可以计算A和B的笛卡尔积，得到所有可能的起点-终点对。

例如，A = {A1, A2, A3} 表示起点可能的位置，B = {B1, B2, B3} 表示终点可能的位置。

计算A和B的笛卡尔积，得到的结果为{(A1, B1), (A1, B2), (A1, B3), (A2, B1), (A2, B2), (A2, B3), (A3, B1), (A3, B2), (A3, B3)}。

接着，我们可以遍历笛卡尔积中的每一个起点-终点对，使用适当的算法（如广度优先搜索或Dijkstra算法）来计算从起点到终点的最短路径。

在实际应用中，路径问题常常与图相关联。

图由节点和节点之间的边组成。

每个节点代表一个位置，边表示两个位置之间的连接。

我们可以利用图的数据结构来表示路径问题，并借助图的遍历算法来寻找最短路径或枚举所有可能的路径。

总结起来，笛卡尔积在路径问题中的应用主要是为了生成起点-终点对。

通过计算起点和终点集合的笛卡尔积，我们可以得到所有可能的起点-终点对，从而应用适当的算法求解路径问题。

特殊图的积图的Merrifield-Simmons指标刘漫;田双亮【摘要】Merrifield-Simmons指标表示图的独立集的数目,记M-S指标.本文定义几类特殊图,研究这些图类的M-S指标,得到了相应的M-S指标表达式.在此基础上,得到了路与完全图的笛卡尔积、直积、半强积以及强积的M-S指标表达式.【期刊名称】《湖北民族学院学报（自然科学版）》【年(卷),期】2019(037)002【总页数】4页(P192-194,211)【关键词】路;完全图;积图;Merrifield-Simmons指标【作者】刘漫;田双亮【作者单位】西北民族大学数学与计算机科学学院,兰州730030;西北民族大学数学与计算机科学学院,兰州730030【正文语种】中文【中图分类】O157.51 前言Merrifield-Simmons指标是由美国化学家Merrifield和Simmons在文献[1]中提出的，它表示图G中所有独立集的数目，简称为M-S指标，用符号i(G)表示.该拓扑指标与许多物理化学性质密切相关，如分子的稳定性，熔沸点以及物质的能量等.设G是具有顶点集V(G)与边集E(G)的简单连通图.对任意的v∈V(G)，用NG(v)表示v的邻点构成的集合，即NG(v)={u|uv∈E(G)}.称NG(v)为v的开邻集，NG[v]={v}∪NG(v)为v的闭邻集.图的结构运算是构造结构复杂的图的重要工具之一，图的常见运算包括笛卡尔积、直积、半强积、强积以及字典积等等.两个简单图G和H的笛卡尔积[2]G□H是具有顶点集V(G)×V(H)的简单图，若顶点(u1,v1)与(u2,v2)相邻当且仅当u1=u2且v1v2∈E(H)，或v1=v2且u1u2∈E(G).两个简单图G和H的直积[3]G×H是具有顶点集V(G)×V(H)的简单图，若顶点(u1,v1)与(u2,v2)相邻当且仅当u1u2∈E(G)且v1v2∈E(H).两个简单图G与H的半强积[4]G·H是具有顶点集V(G)×V(H)的简单图，若顶点(u1,v1)与(u2,v2)相邻当且仅当u1u2∈E(G)且v1v2∈E(H)，或u1=u2且v1v2∈E(H).两个简单图G和H的强积[4]GH是具有顶点集V(G)×V(H)的简单图，若顶点(u1,v1)与(u2,v2)相邻当且仅当u1u2∈E(G)且v1v2∈E(H)，或u1=u2且v1v2∈E(H)，或v1=v2且u1u2∈E(G).Lai-Huan等在文献[5]中通过Matlab编程计算了特殊图类如六角链的M-S指标表达式.Frucht在文献[6]中提出两个图的冠之后，Reyhani等在文献[7]中对一些简单冠图如Pn∘K1的M-S指标的计数问题进行了研究.刘睿琳和陈妹君等在文献[8-9]中研究了最大度为2的图如字典积图的M-S指标，得到了相应的M-S指标表达式.首先，利用不相交完全图定义以下几种特殊图类.设Km,Kn,Kh是分别具有顶点集X={x1,x2,…,xm}，Y={y1,y2,…,yn}与Z={z1,z2,…,zh}的三个不相交的完全图，其中n,h≥2，m≥1且n,h≥m.设G(1)(m,n)=Km∪Kn∪M，G(2)(m,n)=Km,n-M，G(3)(m,n)=G(1)(m,n)∪G(2)(m,n)-M，G(4)(m,n)=G(1)(m,n)∪G(2)(m,n).其中，M={xiyi|i=1,2,…,t}，t=min(m,n)，Km,n是具有二分类(X,Y)的完全二部图.由G(i)(m,n),(i=1,2,3,4)的定义知:G(1)(n,n)=P2□Kn，G(2)(n,n)=P2×Kn，G(3)(n,n)=P2·Kn，G(4)(n,n)=P2Kn.设G(1)(m,n,h)=G(1)(m,n)∪G(1)(n,h)，G(2)(m,n,h)=G(2)(m,n)∪G(2)(n,h)，G(3)(m,n,h)=G(3)(m,n)∪G(3)(n,h)，G(4)(m,n,h)=G(4)(m,n)∪G(4)(n,h).其中，G(i)(m,n)与G(i)(n,h)的顶点集分别为X∪Y与Y∪Z.由G(i)(m,n,h),(i=1,2,3,4)的定义知:G(1)(n,n,n)=P3□Kn，G(2)(n,n,n)=P3×Kn，G(3)(n,n,n)=P3·Kn，G(4)(n,n,n)=P3Kn.对于i=1,2,3,4，为了研究G(i)(m,n)与G(i)(n,m,n)的M-S指标，先给出以下引理. 引理1[10] 设G是一个简单连通图，对任意的顶点u∈V(G)，有:i(G)=i(G-u)+i(G-NG[u]).引理2[10] 若图G的连通分支为G1,G2,…,Gn，则2 主要结果及其证明关于图类G(i)(m,n)的M-S指标有以下定理，其中i=1,2,3,4.定理1 对任意整数m,n，若n≥m≥2，则i(G(1)(m,n))=(m+1)n+1.证明由G(1)(m,n)的定义可知，对G(1)(m,n)的任一独立集B，显然，B ≤2.而G(1)(m,n)中包含两个顶点的独立集共有m(n-1)个，且G(1)(m,n)中包含1个顶点的独立集共有m+n个.所以，i(G(1)(m,n))=1+m+n+m(n-1)=(m+1)n+1.因此，定理结论成立.由定理1及引理1，可直接得到P2与Kn的笛卡尔积的M-S指标的表达式，具体见推论1.推论1 对任意整数n≥2，有i(P2□Kn)=n2+n+1.定理2 对任意整数m,n，若n≥m≥2，则i(G(2)(m,n))=2m+2n+m-1.证明由G(2)(m,n)的定义可知，对G(2)(m,n)的任一独立集B，显然，B必须满足以下条件之一：(i)B⊆X；(ii)B⊆Y；(iii) B =2且B∩X = B∩Y =1.所以，其中，与分别表示m阶与n阶的空图.所以，i(G(2)(m,n))=2m+2n+m-1.因此，定理结论成立.由定理2及引理1可得到以下推论.推论2 对任意整数n≥2，有i(P2×Kn)=2n+1+n-1.定理3 对任意整数m,n，若n≥m≥2，则i(G(3)(m,n))=2m+n+1.证明由G(3)(m,n)的定义可知，对G(3)(m,n)的任一独立集B，B ≤2.若 B =2，则B∩X = B∩Y =1.所以G(3)(m,n)中包含两个顶点的独立集共有m个.所以，i(G(3)m,n)=1+(m+n)+m=2m+n+1.因此，定理结论成立.由定理3及引理1，可直接得到P2与Kn的半强积的M-S指标的表达式.推论3 对任意整数n≥2，有i(P2·Kn)=3n+1.定理4 对任意整数m,n，若n≥m≥2，则i(G(4)(m,n))=m+n+1.证明由G(4)(m,n)的定义可知，对G(4)(m,n)的任一独立集B，B ≤1.若 B =1，则B = X = Y =1.所以，G(4)(m,n)中包含1个顶点的独立集共有m+n个.所以，i(G(4)(m,n))=m+n+1.因此，定理结论成立.由定理4及引理1，可直接得到P2与Kn的强积的M-S指标的表达式，具体见推论4.推论4 对任意整数n≥2，有i(P2Kn)=2n+1.记H(i)(m)=G(i)(n,m,n)，其中i=1,2,3,4.关于图类H(i)(m)的M-S指标有以下结果.定理5 对任意整数m,n，若m≥1,n≥2,则i(H(1)(m))=(n+1)2+mn2.证明对m用数学归纳法.由H(1)(m)的定义以及引理1和引理2可知，i(H(1)(1))=i2(Kn)+i2(Kn-1)=(n+1)2+n2.显然，当m=1时，结论成立.假设当m≤k时，有i(H(1)(k))=(n+1)2+kn2.当m=k+1时，i(H(1)(k+1))=i(H(1)(k+1)-yk+1)+i(H(1)(k+1)-NH(1)(k+1)[yk+1])=i(H(1)(k))+i2(Kn-1)=(n+1)2+kn2+n2=(n+1)2+(k+1)n2.所以，i(H(1)(m))=(n+1)2+mn2.因此，定理结论成立.由定理5及引理1，可直接得到P3与Kn的笛卡尔积的M-S指标的表达式，具体见推论5.推论5 对任意整数n≥2，有i(P3□Kn)=n3+(n+1)2.定理6 对任意整数m,n，若m≥1,n≥2，则i(H(2)(m))=22n+2m+3m-1.证明对m用数学归纳法.由H(2)(m)的定义以及引理1和引理2可知，其中，S2n-1表示2n-1阶的星.显然，当m=1时，结论成立.假设当m≤k时，有i(H(2)(k))=22n+2k+3k-1.当m=k+1时，i(H(2)(k+1))=i(H(2)(k+1)-yk+1)+i(H(2)(k+1)-NH(2)(k+1)[yk+1])=i(H(2)(k))+22+2k-1=22n+2k+3k-1+22+2k-1=22n+2k+1+3(k+1)-1.所以，i(H(2)(m))=22n+2m+3m-1.因此，定理结论成立.由定理6及引理1，可直接得到P3与Kn的直积的M-S指标的表达式，具体见推论6.推论6 对任意整数n≥2，有i(P3×Kn)=22n+2n+3n-1.定理7 对任意整数m,n，若m≥1,n≥2，则i(H(3)(m))=(n+1)2+4m.证明对m用数学归纳法.由H(3)(m)的定义以及引理1和引理2可知，显然，当m=1时，结论成立.假设当m≤k时，有i(H(3)(k))=(n+1)2+4k.当m=k+1时，i(H(3)(k+1))=i(H(3)(k+1)-yk+1)+i(H(3)(k+1)-NH(3)(k+1)[yk+1])=所以，i(H(3)(m))=(n+1)2+4m.因此，定理结论成立.由定理7及引理1，可直接得到P3与Kn的半强积的M-S指标的表达式，具体见推论7.推论7 对任意整数n≥2，有i(P3·Kn)=(n+1)2+4n.定理8 对任意整数m,n，若m≥1,n≥2，则i(H(4)(m))=(n+1)2+m.证明对m用数学归纳法.由H(4)(m)的定义以及引理1和引理2可知，i(H(4)(1))=i2(Kn)+i(K1)=(n+1)2+1.显然，当m=1时，结论成立.假设当m≤k时，有i(H(4)(k))=(n+1)2+k.当m=k+1时，i(H(4)(k+1))=i(H(4)(k+1)-yk+1)+i(H(4)(k+1)-NH(4)(k+1)[yk+1])=i(H(4)(k))+i(K1)=(n+1)2+k+1=(n+1)2+(k+1).所以，i(H(4)(m))=(n+1)2+m.因此，定理结论成立.由定理8及引理1，可直接得到P3与Kn的强积的M-S指标的表达式，具体见推论8.推论8 对任意整数n≥2，有i(P3Kn)=(n+1)2+n.参考文献:【相关文献】[1] MERRIFIELD R E,SIMMONS H E.Topolopical Methods in Chemistry[M].NewYork:Wilery,1989.[2] DOUGLAS B,WEST.Graph Theory[M].Prentice-Hall:Inc,1996.[3] BONDY J A,MURTY U S R.Graph Theory with applications[M].New York:Macmillan,1976.[4] JARADAT M M M.On the edge coloring of graph products[J].International Journal of Mathematics and Mathematical Sciences,2005(16):296-301.[5] CHEN L H,ZHAO puting formulae for two indices of hexagonal chains[J].Journal of Xinjiang University(Natural Science Edition),2012,29(4):442-447.[6] FRUCHT R,HARARY F.On the corona of two graphs[J].Aequationes Mathematicae,1970,4(1/2):264-264.[7] REYHANI M H,ALIKHANI S,RANMANESH M A I.Hosoya and Merrifield-Simmons indices of some classes of corona of two graphs[J].Transactions on Combinatorics,2012,1(4):1-7. [8] 刘睿琳,田双亮,陈妹君,等.两类字典积图的Merrifield-Simmons指标[J].兰州文理学院学报(自然科学版),2017,31(1):15-18.[9] 陈妹君,田双亮.两类运算图的Merrifield-Simmons指标[J].重庆文理学院学报,2015,34(2):37-39.[10] GUTMAN I,POLANSKY O E.Mathematical concepts in organicchemistry[M].Berlin:Springer,1986.。

笛卡尔积图的线性荫度陶昉昀;林文松【摘要】线性森林是指所有分支都是路的森林.图G的线性荫度la(G)是划分G的边集E(G)所需的线性森林的最小数目.图G和H的笛卡尔积图G□□H定义为:顶点集V(G□□H)={(u,v)|u∈V(G),v∈V(H)}.边集E(G□□H)={(u,x)(v,y)|u=v且xy∈E(H),或uv∈E(G)且x=y}.令Pm与Gm分别表示m个顶点的路和圈,Kn表示n个顶点的完全图.证明了la(Kn□□Pm)=[n+1/2](m≥2),la(Kn□□Cm)=[n+2/2]以及la(Kn□Km)=[n+m-1/2].证明过程给出了将这些图分解成线性森林的方法.进一步的线性荫度猜想对这些图类是成立的.【期刊名称】《东南大学学报（英文版）》【年(卷),期】2013(029)002【总页数】4页(P222-225)【关键词】线性森林;线性荫度;笛卡尔积【作者】陶昉昀;林文松【作者单位】东南大学数学系,南京211189;南京林业大学数学系,南京210037;东南大学数学系,南京211189【正文语种】中文【中图分类】O157.5In this paper, all the graphs are simple, finite and undirected. For a realnumber x, 「x⎤ is the least integer not less than x and ⎤x」 is the largest integer not larger than x. Let G be a graph. We use V(G), E(G) and Δ(G) to denote the vertex set, the edge set and the maximum degree of G, respectively.A linear forest is a forest whose components are paths. The linear arboricity la(G) of G defined by Harary[1] is the minimum number of linear forests needed to partition the edge set E(G) of G.Akiyama et al.[2] conjectured that la(G)=「(Δ(G)+1)/2⎤ for any regular graph G. They proved that the conjecture is true for complete graphs and graphs with Δ=3,4[2-3]. Enomoto and Péroche[4] proved that the conjecture is true for graphs with Δ=5,6,8. Guldan[5] proved that the conjecture is true for graphs with Δ=10. It is obvious that la(G)≥「Δ(G)/2⎤for every graph G and la(G)≥「(Δ(G)+1)/2⎤ for every regular graph G. So the conjecture is equivalent to the following linear arboricity conjecture (LAC)[2]. For any graph G, 「Δ(G)/2⎤≤la(G)≤「(Δ(G)+1)/2⎤.Akiyama et al.[2] determined the linear arboricity of complete bipartite graphs and trees. Martinova[6] determined the linear arboricity of the maximal outerplanar graphs. Wu et al.[7-8] proved that the LAC is true for all the planar graphs. Wu[9] also determined the linear arboricity of the series-parallel graphs. Some other researches on linear arboricity can be found in Refs.[10-12].The Cartesian product of two graphs G and H (or simply product), denoted by G□H, is defined as the graph with vertex set V(G□H)={(u,v)|u∈V(G),v∈V(H)} and edge set E(G□H)={(u,x)(v,y)|u=v and xy∈E(H), or uv∈E(G) andx=y}. Let Pm and Cm respectively, denote the path and cycle on m vertices and Kn denote the complete graph on n vertices. In this paper, we determine the linear arboricity of Kn□Pm, Kn□Cm and Kn□Km.The following lemmas are useful in our proofs.Lemma1 If H is a subgraph of G, then la(H)≤la(G).Lemma2 la(G□H)≤la(G)+la(H).Lemma 2 holds by the definition of the linear arboricity and the Cartesian product of graphs.Lemma3[2] la(Kn)=「n/2⎤.Lemma4[13] For n≥3, the complete graph Kn is decomposable into edge disjoint Hamilton cycles if and only if n is odd. For n≥2, the complete graph Kn is decomposable into edge disjoint Hamilton paths if and only if n is even.Lemma5[14] Let V(K2n)={v0,v1,…,v2n-1}. For 0≤i≤n-1, putFi=v0+iv1+iv2n-1+iv2+iv2n-2+i…vn+1+ivn+iwhere the indices of vj’s are taken modulo 2n. Then F0,F1,…,Fn-1 are disjoint Hamilton paths of K2n; i.e., K2n is decomposed into edge disjoint Hamilton paths F0,F1,…,Fn-1.1 la(Kn□Pm)Let V(Kn)={u,v0,v1,…,vn-2} and V(Pm)={y0,y1,…,ym-1}. For convenience, we denote any vertex (x,yj)∈V(Kn□Pm) by x(j). For a fixed j (j=0,1,…,m-1), we use to denote the complete graph induced by {u(j),,,…,}.The following lemma deals with the decomposition of the complete graph K2n+1.Lemma6 E(K2n+1)=nP2n+1∪Mn, where Mn is a matching of order n. Proof Let V(K2n+1)={u,v0,v1,…,v2n-1}. For 0≤i≤n-1, putFi=v0+iv1+iv2n-1+iv2+iv2n-2+i…vn+1+ivn+iwhere the indices of vj’s are taken modulo 2n. Then, by Lemma 5, the complete graph K2n+1\{u} is decomposed into n disjoint Hamilton paths: F0,F1,…,Fn-1. For 0≤i≤n-1, let ei be the n-th edge of Fi andMn={e0,e1,…,en-1}. Then ei=vi+「n/2⎤vi-「n/2⎤ for i=0,1,…,n-1 andMn={v0vn,v1vn+1,…,vn-1v2n-1}. Clearly, Mn is a matching of order n. For each 0≤i≤n-1, by deleting ei from Fi and adding two edges uvi, uvn+i to Fi, we obtain a path on 2n+1 vertices. The n paths obtained in this way together with Mn form a decomposition of K2n+1 as claimed in the lemma. Theorem1 la(Kn□Pm)= for m≥2.Proof If m=2, then la(Kn□Pm)≥ since Kn□Pm is n-regular. If m≥3, thenla(Kn□Pm)≥=, where Δ=Δ(Kn□Pm). We now prove the reverse inequality. If n is even, then la(Kn□Pm)≤la(Kn)+la(Pm)=+1= by Lemmas 2 and 3. Thus Theorem 1 holds for even n.Now suppose that n is odd. Let n=2k+1, where k≥1. For 0≤i≤k-1 and0≤j≤m-1, putwhere the indices of ’s are taken modulo 2k. Then by Lemmas 4 and 5, for 0≤j≤m-1, is decomposed into k edge disjoint Hamilton cycles=u(j)(i=0,1,…,k-1).Let be the k-th edge of and = \{} for 0≤i≤k-1 and 0≤j≤m-1. From the proof of Lemma 6, each complete graph can be decomposed into k edgedisjoint Hamilton paths ,,…, and a matching ={,,…,}.Let Nxi={j=1,3,…,s}, where s=m-2 if m is odd and s=m-3 if m is even; and Nyi={j=0,2,…,t}, where t=m-3 if m is odd and t=m-2 if m is even.Let Li=()∪Nxi∪Nyi for 0≤i≤k-1. Then L0,L1,…,Lk-1 are k edge disjoint Hamilton paths of Kn□Pm. After we take away these Hamilton paths from Kn□Pm, the remaining edges form a linear forest. Thus,la(Kn□Pm)≤k+1=+1=. This com pletes the proof.2 la(Kn□Cm)Theorem2 la(Kn□Cm)=.Proof Since Kn□Cm can be decomposed into a Kn□Pm and a matching of size n, we have la(Kn□Cm)≤la(Kn□Pm)+1=+1 by Theorem 1. On the other hand, since Kn□Cm is (n+1)-regular, la(Kn□Cm)≥=. If n is odd, thenla(Kn□Cm)≤=. Therefore the theorem holds for odd n.Now we consider the case that n is even. Note that , we only need to show that Kn□Cm can be decomposed into linear forests. Let n=2k, where k≥1. Let V(Kn)={v0,v1,…,v2k-1} and V(Cm)={y0,y1,…,ym-1}. For convenience, we denote any vertex (vi,yj)∈V(Kn□Cm) by . For a fixed j (j=0,1,…,m-1), we use to denote the complete graph induced by {,,…,}. By Lemma 5, for 0≤j≤m-1, each can be decomposed into k edge disjoint Hamilton paths (i=0,1,…,k-1), whereand the subscripts are taken modulo 2k.For i=0,1,…,k-1, let Li=()∪{}∪{}. It is easy to see that L0,L1,…,Lk-1 are k edge disjoint linear forests and the remaining edges in Kn□Cm form onelinear forest. Thus, la(Kn□Cm)≤k+1=, which completes the proof.3 la(Kn□Km)Theor em3 la(Kn□Km)= if n and m are both even.Proof By Lemmas 2 and 3, la(Kn□Km)≤la(Kn)+la(Km)=+=. Since Kn□Km is (n+m-2)-regular, la(Kn□Km)≥=.Now, we consider the case that at least one of n,m is odd.Theorem 4 la(Kn□Km)= if n is even and m is odd.Proof Let n=2k, k≥1. Let V(Kn)={v0,v1,…,vn-1} and V(Km)={y0,y1,…,ym-1}. For convenience, we denote any vertex (vi,yj)∈V(Kn□Km) by . For a fixed j (j=0,1,…,m-1), we use to denote the complete graph induced by {,,…,}. For a fixed i (i=0,1,…,n-1), we use to denote the complete graph induced by {,,…,}. By Lemma 5, for 0≤j≤m-1, each can be decomposed into k edge disjoint Hamilton paths (i=0,1,…,k-1), whereand the subscripts are taken modulo 2k.For i=0,1,…,k-1, let Ni={j=0,2,…,m-3} and Ni+k={j=1,3,…,m-2}. It is easy to see that each Ni(i=0,1,…,2k-1) is a matching of and |Ni|=. By Lemma 6, the edges in each Ni(i=0,1,…,2k-1) can be partitioned into Hamilton paths. So the edges in E()\Ni(i=0,1,…,2k-1) form linear forests together. Furthermore, for 0≤i≤k-1, each ()∪Ni∪Ni+k forms a linear forest. So la(Kn□Km)≤+k=+=. On the other hand, la(Kn□Km)≥= since Kn□Km is (n+m-2)-regular. This completes the proof.Theorem5 la(Kn□Km)= if n and m are both odd.Proof We use the same notations in Theorem 4; i.e., letV(Kn□Km)={i=0,1,…,n-1;j=0,1,…,m-1}. For a fixed j (j=0,1,…,m-1), we use to denote the complete graph induced by {,,}. For a fixed i (i=0,1,…,n-1), we use to denote the complete graph induced by {,,…,}.Let Hi={j=0,2,…,m-3} for i=0,1,3,5,…n-2 and Hi={j=1,3,…,m-2} fori=2,4,6,…n-1. Then each Hi is a matching of with edges. By Lemma 6, the edges in each E()\Hi(i=0,1,…,n-1) can be partitioned into Hamilton paths. So the edges in E()\Hi(i=0,1,…,n-1) form linear forests together.Let Lj={,,…,} for j=0,1,…m-1. Then each Lj is a matching of with edges. Again by Lemma 6, the edges in each E()\Lj(j=0,1,…,m-1) can be partitioned into Hamilton paths. So the edges in E()\Lj(j=0,1,…,m-1) form linear forests together.It is clear that (Hi)∪(Lj) forms a linear forest. So la(Kn□Km)≤++1=. On the other hand, since Kn□Km is (n+m-2)-regular, la(Kn□Km)≥=. This completes the proof.Summarizing Theorems 3 to 5, we have the following theorem. Theorem6 la(Kn□Km)=.References[1]Harary F. Covering and packing in graphs 1 [J]. AnnalsoftheNewYorkAcademyofSciences, 1970, 175(1): 198-205.[2]Akiyama J, Exoo G, Harary F. Covering and packing in graphs 3: cyclic and acyclic invariants [J]. MathSlovaca, 1980, 30(4): 405-417.[3]Akiyama J, Exoo G, Harary F. Covering and packing in graphs 4: linear arboricity [J]. Networks, 1981, 11(1): 69-72.[4]Enomoto H, Péroche B. The linear arboricity of some regular graphs [J].JournalofGraphTheory, 1984, 8(2): 309-324.[5]Guldan F. The linear arboricity of 10-regular graphs [J]. MathSlovaca, 1986, 36(3): 225-228.[6]Martinova M K. Linear arboricity of maximal outerplanar graphs [J]. GodishnikVisshUchebnZavedPrilozhnaMath, 1987, 23: 147-155. (in Bulgarian)[7]Wu Jianliang. On the linear arboricity of planar graphs [J]. JournalofGraphTheory, 1999, 31(2): 129-134.[8]Wu Jianliang, Wu Yuwen. The linear arboricity of planar graphs of maximum degree seven are four [J]. JournalofGraphTheory, 2008, 58(3): 210-220.[9]Wu Jianliang. The linear arboricity of series-parallel graphs [J]. GraphsandCombinatorics, 2000, 16(3): 367-372.[10]Lu Xiaoxu, Xu Baogang. A note on vertex-arboricity of plane graphs [J]. JournalofNanjingUniversity: NaturalSciences, 2007, 43(1): 13-18.[11]Tan Xiang, Chen Hongyu, Wu Jianliang. The linear arboricity of planar graphs with maximum degree at least five [J]. BulletinoftheMalaysianMathematicalSciencesSociety, 2011, 34(3): 541-552.[12]Wu Jianliang, Hou Jianfeng, Liu Guizhen. The linear arboricity of planar graphs with no short cycles [J]. TheoreticalComputerScience, 2007,381(1/2/3): 230-233.[13]Bollobs B. Moderngraphtheory [M]. New York:Springer-Verlag, 1998.[14]Chen B L, Huang K C. On the linear k-arboricity of Kn and Kn,n [J].DiscreteMath, 2002, 254(1/2/3): 51-61.。

笛卡尔积路径问题
（原创版）
目录
1.笛卡尔积的定义与概念
2.路径问题的提出
3.笛卡尔积在路径问题中的应用
4.笛卡尔积的优缺点
5.结论
正文
1.笛卡尔积的定义与概念
笛卡尔积，又称直积或笛卡儿积，是一个数学概念，用于描述两个或多个集合之间的组合。

给定两个集合 A 和 B，它们的笛卡尔积是一个包含所有可能的有序对 (a, b) 的集合，其中 a 来自集合 A，b 来自集合B。

用符号表示为：A × B。

2.路径问题的提出
路径问题是图论中的一个经典问题，它涉及到寻找从一个顶点到另一个顶点的最短路径。

在网络科学、社交网络、交通运输等领域具有广泛的应用。

3.笛卡尔积在路径问题中的应用
在路径问题中，笛卡尔积被用于表示所有可能的路径。

假设有一个无向图 G = (V, E)，其中 V 表示顶点集合，E 表示边集合。

我们可以将顶点集合 V 看作是一个集合，边集合 E 看作是另一个集合。

这样，笛卡尔积 V × V 就代表了所有可能的顶点序列，即所有可能的路径。

我们可以通过分析笛卡尔积，找到从起点到终点的最短路径。

4.笛卡尔积的优缺点
笛卡尔积的优点是能够直观地表示所有可能的组合，便于分析和研究。

然而，它的缺点是计算量较大，尤其是在处理大规模数据时，可能会导致计算效率低下。

5.结论
笛卡尔积作为一种数学概念，在路径问题等许多领域具有广泛的应用。

通过分析笛卡尔积，我们可以找到从起点到终点的最短路径。

然而，需要注意的是，笛卡尔积的计算量较大，可能会影响计算效率。

第59卷 第3期吉林大学学报(理学版)V o l .59 N o .32021年5月J o u r n a l o f J i l i nU n i v e r s i t y (S c i e n c eE d i t i o n )M a y2021d o i :10.13413/j .c n k i .jd x b l x b .2020299似星树与路的乘积图的任意可分性张盼盼,刘凤霞,孟吉翔(新疆大学数学与系统科学学院,乌鲁木齐830046)摘要:设似星树S =S (a 1,a 2, ,a t ,b 1,b 2, ,b s ),其中a i (1ɤi ɤt )是奇数,b j (1ɤj ɤs )是偶数.首先,讨论似星树S 与路P l 的乘积图S ▷◁P l 在t 和s 不同取值下是否为任意可分图,并用图不含完美匹配的方法和反证法给出其不是任意可分图的充分条件;其次,分析图S ▷◁P l 的Ha m i l t o n 性,并用似星树的任意可分性给出图为任意可分图的充分条件.结果表明,当t =1且s ɤ2时,图S ▷◁P l 是任意可分图;当tȡ2或t =0,或者t =1,s ȡ3,b 1=b 2= =b s ,t +s ȡl +2时,图S ▷◁P l 均不是任意可分图.关键词:任意可分图;乘积图;似星树;可迹图中图分类号:O 157.5 文献标志码:A 文章编号:1671-5489(2021)03-0525-06A r b i t r a r i l y P a r t i t i o n a b l eP r o d u c tG r a pho f S t a r -L i k eT r e e a n dP a t hZ H A N GP a n p a n ,L I U F e n g x i a ,M E N GJ i x i a n g(C o l l e g e o f M a t h e m a t i c s a n dS y s t e mS c i e n c e ,X i n j i a n g U n i v e r s i t y ,U r u m qi 830046,C h i n a )A b s t r a c t :L e t S =S (a 1,a 2, ,a t ,b 1,b 2, ,b s )b eas t a r -l i k et r e e ,w h e r e a i i so d d ,b j ise v e nf o r 1ɤi ɤt ,1ɤj ɤs .F i r s t l y ,u n d e rd i f f e r e n tv a l u e so f t a n d s ,w ed i s c u s sw h e t h e r t h e p r o d u c t g r a p h S ▷◁P l o f a s t a r -l i k e t r e e S a n da p a t h P l i s a r b i t r a r i l yp a r t i t i o n a b l e g r a p h .W e g i v e s o m e s u f f i c i e n t c o n d i t i o n s f o r S s u c ht h a t S ▷◁P l isn o ta r b i t r a r i l yp a r t i t i o n a b l e g r a p h b y c o n t r a d i c t i o na n dt h e m e t h o do f g r a p h s w i t h o u t p e r f e c t m a t c h i n g .S e c o n d l y ,b y a n a l y z i n g t h e H a m i l t o n i a n p r o p e r t y o f g r a p h s S ▷◁P l a n d u s i n g a r b i t r a r y p a r t i t i o n o f s t a r -l i k e t r e e s ,w e g i v e s o m e s u f f i c i e n t c o n d i t i o n s f o r S s u c h t h a t S ▷◁P l i sa r b i t r a r i l yp a r t i t i o n a b l e g r a p h .T h er e s u l t ss h o wt h a t i f t =1a n d s ɤ2,t h e n S ▷◁P l i s a r b i t r a r i l yp a r t i t i o n a b l e g r a p h ;i f t ȡ2o r t =0,o r t =1,s ȡ3,b 1=b 2= =b s ,t +s ȡl +2,t h e n S ▷◁P l is n o t a r b i t r a r i l yp a r t i t i o n a b l e g r a p h .K e y w o r d s :a r b i t r a r i l yp a r t i t i o n a b l e g r a p h ;p r o d u c t g r a p h ;s t a r -l i k e t r e e ;t r a c e a b l e g r a p h 收稿日期:2020-10-07.第一作者简介:张盼盼(1994 ),女,汉族,硕士研究生,从事图论及其应用的研究,E -m a i l :z p p s h e @163.c o m.通信作者简介:刘凤霞(1981 ),女,汉族,博士,副教授,从事图论及其应用的研究,E -m a i l :x ju l f x @163.c o m.基金项目:国家自然科学基金(批准号:11961067).1 引言与预备知识设图G =(V ,E )是阶为n 的简单图,正整数序列λ=(λ1,λ2, ,λp )是一个非递减序列.如果λ1+λ2+ +λp =n ,则称λ是G 的可允许序列.如果λ是一个可允许序列,且存在对点集V 的一个划分(V 1,V 2, ,V p ),使得每个V i 导出一个阶为λi 的G 的连通子图,则称λ是G 的可实现序列,且(V 1,V 2, ,V p )是序列λ在G 中的实现,每个子图G [V i ]称为图G 的λi 分支.如果每个可允许序列都是可实现的,则称G 是任意可分图(简称A P 图或A V D 图)[1].如果图G 含一条H a m i l t o n 路,则称图G 为可迹图.显然,每个可迹图都是任意可分图.当图G 的阶为偶数时,G 有完美匹配等价于序列(2,2, ,2)是G 的可实现序列;当图G 的阶为奇数时,G 有几乎完美匹配等价于序列(1,2, ,2)是G 的可实现序列.因此,任意可分图一定有完美匹配或几乎完美匹配,从而一个图有完美匹配或者几乎完美匹配的必要条件是该图为任意可分图.如果图G 的生成树是任意可分图,则图G 是任意可分图.H o r ň췍k 等[2]证明了如果树T 是任意可分的,则T 的最大度至多为6,并且提出了任意可分树的最大度至多为4的猜想.该猜想被B a r t h 等[3]证明,得到了任意可分树的最大度至多为4,且每个4度顶点与一个叶子点相邻的结论.C i c h a c z 等[4]刻画了4个叶子点的毛毛虫树的任意可分性,并展示了最大度为3或4的两类任意可分树.M a r c z yk [5]证明了对阶为n 的连通图G ,当独立数至多为n /2,且任意一对不相邻顶点的度和至少为n -3时,图G 是任意可分图或者同构于两个例外图.H o r ň췍k 等[6]证明了对阶数n ȡ20的连通图G ,任意两个不相邻顶点的度和至少为n -5,则G 有完美匹配或几乎完美匹配.B a u d o n 等[7]提出了任意可分图和可迹图的笛卡尔积图是任意可分图的猜想,证明了可迹图的顶点数至多为4时猜想成立,并证明了当两个任意可分图中至少有一个阶数至多为4时,这两个任意可分图的笛卡尔积图也是任意可分图.文献[8]证明了树T 的最大度至多为l +1时,如果T 中有一条包含所有(l +1)度顶点的路,则T ѲC l 是任意可分图.此外,文献[9-11]研究了树的笛卡尔积图的相关性质.本文将两个图G 和H 的乘积图记为G ▷◁H ,其顶点集V (G ▷◁H )={(g ,h )g ɪV (G )且h ɪV (H )},边集E (G ▷◁H )={(g ,h )(g ᶄ,h ᶄ)g g ᶄɪE (G )且h h ᶄɪE (H )或g gᶄɪE (G )且h =h ᶄ}. 用S =S (a 1,a 2, ,a t ,b 1,b 2, ,b s )表示最大度为t +s 的似星树,设d (v )=t +s ,则S -{v }=P a 1ɣP a 2ɣ ɣP a t ɣP b 1ɣP b 2ɣ ɣP b s ,其中P a i =v i 1v i 2 v i a i ,P b j =v (t +j )1v (t +j )2 v (t +j )b j ,且a i (1ɤi ɤt )是奇数,b j (1ɤj ɤs )是偶数,a 1ɤa 2ɤ ɤa t , b 1ɤb 2ɤ ɤb s , V (S )=1+ðt i =1a i +ðsj =1b j .本文给出在t 和s 的不同取值下,乘积图S ▷◁P l 的任意可分性.2 主要结果设S =S (a 1,a 2, ,a t ,b 1,b 2, ,b s )是最大度为t +s 的似星树,假设t +s ȡ2.设G =S ▷◁P l ,其中P l =l ȡ2,图S p是S 在G 中的第p 个拷贝,其对应的点集为v p ɣ{v p i j 1ɤi ɤt +s ,1ɤj ɤm a x 0ɤq ɤt ,0ɤg ɤs {a q ,b g }},其中v p 是S p 的最大度点.似星树S (a ,b ,c )是阶为1+a +b +c ,由一个3度顶点连接3条长分别为a ,b ,c 的不交路的图.本文将序列(λ1, ,λ1, ,λp , ,λp )记为((λ1)k 1, ,(λp )k p ),对i ɪ{1,2, ,p },λi 出现k i 次.两个正整数a 和b 的最大公因子记为gc d (a ,b ).命题1 对于图G 及其可允许序列λ=(λ1,λ2, ,λp ),存在(V 1,V 2, ,V m ),满足V 1=λ1, V 2=λ2, , V m =λm ,且G [V j ]连通,其中1ɤj ɤm ,如果V -V 1-V 2- -V m =V 0,G [V 0]有一条H a m i l t o n 路,则必存在V m +1,V m +2, ,V p ,满足V i =λi 且G [V i ]连通,其中m +1ɤi ɤp .因此,图G 的可允许序列λ=(λ1,λ2, ,λp )是可实现的.引理1(T u t t e ’s 定理)[12] 设图G 是阶为偶数的连通图,则图G 有完美匹配当且仅当对所有的点子集S ⊂V ,均有o (G -S )ɤS .引理2[13] 设图G 是阶为奇数的连通图,则图G 有几乎完美匹配当且仅当对所有的点子集S ⊂V ,625 吉林大学学报(理学版) 第59卷均有o (G -S )ɤS +1.引理3[1,14] 设图G 是似星树S (1,a ,b ),且1ɤa ɤb ,则图G 是任意可分图当且仅当gc d (a +1,b +1)=1. 定理1 设S =S (a 1,a 2, ,a t ,b 1,b 2, ,b s )是似星树,其中t ȡ2,则图S ▷◁P l 不是任意可分图.证明:设G =S ▷◁P l ,为证明图G 不是任意可分图,只需找到一个不可实现的序列,下面证明图G 不含完美匹配或几乎完美匹配.取G 的独立集I ={v i ,v ir j i =1,2, ,l ;r =1,2, ,t ;j 是所有小于a r 的偶数},图G -I 的奇分支数为o (G -I ),如图1(A )所示.设m =a 1+a 2+ +a t ,S i是S 在图G 中的第i 个拷贝,则有I (S i)=a 1-1+a 2-1+ +a t -12+1=m -t +22,I =(m -t +2)l 2,o (S i -I (S i))=m +1-m -t +22=m +t 2,o (G -I )=(m +t )l 2,o (G -I )-I =(t -1)l . 因为t ȡ2,则o (G -I )-I ȡ2.由引理1和引理2知,图G 不含完美匹配或几乎完美匹配.因此,图G 不是任意可分图.定理2 设S =S (a 1,a 2, ,a t ,b 1,b 2, ,b s )是似星树,其中t =0,则图S ▷◁P l 不是任意可分图.证明:设G =S ▷◁P l ,由t+s ȡ2,t =0知s ȡ2,与定理1的证明类似.令图G 的独立集I ={v ir j i =1,2, ,l ;r =t +1,t +2, ,t +s ;j 是所有小于b r -t 的奇数},o (G -I )是图G -I 的奇分支数,如图1(B )所示.设m =b 1+b 2+ +b s ,S i是S 在图G 中的第i 个拷贝.显然,G -I 是孤立点,则有I =m l 2,o (G -I )=m l 2+l,o (G -I )-I =l ȡ2.由引理1和引理2知,图G 不含完美匹配或几乎完美匹配.因此,图G 不是任意可分图.定理1和定理2分别讨论了t ȡ2和t =0的情形,下面讨论t =1的情形.定理3 设S =S (a 1,a 2, ,a t ,b 1,b 2, ,b s )是似星树,其中t =1,s =1,则图S ▷◁P l 是任意可分图.图1 图G 的拷贝S iF i g .1 C o p y S ii n g r a ph G 图2 图S (a 1,b 1)▷◁P l (l 为偶数)F i g .2 G r a ph S (a 1,b 1)▷◁P l (l i s e v e n )证明:设G =S ▷◁P l ,当l 为偶数时,可找到图G 中的一条Ha m i l t o n 路P ,如图2所示,即725 第3期 张盼盼,等:似星树与路的乘积图的任意可分性P =v 12b 1v 22(b 1-1)v 32b 1v 42(b 1-1) v l -32b 1v l -22(b 1-1)v l -12b 1v l 2(b 1-1)v l 2b 1v l -12(b 1-1)v l -22b 1v l -32(b 1-1) v 42b 1v 32(b 1-1)v 22b 1v 12(b 1-1)v 12(b 1-2) v 122v 221v 322v 421 v l -322v l -221v l -122v l 21v l 22v l -121v l -222v l -321 v 422v 321v 222v 121v 1v 211v 3v 411 v l -3v l -211v l -1v l 11v l v l -111v l -2v l -311 v 4v 311v 2v 111v 112v 213v 312v 413v l -312v l -213v l -112v l 13v l 12v l -113v l -212v l -313 v 412v 313v 212v 113 v 11(a 1-1)v 21a 1v 31(a 1-1)v 41a 1v l -31(a 1-1)v l -21a 1v l -11(a 1-1)v l 1a 1v l 1(a 1-1)v l -11a 1v l -21(a 1-1)v l -31a 1 v 41(a 1-1)v 31a 1v 21(a 1-1)v 11a 1.当l 为奇数时,同理可找到图G 中的一条H a m i l t o n 路.因此,图G 是任意可分图.定理4 设S =S (a 1,a 2, ,a t ,b 1,b 2, ,b s )是似星树,其中t =1,s =2,即S =S (a 1,b 1,b 2),则图S ▷◁P l 是任意可分图.证明:下面仅讨论l 为奇数的情形,当l 为偶数时同理可证.令P 3=v 13b 2v 23(b 2-1)v 33b 2v 43(b 2-1) v l -33(b 2-1)v l -23b 2v l -13(b 2-1)v l 3b 2v l 3(b 2-1)v l -13b 2v l -23(b 2-1)v l -33b 2v 43b 2v 33(b 2-1)v 23b 2v 13(b 2-1) v 132v 231v 332v 431 v l -331v l -232v l -131v l 32v l 31v l -132v l -231v l -332 v 432v 331v 232v 131. 1)如图3所示,a 1=1.此时,设P l 21=v l 21v l -122v l -221v l -322 v 422v 321v 222v 121v 122v 221v 322v 421 v l -321v l -222v l -121v l 22 v l 2(b 1-1)v l -12b 1v l -22(b 1-1)v l -32b 1v 42b 1v 32(b 1-1)v 22b 1v 12(b 1-1)v 12b 1v 22(b 1-1)v 32b 1v 42(b 1-1) v l -32(b 1-1)v l -22b 1v l -12(b 1-1)v l 2b 1,则P *=P 3v 1v 111v 2v 211v 3v 311 v l -3v l -311v l -2v l -211vl -1.将P *反方向的路记为P ᶄ*,即从点vl -1开始的路.图3 图S (1,b 1,b 2)▷◁P lF i g .3G r a ph S (1,b 1,b 2)▷◁P l 设G =S ▷◁P l ,假设序列λ=(λ1,λ2, ,λp )是图G 的可允许序列.下面说明λ是可实现的.若对某个集合I ⊆{1,2, ,p },有ði ɪI λi=P *,则图G -P *包含一个同构于似星树S (1,1,b 1l )的生成子图.因为b 1l 是偶数,则g c d (2,b 1l +1)=1.由引理3,似星树S (1,1,b 1l )是任意可分图.因此,由命题1,序列λ在图G 中是可实现的.若对任意的集合I ⊆{1,2, ,p },有ði ɪI λiʂP *,则存在某个I ,使得ði ɪI λi<P *且ði ɪI λi+λj >P *,其中j ɪ{1,2, ,p }\I .令V r =r =P *-ði ɪI λi ,显然r <λj .不失一般性,令V r ⊂V j .①当r =1时,令V r ={v l -1}.当λj =2时,令V j ={v l -111}ɣV r ,图G -ði ɪI V i -V j 包含一条生成路v l 11v l P l 21.当λj ȡ3时,令V r ɣ{v l -111,v l 11}⊆V j .因为v l -1v l 11ɪE (G ),从路v l 11v l P l21上依次取点给V j ,图G -ði ɪI V i -V j 包含路v lPl21上的一条生成路.②当r ȡ2时,从路P ᶄ*上依次取r 个点给V r .类似①的讨论,可得G -ði ɪI V i -V j 包含一条路.825 吉林大学学报(理学版) 第59卷因此,序列λ是图G 的可实现序列.2)如图4所示,a 1ȡ3.此时,令P 121=v 121v 222v 321v 422 v l -322v l -221v l -122v l 21v l 22v l -121v l -222v l -321 v 421v 322v 221v 122v 123 v 12(b 1-1)v 22b 1v 32(b 1-1)v 42b 1v l -32b 1v l -22(b 1-1)v l -12b 1v l 2(b 1-1)v l 2b 1v l -12(b 1-1)v l -22b 1v l -32(b 1-1) v 42(b 1-1)v 32b 1v 22(b 1-1)v 12b 1,P 2=v l 1a 1v l 1(a 1-1)v l 1(a 1-2)v l -11(a 1-3)v l -21(a 1-2)v l -31(a 1-3)v l -41(a 1-2) v 41(a 1-3)v 31(a 1-2)v 21(a 1-3)v 21(a 1-2)v 31(a 1-3)v 41(a 1-2) v l -31(a 1-2)v l -21(a 1-3)v l -11(a 1-2)v l 1(a 1-3)v l 1(a 1-4)v l -11(a 1-5)v l -21(a 1-4)v l -31(a 1-5) v l 13v l -112v l -213v l -312 v 513v 412v 313v 212v 213v 312v 413v 512 v l -313v l -212v l -113v l 12v l 11v l v l -111v l -1 v 211v 2P 121,P *=P 3v 1v 111v 112 v 11(a 1-1)v 11a 1v 21(a 1-1)v 21a 1v 31(a 1-1)v 31a 1 v l -21(a 1-1)v l -21a 1v l -11(a 1-1).此外,将P *反方向的路记为P ᶄ*,即从v l -11(a 1-1)开始的一条路.图4 图S (a 1,b 1,b 2)▷◁P lF i g .4G r a ph S (a 1,b 1,b 2)▷◁P l 若对某个集合I ⊆{1,2, ,p },有ði ɪI λi=P *,则图G -P *包含一个同构于似星树S (1,1,b 1l +(a 1-1)(l -1))的生成子图.因为b 1l +(a 1-1)(l -1)是偶数,则g c d (2,b 1l +(a 1-1)(l -1)+1)=1.由引理3,似星树S (1,1,b 1l +(a 1-1)(l -1))是任意可分图.因此,序列λ在图G 中是可实现的.若对任意的集合I ⊆{1,2, ,p },有ði ɪI λiʂP *.类似于1)中对r 的假设,从路P *上的点v l -11(a 1-1)处依次取r 个点给V r .不失一般性,令V r ⊂V j .①当r =1时,令V r ={v l -1(a 1-1)}.此时,若λj =2,则令V j ={v l -11a 1}ɣV r ,图G -ði ɪI V i -V j 包含一条生成路P 2.若λj ȡ3,因为v l -11(a 1-1)v l 1a 1ɪE (G ),则令V r ɣ{vl -11a 1,v l1a 1}⊆V j ,从路P 2上的点v l1a 1处依次取点给V j .②当r ȡ2时,从路P ᶄ*上的点v l -11(a 1-1)处依次取r 个点给V r .类似于1)中②的讨论,可得图G -ði ɪI V i -V j 包含一条路.因此,序列λ是图G 的可实现序列.定理5 设S =S (a 1,a 2, ,a t ,b 1,b 2, ,b s )是似星树,其中t =1,s ȡ3,且Δ(S )ȡl +2.如果b 1=b 2= =b s ,则图S ▷◁P l 不是任意可分图.证明:设G =S ▷◁P l ,G =n ,Δ(S )=k .令q =b 1=b 2= =b s 且b =q l ,则n =(k -1)b +(a 1+1)l .考虑到图G -{v 1,v 2, ,v l }连通分支的阶为a 1l 和b ,下面分两种情形讨论.1)若a 1<b 1,则a 1l <b .设λ=((b +1)l,c )是G 的可允许序列,其中c =n -l (b +1)=(k -1)b +a 1l -b l >a 1l .925 第3期 张盼盼,等:似星树与路的乘积图的任意可分性035吉林大学学报(理学版)第59卷若λ是G的可实现序列,则每个b+1分支必须包含一个点v i,iɪ{1,2, ,l}.因为cȡa1l+1,故c分支必包含一个点v i,iɪ{1,2, ,l},共需(l+1)个点,与l={v i i=1,2, ,l}矛盾.2)若a1>b1,则如果k=l+2,可考虑G的可允许序列λ=((b+1)l,a1l+1,c),其中c=b-1.如果k>l+2,可考虑G的可允许序列λ=((b+1)l+1,a1l+1,c),其中c=(k-l-2)b-2.在这两种情形下,每个b+1分支必包含一个点v i,iɪ{1,2, ,l},每个a1l+1分支也必包含一个点v i,iɪ{1,2, ,l},与l={v i i=1,2, ,l}矛盾,故λ不是G的可实现序列,图S▷◁P l不是任意可分图.参考文献[1] B A R T H D,B A U D O N O,P U E C HJ.D e c o m p o s a b l eT r e e s:A P o l y n o m i a lA l g o r i t h mf o rT r i p o d s[J].D i s c r e t eA p p lM a t h,2002,119(3):205-216.[2] HO R㊅NÁK M,WO Z'N I A K M.A r b i t r a r i l y V e r t e xD e c o m p o s a b l eT r e e sA r e o fM a x i m u m D e g r e e a tM o s t S i x[J].O p u s c u l aM a t h,2003,23:49-62.[3] B A R T H D,F O U R N I E R H.A D e g r e e B o u n do n D e c o m p o s a b l e T r e e s[J].D i s c r e t e M a t h,2006,306(5):469-477.[4] C I C HA C ZS,GÖR L I C H A,MA R C Z Y K A,e t a l.A r b i t r a r i l y V e r t e xD e c o m p o s a b l eC a t e r p i l l a r sw i t hF o u ro rF i v eL e a v e s[J].D i s c u s sM a t h:G r a p hT h e o r y,2006,26(2):291-305.[5] MA R C Z Y K A.A N o t e o nA r b i t r a r i l y V e r t e xD e c o m p o s a b l eG r a p h s[J].O p u s c u l aM a t h,2006,26(1):109-118.[6] HO R㊅NÁK M,MA R C Z Y K A,S C H I E R M E Y E RI,e t a l.D e n s eA r b i t r a r i l y V e r t e xD e c o m p o s a b l eG r a p h s[J].G r a p h sC o m b i n,2012,28(6):807-821.[7] B A U D O N O,B E N S MA I LJ,K A L I N OW S K IR,e t a l.O nt h eC a r t e s i a nP r o d u c t o f a nA r b i t r a r i l y P a r t i t i o n a b l eG r a p ha n daT r a c e a b l eG r a p h[J].D i s c r e t eM a t hT h e o rC o m p u t S c i,2014,16(1):225-232.[8] L I U FX,WUBY,M E N GJX.P a r t i t i o n i n g t h eC a r t e s i a nP r o d u c t o f aT r e e a n dC y c l e[J].A p p lM a t hC o m p u t,2018,332:90-95.[9] T I A NJ,X U K X,K L A V㊅Z A RS.T h eG e n e r a l P o s i t i o nN u m b e r o f t h eC a r t e s i a nP r o d u c t o fT w oT r e e s[J/O L].B u l l e t i nA u s t r a l i a n M a t hS o c,2020-09-15[2020-10-04].h t t p s://a r x i v.o r g/p d f/2009.07305v1.p d f.[10] B A L A K R I S HN A N R,R A JSF,K A V A S K A R T.b-C o l o r i n g o fC a r t e s i a nP r o d u c to fT r e e s[J].T a i w a n e s eJM a t h,2016,20(1):1-11.[11] S H I U W C,L OW R M.T h eI n t e g e r-M a g i cS p e c t r aa n d N u l lS e t so ft h e C a r t e s i a n P r o d u c to fT r e e s[J].A u s t r a l a s JC o m b i n,2018,70:157-167.[12] T U T T E W T.T h eF a c t o r i z a t i o no fL i n e a rG r a p h s[J].JL o n d o n M a t hS o c,1947,22:107-111.[13] L I U FX,WU B,M E N GJX.A r b i t r a r i l y P a r t i t i o n a b l e{2K2,C4}-F r e eG r a p h s[J/O L].D i s c u s M a t h G r a p hT h e o r y,2019-11-30[2020-01-18].h t t p s://d o i.o r g/10.7151/d m g t.2289.[14] HO R㊅N A K M,WO Z'N I A K M.O nA r b i t r a r i l y V e r t e xD e c o m p o s a b l eT r e e s[J].D i s c r e t e M a t h,2008,308(7):1268-1281.(责任编辑:赵立芹)。