P_m和P_n的强直积的强边染色

研究2条路P_m和P_n的强直积P_m■P_n的强边染色问题.利用P_m■P_n子图的同构图确定其强边色数的下界,然后通过构造强边染色得到其上界,进而确定了强直积P_m■P_n的强边色数.

图的强直积的2-距离染色(英文)

设G,H是阶至少为2的简单图。图G与H的强直积是指这样一个图G□×H,其顶点集合为V(G)×V(H),并且(x1,x2)(y1,y2)∈E(G□×H)当且仅当[x1y1∈E(G)且x2y2∈E(H)]或者[x1=y1且x2y2∈E(H)]或者[x2=y2且x1y1∈E(G)]。一个图G的使用了k种颜色的2-距离染色是指一个从V(G)到{1,2,…,k}的映射f,使得任意两个不同的距离最多是2的顶点染不同的颜色。对图G进行2-距离染色所需的最少的颜色数称为图G的2-距离色数,记为χ2(G)。文中将获得两个图的强直积的2-距离色数的可达到的上界和下界:Δ(G□×H)+1≤χ2(G□×H)≤χ2(G).χ2(H)。对一些特殊图,例如Pm□×Kn,Pm□×Wn,Pm□×Sn,Pm□×Fn,Pm□×Cn(n≡0(mod3)或者n=5),给出了它们的2-距离色数。

几类积图的团染色数

设G=(V,E)为简单图,V和E分别表示图的点集和边集.图G的一个k-团染色是指点集V到色集{1,2,…,k}的一个映射,使得G的每个至少含两个点的极大团都至少有两种颜色.分别给出了任意两个图的团色数与它们通过笛卡尔积、Kronecker积、强直积或字典积运算后得到的积图的团色数之间的关系.

积图的道路正性

本文所讨论的积图是图的笛卡尔积G1×G2，目的张量积G1∧AG；，图的逻辑积G2G1和图的强直积G1·G2四种积图。证明了：（1）如果G1和G2都是连通图，则积图中笛卡尔积，逻辑积和强直积都是道路正图。（2）图的张量积G1∧G2是道路正图的是图G1和G2是一个连通图，G1或G2有一个奇圈，且其中λ1和λn分别是图G1的最大和最小特征值，μ1和μm分别是图G2的最大和最小特征值。

积图的道路正性

该文所讨论的积图是图的笛卡尔积 Ｇ１×Ｇ２，图的张量积 Ｇ１∧Ｇ２，图的逻辑积 Ｇ２Ｇ１和图的强直积 Ｇ１· Ｇ２四种积图。证明了： （１）如果 Ｇ１和 Ｇ２都是连通图，则积图中笛卡尔积，逻辑积和强直积都是道路正图。 （２）图的张量积 Ｇ１ ∧Ｇ２是道路正图的是图 Ｇ１和 Ｇ２是一个连通图，Ｇ１或 Ｇ２有一个奇圈，且其中λ１和λ 分别是图Ｇ１的最大和最小特征值。

The Path-Positive Property on the Products of Graphs

The products of graphs discussed in this paper are the following four kinds: the Cartesian product of graphs, the tensor product of graphs, the lexicographic product of graphs and the strong direct product of graphs. It is proved that:① If the graphs G 1 and G 2 are the connected graphs, then the Cartesian product, the lexicographic product and the strong direct product in the products of graphs, are the path positive graphs. ② If the tensor product is a path positive graph if and only if the graph G 1 and G 2 are the connected graphs, and the graph G 1 or G 2 has an odd cycle and max{ λ 1μ 1,λ nμ m}≥2 in which λ 1 and λ n [ or μ 1 and μ m] are maximum and minimum characteristic values of graph G 1 [ or G 2 ], respectively.