Distinguishing colorings of Cartesian products of complete graphs

We determine the values of s and t for which there is a coloring of the edges of the complete bipartite graph K_s,t which admits only the identity automorphism. In particular, this allows us to determine the distinguishing number of the Cartesian product of complete graphs.     

Distinguishing chromatic numbers of complements of Cartesian products of complete graphs

The distinguishing chromatic number of a graph, $G$, is the minimum number of colours required to properly colour the vertices of $G$ so that the only automorphism of $G$ that preserves colours is the identity. There are many classes of graphs for which the distinguishing chromatic number has been studied, including Cartesian products of complete graphs (Jerebic and Klav?ar, 2010). In this paper we determine the distinguishing chromatic number of the complement of the Cartesian product of complete graphs, providing an interesting class of graphs, some of which have distinguishing chromatic number equal to the chromatic number, and others for which the difference between the distinguishing chromatic number and chromatic number can be arbitrarily large.     

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.     

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.     

Distinguishing Cartesian powers of graphs

The distinguishing number D(G) of a graph is the least integer d such that there is a d‐labeling of the vertices of G that is not preserved by any nontrivial automorphism of G. We show that the distinguishing number of the square and higher powers of a connected graph G ≠ K₂, K₃ with respect to the Cartesian product is 2. This result strengthens results of Albertson [Electron J Combin, 12 ( 1 ), #N17] on powers of prime graphs, and results of Klav?ar and Zhu [Eu J Combin, to appear]. More generally, we also prove that d(G □ H) = 2 if G and H are relatively prime and |H| ≤ |G| < 2^|H| ? |H|. Under additional conditions similar results hold for powers of graphs with respect to the strong and the direct product. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 250–260, 2006     

若干笛卡尔积图的邻点可区别关联染色

An adjacent vertex distinguishing incidence coloring of graph G is an incidence coloring of G such that no pair of adjacent vertices meets the same set of colors.We obtain the adjacent vertex distinguishing incidence chromatic number of the Cartesian product of a path and a path,a path and a wheel,a path and a fan,and a path and a star.     

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.     

Cartesian products of block graphs

Hamming graphs (being the Cartesian products of complete graphs) are known to be the quasi-median graphs not containing the 3-vertex path as a convex subgraph. Similarly, the Cartesian products of trees have been characterized among median graphs by a single forbidden convex subgraph. In this note a common generalization of these two results is given that characterizes the Cartesian products of block graphs.     

A two-coloring of Cartesian products

We shall color the Cartesian product ω × ω₁with two colors. Can an infinite subset A ?ω and an uncountable subset B ?ω₁ be found such that the product A × B can be one-colored? This problem proves to be unsolvable in ZFC.     

Recognizing triangulated Cartesian graph products

Computational meshes for numerical simulation frequently show—at least locally—a structure resembling a triangulated grid. Our goal is to recognize product-like structures in triangular meshes. We define triangulated Cartesian products of graphs and analyze their structural properties. We show how to recognize and factorize graphs that are triangulated products of two factors, when the factors are triangle-free graphs. We also discuss properties of products with more than two factors.     

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.)

     

Polytopality and Cartesian products of graphs

We study the question of polytopality of graphs: when is a given graph the graph of a polytope? We first review the known necessary conditions for a graph to be polytopal, and we present three families of graphs which satisfy all these conditions, but which nonetheless are not graphs of polytopes. Our main contribution concerns the polytopality of Cartesian products of non-polytopal graphs. On the one hand, we show that products of simple polytopes are the only simple polytopes whose graph is a product. On the other hand, we provide a general method to construct (non-simple) polytopal products whose factors are not polytopal.     

Cartesian products of trees and paths

We characterize the (weak) Cartesian products of trees among median graphs by a forbidden 5-vertex convex subgraph. The number of tree factors (if finite) is half the length of a largest isometric cycle. Then a characterization of Cartesian products of n trees obtains in terms of isometric cycles and intervals. Finally we investigate to what extent the proper intervals determine the product structure. © 1996 John Wiley & Sons, Inc.