积图的道路正性

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

星样树与路的笛卡尔积图的任意可分性

一个图G称为是任意可分的(简记AP),如果对于正整数|V(G)|的任一满足∑p i=1 ni=|V(G)|的划分τ=(n1,n2,⋯,np),总是存在顶点集V的一个划分(V1,V2,⋯,Vp)满足|Vi|=ni,i=1,2,⋯,p,使得每个Vi导出的图是图G的一个连通子图.记S(a1,a2,⋯,at,b1,b2,⋯,bl)是最大度Δ(S)=t+l的星样树,其中ai是奇数,bj是偶数且a1≤a2≤⋯≤at,b1≤b2≤⋯≤bl.我们证明了对于一个大于等于2的偶数n,当Δ(S)≤n+1时,如果t≤2,或t≥3且a3>1,则笛卡尔积图S◻Pn是AP的.对于一个大于2的奇数n,如果Δ(S)≤n+1且t≤2,则S◻Pn是AP的;如果Δ(S)≤n+1且t≥3,则S◻Pn不是AP的.

星图Sm与路Pn的笛卡尔积的2-页交叉数

一个图的2-页交叉数是最小的t使得这个图在2-页书上有一个交叉点数为t的好的画法.星图Sm与路Pn的笛卡尔积的2-页交叉数被证明为(n-1)[m2][m-12],其中m≥1且n≥1.

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.