Game coloring the Cartesian product of graphs

This article proves the following result: Let G and G′ be graphs of orders n and n′, respectively. Let G^* be obtained from G by adding to each vertex a set of n′ degree 1 neighbors. If G^* has game coloring number m and G′ has acyclic chromatic number k, then the Cartesian product G□G′ has game chromatic number at most k(k + m ? 1). As a consequence, the Cartesian product of two forests has game chromatic number at most 10, and the Cartesian product of two planar graphs has game chromatic number at most 105. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 261–278, 2008     

List coloring of Cartesian products of graphs

A well-established generalization of graph coloring is the concept of list coloring. In this setting, each vertex v of a graph G is assigned a list L(v) of k colors and the goal is to find a proper coloring c of G with c(v)∈L(v). The smallest integer k for which such a coloring c exists for every choice of lists is called the list chromatic number of G and denoted by χ_l(G).We study list colorings of Cartesian products of graphs. We show that unlike in the case of ordinary colorings, the list chromatic number of the product of two graphs G and H is not bounded by the maximum of χ_l(G) and χ_l(H). On the other hand, we prove that χ_l(G×H)?min{χ_l(G)+col(H),col(G)+χ_l(H)}-1 and construct examples of graphs G and H for which our bound is tight.     

Cartesian product stabilization of 3-manifolds

The Cartesian product of a closed, orientable prime geometric 3-manifold and a closed orientable surface is unique except for the case of the Cartesian product of a special class of Seifert manifolds and a torus. The same type of uniqueness holds for stabilization of 3-manifolds by an n-dimensional torus. Cartesian squares of Seifert fibered 3-manifolds are completely classified.     

关于笛卡尔乘积图的优美性

研究了笛卡尔乘积图Pm×Pn×P1的优美标号算法,并且给出了他们都是优美图的证明,同时推广了笛卡尔乘积图Pm×Pn是优美图的结论.     

Connectivity of Cartesian product graphs

Use v_i,κ_i,λ_i,δ_i to denote order, connectivity, edge-connectivity and minimum degree of a graph G_i for i=1,2, respectively. For the connectivity and the edge-connectivity of the Cartesian product graph, up to now, the best results are κ(G₁×G₂)?κ₁+κ₂ and λ(G₁×G₂)?λ₁+λ₂. This paper improves these results by proving that κ(G₁×G₂)?min{κ₁+δ₂,κ₂+δ₁} and λ(G₁×G₂)=min{δ₁+δ₂,λ₁v₂,λ₂v₁} if G₁ and G₂ are connected undirected graphs; κ(G₁×G₂)?min{κ₁+δ₂,κ₂+δ₁,2κ₁+κ₂,2κ₂+κ₁} if G₁ and G₂ are strongly connected digraphs. These results are also generalized to the Cartesian products of connected graphs and n strongly connected digraphs, respectively.     

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

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

The Cartesian product of hypergraphs

We show that every simple, (weakly) connected, possibly directed and infinite, hypergraph has a unique prime factor decomposition with respect to the (weak) Cartesian product, even if it has infinitely many factors. This generalizes previous results for graphs and undirected hypergraphs to directed and infinite hypergraphs. The proof adopts the strategy outlined by Imrich and ?erovnik for the case of graphs and introduces the notion of diagonal‐free grids as a replacement of the chord‐free 4‐cycles that play a crucial role in the case of graphs. This leads to a generalization of relation Δ on the arc set, whose convex hull is shown to coincide with the product relation of the prime factorization. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Wielandt type theorem for Cartesian product of digraphs

We show that mn-1 is an upper bound of the exponent of the Cartesian product D×E of two digraphs D and E on m,n vertices, respectively and we prove our upper bound is extremal when (m,n)=1. We also find all D and E when the exponent of D×E is mn-1. In addition, when m=n, we prove that the extremal upper bound of exp(D×E) is n²-n+1 and only the Cartesian product, Z_n×W_n, of the directed cycle and Wielandt digraph has exponent equals to this bound.     

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

图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}.     

TWO NEW CONSTRUCTIONS OF CARTESIAN AUTHENTICATION CODES FROM SYMPLECTIC GEOMETRY

ＴＷＯＮＥＷＣＯＮＳＴＲＵＣＴＩＯＮＳＯＦＣＡＲＴＥＳＩＡＮＡＵＴＨＥＮＴＩＣＡＴＩＯＮＣＯＤＥＳＦＲＯＭＳＹＭＰＬＥＣＴＩＣＧＥＯＭＥＴＲＹＧＡＯＹＯＵＡＮＤＺＯＵＺＥＮＧＪＩＡ（ＤｅｐａｒｔｍｅｎｔｏｆＢａｓｉｃＳｃｉｅｎｃｅ，Ｎｏｒｔｈｅａｓｔ...     

路和圈上的卡氏乘积图的关联着色数(英文)

本文给出了路与路,路与圈的卡氏乘积图的关联着色数的完整刻画.对于圈与圈的卡氏乘积图的情形,也给出了其关联着色数的上界为乘积图的最大度加三,并且又给出了几类其关联着色数小于其最大度加三的圈与圈的卡氏乘积图类.     

The signed star domination numbers of the Cartesian product graphs

Let G be a graph with vertex set V(G) and edge set E(G). A function f:E(G)→{-1,1} is said to be a signed star dominating function of G if for every v∈V(G), where E_G(v)={uv∈E(G)|u∈V(G)}. The minimum of the values of , taken over all signed star dominating functions f on G, is called the signed star domination number of G and is denoted by γ_SS(G). In this paper, a sharp upper bound of γ_SS(G×H) is presented.     

The generalized hierarchical product of graphs

A generalization of both the hierarchical product and the Cartesian product of graphs is introduced and some of its properties are studied. We call it the generalized hierarchical product. In fact, the obtained graphs turn out to be subgraphs of the Cartesian product of the corresponding factors. Thus, some well-known properties of this product, such as a good connectivity, reduced mean distance, radius and diameter, simple routing algorithms and some optimal communication protocols, are inherited by the generalized hierarchical product. Besides some of these properties, in this paper we study the spectrum, the existence of Hamiltonian cycles, the chromatic number and index, and the connectivity of the generalized hierarchical product.     

The basis number of the Cartesian product of stars and wheels with different ladders

The basis number of a graph G is defined to be the least positive integer d such that G has a d-fold basis for the cycle space of G. We investigate the basis number of the cartesian product of stars and wheels with ladders, circular ladders and Möbius ladders.     

A new class of antimagic Cartesian product graphs

An antimagic labeling of a finite undirected simple graph with m edges and n vertices is a bijection from the set of edges to the integers 1,…,m such that all n-vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with the same vertex. A graph is called antimagic if it has an antimagic labeling. In 1990, Hartsfield and Ringel [N. Hartsfield, G. Ringel, Pearls in Graph Theory, Academic Press, INC., Boston, 1990, pp. 108-109, Revised version, 1994] conjectured that every simple connected graph, except K₂, is antimagic. In this article, we prove that a new class of Cartesian product graphs are antimagic. In particular, by combining this result and the antimagicness result on toroidal grids (Cartesian products of two cycles) in [Tao-Ming Wang, Toroidal grids are anti-magic, in: Proc. 11th Annual International Computing and Combinatorics Conference COCOON’2005, in: LNCS, vol. 3595, Springer, 2005, pp. 671-679], all Cartesian products of two or more regular graphs of positive degree can be proved to be antimagic.     

几类积图的团染色数

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

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.