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

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

The profile of the Cartesian product of graphs

Given a graph G, a proper labelingf of G is a one-to-one function from V(G) onto {1,2,…,|V(G)|}. For a proper labeling f of G, the profile widthw_f(v) of a vertex v is the minimum value of f(v)−f(x), where x belongs to the closed neighborhood of v. The profile of a proper labelingfofG, denoted by P_f(G), is the sum of all the w_f(v), where v∈V(G). The profile ofG is the minimum value of P_f(G), where f runs over all proper labeling of G. In this paper, we show that if the vertices of a graph G can be ordered to satisfy a special neighborhood property, then so can the graph G×Q_n. This can be used to determine the profile of Q_n and K_m×Q_n.     

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.     

Circular chromatic index of Cartesian products of graphs

The circular chromatic index of a graph G, written , is the minimum r permitting a function such that whenever e and are incident. Let □ , where □ denotes Cartesian product and H is an ‐regular graph of odd order, with (thus, G is s‐regular). We prove that , where is the minimum, over all bases of the cycle space of H, of the maximum length of a cycle in the basis. When and m is large, the lower bound is sharp. In particular, if , then □ , independent of m. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 7–18, 2008     

The genus of the Cartesian product of two graphs

Upper and lower bounds are given for the genus, γ(G₁ × G₂), of the Cartesian product of arbitrary graphs G₁ and G₂, in terms of the genera γ(G₁) and γ(G₂). These bounds are then used to obtain asymptotic results for the cases in which G₁ and G₂ are both regular complete k-partite graphs.     

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     

The distinguishing chromatic number of Cartesian products of two complete graphs

A labeling of a graph G is distinguishing if it is only preserved by the trivial automorphism of G. The distinguishing chromatic number of G is the smallest integer k such that G has a distinguishing labeling that is at the same time a proper vertex coloring. The distinguishing chromatic number of the Cartesian product is determined for all k and n. In most of the cases it is equal to the chromatic number, thus answering a question of Choi, Hartke and Kaul whether there are some other graphs for which this equality holds.     

The chromatic difference sequence of a graph

Let α_k(G) denote the maximum number of vertices in a k-colorable subgraph of G. Set α_k(G)=α_k(G)?α_(k?1)(G). The sequence a₁(G), a₂(G),… is called the chromatic difference sequence of the graph G. We present necessary and sufficient conditions for a sequence to be the chromatic difference sequence of some 4-colorable graph.     

Gromov hyperbolicity in Cartesian product graphs

If X is a geodesic metric space and x ₁, x ₂, x ₃ ∈ X, a geodesic triangle T = {x ₁, x ₂, x ₃} is the union of the three geodesics [x ₁ x ₂], [x ₂ x ₃] and [x ₃ x ₁] in X. The space X is δ-hyperbolic (in the Gromov sense) if any side of T is contained in a δ-neighborhood of the union of the two other sides, for every geodesic triangle T in X. If X is hyperbolic, we denote by δ(X) the sharp hyperbolicity constant of X, i.e. δ(X) = inf{δ ≥ 0: X is δ-hyperbolic}. In this paper we characterize the product graphs G ₁ × G ₂ which are hyperbolic, in terms of G ₁ and G ₂: the product graph G ₁ × G ₂ is hyperbolic if and only if G ₁ is hyperbolic and G ₂ is bounded or G ₂ is hyperbolic and G ₁ is bounded. We also prove some sharp relations between the hyperbolicity constant of G ₁ × G ₂, δ(G ₁), δ(G ₂) and the diameters of G ₁ and G ₂ (and we find families of graphs for which the inequalities are attained). Furthermore, we obtain the precise value of the hyperbolicity constant for many product graphs.     

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.     

Critical graphs for chromatic difference sequences

Let α_k(G) denote the maximum number of vertices in a k-colorable subgraph of G. Set α_k=α_k(G)-α(_k-1)(G). The sequence a₁(G),a₂(G),… is called the chromatic difference sequence (cds) of G. We call a graph G critical if no proper subgraph of G has the same cds as G. We prove that (with a single exception) if there exists a graph G having cds (G)=〈a₁,a₂,a₃〉 (a₃>) and if a₁?a₂+a₃, then there exists a connected critical graph H with cds(H)= 〈a₁, a₂,a₂〉.     

On linkedness in the Cartesian product of graphs

We study linkedness of the Cartesian product of graphs and prove that the product of an a-linked and a b-linked graph is \((a+b-1)\)-linked if the graphs are sufficiently large. Further bounds in terms of connectivity are shown. We determine linkedness of products of paths and products of cycles.     

Generalized 3-edge-connectivity of Cartesian product graphs

The generalized k-connectivity κ _k (G) of a graph G was introduced by Chartrand et al. in 1984. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized k-edge-connectivity which is defined as λ _k (G) = min{λ(S): S ? V (G) and |S| = k}, where λ(S) denotes the maximum number l of pairwise edge-disjoint trees T ₁, T ₂, …, T _l in G such that S ? V (T _i ) for 1 ? i ? l. In this paper we prove that for any two connected graphs G and H we have λ ₃(G □ H) ? λ ₃(G) + λ ₃(H), where G □ H is the Cartesian product of G and H. Moreover, the bound is sharp. We also obtain the precise values for the generalized 3-edge-connectivity of the Cartesian product of some special graph classes.     

Game chromatic number of strong product graphs

The graph coloring game is a two-player game in which the two players properly color an uncolored vertex of G alternately. The first player wins the game if all vertices of G are colored, and the second wins otherwise. The game chromatic number of a graph G is the minimum integer k such that the first player has a winning strategy for the graph coloring game on G with k colors. There is a lot of literature on the game chromatic number of graph products, e.g., the Cartesian product and the lexicographic product. In this paper, we investigate the game chromatic number of the strong product of graphs, which is one of major graph products. In particular, we completely determine the game chromatic number of the strong product of a double star and a complete graph. Moreover, we estimate the game chromatic number of some King's graphs, which are the strong products of two paths.