有向笛卡尔积图的有向度量维数(英文)

设D是一个有向图,w={w_1,w_2,…,w_k}是D的一个有序点子集,v是D中任意一点。我们把有序k元素组r(v|w)=(d(v,w_1),d(v,w_2),…,d(v,w_k))称为点v对于W的(有向距离)表示。如果在D中,任意两个不同的点u和v对W的(有向距离)表示都不相同,则称W是有向图D的一个分解集。我们把D的最小分解集的基数称为有向图D的有向度量维数,并用dim(D)来表示。本文研究了有向笛卡尔积图D_1×D_2的有向度量维数。设P_m和C_m分别是长为m的有向路和有向圈。在文中我们分别给出了dim(D_1×D_2)的一个下界与dim(D×P_m)和dim(D×C_m)的上界,并通过确定dim(P_m×P_n),dim(C_m×P_n)和dim(C_m×C_n)的精确值说明了我们给出的上界是紧的。     

完全有向图的奇长圈覆盖

设DK_v表示完全有向对称图,C（v,m）表示覆盖DK_v的m长有向圈的最小圈数（称为覆盖数）.对任意正整数m和v,当m≤v≤m+6时,覆盖数C（v,m） 被确定.     

具有最小弧数的唯一泛圈有向图的计数

唯一泛圈有向图D是一个定向图,对每一个n,3≤n≤υ,D中有且只有一个长为n的有向圈.用g(υ)表示具有υ个顶点的唯一泛圈有向图最小可能的弧数,用N(υ)表示具有υ个顶点、g(υ)条弧且互不同构的唯一泛圈有向图的个数.确定了当υ=3,4,5,6,7,8时的N(υ).     

笛卡尔乘积图的成对控制

Let γpr（G） denote the paired domination number and G □ H denote the Cartesian product of graphs G and H. In this paper we show that for all graphs G and H without isolated vertex, γpr（G）γpr（H）≤ 7γpr （G □H）.     

关于图的反符号圈控制数

本文研究了图的反符号圈控制的问题.利用分类和反证的方法,获得了满足反符号圈控制数为负边数加4的连通图的刻画和完全二部分图的反符号圈控制数.     

有向圈的SD计算方法

阐述了将有向图转化为流图的算法,将系统动力学(System Dynamic,记为SD)与图论相结合,得到计算有向圈的新方法,并给出了算例.     

若干笛卡尔积图的邻点可区别E-全染色

图G(V,E)的k是一个正整数,f是V(G)∪E(G)到{1,2,…,k}的一个映射,如果u,v∈V(G),则f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),C(u)≠C(v),称f是图G的邻点可区别E-全染色,称最小的数k为图G的邻点可区别E-全色数.得到了Pm×Pn,Pm×Cn,Cm×Cn的邻点可区别E-全色数,其中C(u)={f(u)}∪{f(uv)uv∈E(G)}.     

交叉数为2的笛卡尔积图

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

图的强符号圈控制数

本文研究了图的强符号圈控制数γ′_(ssc)(G).利用最大独立集最大匹配等方法,刻画了满足γ′_(ssc)(G)=|E|-2的所有连通图,给出了γ′_(ssc)(G)的一个下界,求出了两类特殊图的强符号圈控制数.     

有向圈的行列式算法及HAMILTON图条件

本文引入有向路乘法、弧行列式等概念 ,讨论了弧行列式的性质 ,阐述了二种计算有向圈的行列式方法及有向图 D为 Hamilton图的充要条件 ,最后给出了计算实例     

The Twin Domination Numb er of Strong Pro duct of Digraphs

Let γ*(D) denote the twin domination number of digraph D and let D_1  D_2 denote the strong product of D_1 and D_2. In this paper, we obtain that the twin domination number of strong product of two directed cycles of length at least 2.Furthermore, we give a lower bound of the twin domination number of strong product of two digraphs, and prove that the twin domination number of strong product of the complete digraph and any digraph D equals the twin domination number of D.     

乘积图的Fractional控制

Let G =(V,E) be a simple graph.For any real function g :V-→ R and a subset S V,we write g(S) =∑v∈Sg(v).A function f :V-→ [0,1] is said to be a fractional dominating function(F DF) of G if f(N [v]) ≥ 1 holds for every vertex v ∈ V(G).The fractional domination number γf(G) of G is defined as γf(G) = min{f(V)|f is an F DF of G }.The fractional total dominating function f is defined just as the fractional dominating function,the difference being that f(N(v)) ≥ 1 instead of f(N [v]) ≥ 1.The fractional total domination number γ0f(G) of G is analogous.In this note we give the exact values ofγf(Cm × Pn) and γ0f(Cm × Pn) for all integers m ≥ 3 and n ≥ 2.     

Domination of generalized Cartesian products

The generalized prism πG of G is the graph consisting of two copies of G, with edges between the copies determined by a permutation π acting on the vertices of G. We define a generalized Cartesian product that corresponds to the Cartesian product when π is the identity, and the generalized prism when H is the graph K₂. Burger, Mynhardt and Weakley [A.P. Burger, C.M. Mynhardt, W.D. Weakley, On the domination number of prisms of graphs, Discuss. Math. Graph Theory 24 (2) (2004) 303-318.] characterized universal doublers, i.e. graphs for which γ(πG)=2γ(G) for any π. In general for any n≥2 and permutation π, and a graph attaining equality in this upper bound for all π is called a universal multiplier. We characterize such graphs.     

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

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

一个六阶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.     

Hadwiger Number and the Cartesian Product of Graphs

The Hadwiger number η(G) of a graph G is the largest integer n for which the complete graph K _n on n vertices is a minor of G. Hadwiger conjectured that for every graph G, η(G) ≥ χ(G), where χ(G) is the chromatic number of G. In this paper, we study the Hadwiger number of the Cartesian product of graphs. As the main result of this paper, we prove that for any two graphs G ₁ and G ₂ with η(G ₁) = h and η(G ₂) = l. We show that the above lower bound is asymptotically best possible when h ≥ l. This asymptotically settles a question of Z. Miller (1978). As consequences of our main result, we show the following:

控制数与星独立数

本文，我们讨论星独立数、分数星独立数、分数控制数和控制数间的关系，利用规划理论给出了上述参数的一些性质。     

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

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