三类笛卡尔积图的关联色数

图的关联色数的概念是 Brualdi和 Massey于 1 993年引入的 ,它同图的强色指数有密切的关系 .Guiduli[2 ] 说明关联色数是有向星萌度的一个特殊情况 ,迄今仅确定了某些特殊图类的关联色数 .本文给出了完全图与完全图、圈与完全图、圈与圈的笛卡尔积图的关联色数。     

有向圈的笛卡尔积有向图的双控制数

Let γ*(D) denote the twin domination number of digraph D and let Cm Cn denote the Cartesian product of C_m and C_n, the directed cycles of length m, n ≥ 2. In this paper, we determine the exact values: γ*(C_2?C_n) = n; γ*(C_3 ?C_n) = n if n ≡ 0(mod 3),otherwise, γ*(C_3?C_n) = n + 1; γ*(C_4?C_n) = n + n/2 if n ≡ 0, 3, 5(mod 8), otherwise,γ*(C_4?C_n) = n + n/2 + 1; γ*(C_5?C_n) = 2n; γ*(C_6?C_n) = 2n if n ≡ 0(mod 3), otherwise,γ*(C_6?C_n) = 2n + 2.     

交叉数为2的笛卡尔积图

图G的交叉数,记作cr(G),是把G画在平面上的所有画法中边与边产生交叉的最小数目,它是拓扑图论中的一个热点问题。Kle?c和Petrillová刻画了当G₁为圈且cr(G₁G₂)-2时,因子图G₁和G₂满足的充要条件。在此基础上,本文研究当|V(G₁)|≥3且cr(G₁G₂)=2时,G₁和G₂应满足的充要条件。     

交叉数为2且因子图为路的笛卡尔积图

M.Kle??和J.Petrillová刻画了当G1为圈且cr (G1G2)=2时,因子图G1和G2所满足的充要条件.在此基础上,该文进一步刻画了在cr (G1G2)=2的前提下,当G1=P4,或者G1=P3且△(G2)=4时,因子图G2应满足的充要条件.     

笛卡尔积K_(1,1,2,2)×P_n的交叉数

已经确定了的六个顶点的图与路、星和圈的笛卡尔积的交叉数为数不多,作者们继续深化这方面的研究,确定了K1,1,2,2与路Pn的笛卡尔积的交叉数为9n-1.     

循环图C(10,2)与路P_n的笛卡尔积的交叉数

证明了循环图C(10,2)与路P_n的笛卡尔积的交叉数是10n及循环图C(2m,2)的一点悬挂和两点悬挂的交叉数分别是m,2m.     

循环图C(12,2)与路P_n的笛卡尔积的交叉数

循环图C(m,2)表示由圈Cm(v_1v_2…v_mv_1)增加边v_iv_i+2(i=1,2,…,m,i+2(modm))所得到的图,本文证明了循环图C(12,2)与路P_n的笛卡尔积的交叉数是12n.     

一个六阶3-连通图与路Pn的笛卡尔积的交叉数

C(6,2)表示由圈C6增加边vivi 2(i=1,…,6,i 2(m od6))所得的图,把边vivi 2叫做C(6,2)的弦,B表示C(6,2)除去一条弦所得到的图,我们确定了B与Pn笛卡尔积的交叉数为5n-1.     

泊松图P(4,1)与路Pn的笛卡尔积的交叉数

泊松图$P(m, 1)$与路$P_n$的笛卡尔积的交叉数是一个NP-完全问题, Y.H. Peng和Y.C.Yiew 证明了$P(3,1)$与$P_n$的笛卡尔积的交叉数为$4n$, 我们证明明了$P(4,1)$与$P_n$的笛卡尔积的交叉数为$8n$.     

交叉积的同调维数

本文证明了当Ｈ是有限维半单和余半单的Ｈｏｐｆ代数时,Ｒ与交叉积Ｒ＃σＨ的整体维数是相同的;同时,它们的弱维数也是相同的．     

A note on the partition dimension of Cartesian product graphs

Let G = (V, E) be a connected graph. The distance between two vertices u, v ∈ V, denoted by d(u, v), is the length of a shortest u − v path in G. The distance between a vertex v ∈ V and a subset P ⊂ V is defined as , and it is denoted by d(v, P). An ordered partition {P₁, P₂, … , P_t} of vertices of a graph G, is a resolving partition of G, if all the distance vectors (d(v, P₁), d(v, P₂), … , d(v, P_t)) are different. The partition dimension of G, denoted by pd(G), is the minimum number of sets in any resolving partition of G. In this article we study the partition dimension of Cartesian product graphs. More precisely, we show that for all pairs of connected graphs G, H, pd(G × H) ? pd(G) + pd(H) and pd(G × H) ? pd(G) + dim(H), where dim(H) denotes the metric dimension of H. Consequently, we show that pd(G × H) ? dim(G) + dim(H) + 1.     

