Global defensive alliances of trees and Cartesian product of paths and cycles

Given a graph $G$, a defensive alliance of $G$ is a set of vertices $S?V\left(G\right)$ satisfying the condition that for each $v\in S$, at least half of the vertices in the closed neighborhood of $v$ are in $S$. A defensive alliance $S$ is called global if every vertex in $V\left(G\right)?S$ is adjacent to at least one member of the defensive alliance $S$. The global defensive alliance number of $G$, denoted ${\gamma }_a\left(G\right)$, is the minimum size around all the global defensive alliances of $G$. In this paper, we present an efficient algorithm to determine the global defensive alliance numbers of trees, and further give formulas to decide the global defensive alliance numbers of complete $k$-ary trees for $k=2,3,4$. We also establish upper bounds and lower bounds for ${\gamma }_a(P_m\times P_n),{\gamma }_a(C_m\times P_n)$ and ${\gamma }_a(C_m\times C_n)$, and show that the bounds are sharp for certain $m,n$.     

On the crossing numbers of Cartesian products with trees

Zip product was recently used in a note establishing the crossing number of the Cartesian product K₁,n □ P_m. In this article, we further investigate the relations of this graph operation with the crossing numbers of graphs. First, we use a refining of the embedding method bound for crossing numbers to weaken the connectivity condition under which the crossing number is additive for the zip product. Next, we deduce a general theorem for bounding the crossing numbers of (capped) Cartesian product of graphs with trees, which yields exact results under certain symmetry conditions. We apply this theorem to obtain exact and approximate results on crossing numbers of Cartesian product of various graphs with trees. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 287–300, 2007     

On the packing chromatic number of Cartesian products, hexagonal lattice, and trees

The packing chromatic number χ_ρ(G) of a graph G is the smallest integer k such that the vertex set of G can be partitioned into packings with pairwise different widths. Several lower and upper bounds are obtained for the packing chromatic number of Cartesian products of graphs. It is proved that the packing chromatic number of the infinite hexagonal lattice lies between 6 and 8. Optimal lower and upper bounds are proved for subdivision graphs. Trees are also considered and monotone colorings are introduced.     

Walks and paths in trees

Recently Csikvári [Combinatorica 30(2) 2010, 125–137] proved a conjecture of Nikiforov concerning the number of closed walks on trees. Our aim is to extend this theorem to all walks. In addition, we give a simpler proof of Csikvári's result and answer one of his questions in the negative. Finally we consider an analogous question for paths rather than walks. © 2011 Wiley Periodicals, Inc. J Graph Theory     

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

     

On domination numbers of Cartesian product of paths

We show the link between the existence of perfect Lee codes and minimum dominating sets of Cartesian products of paths and cycles. From the existence of such a code we deduce the asymptotical values of the domination numbers of these graphs.     

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.     

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.     

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.