图和有向图的测地数

对于图G（或者有向图D）内的任意两点u和υ,u-υ测地线是指在u和υ之间的最短路（或者从u到υ）.I（u,υ）表示位于一条u-υ测地线上所有点的集合,对于S（U∣）V（G）,I（S）表示所有I（u,υ）的并,这里u,υ∈S.图G（或者有向图D）的测地数g（G）（g（D））是使J（S）=V（G）（J（S）=V（D））的最小点集S的基数.定义G的所有定向图中测地数的最小值为G的下测地数,即g-（G）=min{g（D）：D是G的定向图）;定义G的所有定向图中测地数的最大值为G的上测地数,即g＋（G）=max{g（D）：D是G的定向图）.本文的主要目的是研究G V H 的上、下测地数,此外,文章给出了g（G）=g（G×P3）的一个充分必要条件.     

Cartesian products of directed graphs with loops

We show that every nontrivial finite or infinite connected directed graph with loops and at least one vertex without a loop is uniquely representable as a Cartesian or weak Cartesian product of prime graphs. For finite graphs the factorization can be computed in linear time and space.     

Packing dimension and Cartesian products

We show that for any analytic set in , its packing dimension can be represented as , where the supremum is over all compact sets in , and denotes Hausdorff dimension. (The lower bound on packing dimension was proved by Tricot in 1982.) Moreover, the supremum above is attained, at least if . In contrast, we show that the dual quantity , is at least the ``lower packing dimension' of , but can be strictly greater. (The lower packing dimension is greater than or equal to the Hausdorff dimension.)

     

有限偏序集的Cartesian积的收缩

通过对有限偏序集的Cartesian积的收缩的考查,证明了Plotkin在1978年提出的一个猜想,并部分回答了Mislove和Lawson在"Open Problems in Topology"中提出的一个公开问题.     

图的笛卡儿积的测地数

对于图G内的任意两点u和v，u-v测地线是指u和v之间的最短路．I（u，v）表示位于u-v测地线上所有点的集合，对于．S∈V（G），I（S）表示所有I（u，v）的并，这里“u,v∈．S．G的测地数g（G）是使I（S）=V（G）的点集．S的最小基数．在这篇文章，我们研究G×K3的测地数和g（G）与g（G×K3）相等的充分必要条件，还给出了T×Km和Cn×Km的测地数，这里T是树．     

反超图的笛卡儿积的上色数

讨论反超图的笛卡儿积的着色理论 ,求出了满足一定条件的反超图的笛卡儿积的上色数 .     

笛卡尔乘积图的圈点连通度

图G的圈点连通度,记为κ_c(G),是所有圈点割中最小的数目,其中每个圈点割S满足G-S不连通且至少它的两个分支含圈.这篇文章中给出了两个连通图的笛卡尔乘积的圈点连通度:(1)如果G_1≌K_m且G_2≌K_n,则κ_c(G_1×G_2)=min{3m+n-6,m+3n-6},其中m+n≥8,m≥n+2,或n≥m+2,且κ_c(G_1×G_2)=2m+2n-8,其中m+n≥8,m=n,或n=m+1,或m=n+11;(2)如果G_1≌K_m(m≥3)且G_2■K_n,则min{3m+κ(G_2)-4,m+3κ(G_2)-3,2m+2κ(G_2)-4}≤κ_c(G_1×G_2)≤mκ(G2);(3)如果G_1■K_m,K_(1,m-1)且G_2■K_n,K_(1,n-1),其中m≥4,n≥4,则min{3κ(G_1)+κ(G_2)-1,κ(G_1)+3κ(G_2)-1,2_κ(G_1)+2_κ(G_2)-2}≤κ_c(G_1×G_2)≤min{mκ(G_2),nκ(G_1),2m+2n-8}.     

笛卡尔乘积图里的最小k-路点覆盖

对于子集$S\subseteq V(G)$,如果图$G$里的每一条$k$路都至少包含$S$中的一个点,那么我们称集合$S$是图$G$的一个$k$-路点覆盖.很明显,这个子集并不唯一.我们称最小的$k$-路点覆盖的基数为$k$-路点覆盖数, 记作$\psi_k(G)$.本文给出了一些笛卡尔乘积图上$\psi_k(G)$值的上界或下界.