The achromatic number of a graph $G$ is the maximum number of colours in a proper vertex colouring of $G$ such that for any two distinct colours there is an edge of $G$ incident with vertices of those two colours. We determine the achromatic number of the Cartesian product of $K_5$ and $K_n$ for all $n \le 24$.
In this paper we characterize the convex dominating sets in the composition and Cartesian product of two connected graphs. The concepts of clique dominating set and clique domination number of a graph are defined. It is shown that the convex domination number of a composition $G[H]$ of two non-complete connected graphs $G$ and $H$ is equal to the clique domination number of $G$. The convex domination number of the Cartesian product of two connected graphs is related to the convex domination numbers of the graphs involved.
The generalized $k$-connectivity $\kappa _{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 $\lambda _k(G) = \min \{\lambda (S)\colon S \subseteq V(G)$ and $|S|= k\}$, where $\lambda (S)$ denotes the maximum number $\ell $ of pairwise edge-disjoint trees $T_1, T_2, \ldots , T_{\ell }$ in $G$ such that $S\subseteq V(T_i)$ for $1\leq i\leq \ell $. In this paper we prove that for any two connected graphs $G$ and $H$ we have $\lambda _3(G\square H)\geq \lambda _3(G)+\lambda _3(H)$, where $G\square 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.
The isolated rupture degree for a connected graph G is defined as ir(G) = max{i(G-S)-|S|-m(G-S):S is element C(G)}, where i(G-S) and m(G-S), respectively, denote the number of components which are isolated vertices and the order of a largest component in G-S. C(G) denotes the set of all cut-sets of G. The isolated rupture degree is a new graph parameter which can be used to measure the vulnerability of networks. In this paper, we firstly give a recursive algorithm for computing the isolated rupture degree of trees, and determine the maximum and minimum isolated rupture degree of trees with given order and maximum degree. Then, the exact value of isolated rupture degree of gear graphs are given. In the final, we determine the rupture degree of the Cartesian product of two special graphs and a special permutation graph.
The concept of the $k$-pairable graphs was introduced by Zhibo Chen (On $k$-pairable graphs, Discrete Mathematics 287 (2004), 11–15) as an extension of hypercubes and graphs with an antipodal isomorphism. In the same paper, Chen also introduced a new graph parameter $p(G)$, called the pair length of a graph $G$, as the maximum $k$ such that $G$ is $k$-pairable and $p(G)=0$ if $G$ is not $k$-pairable for any positive integer $k$. In this paper, we answer the two open questions raised by Chen in the case that the graphs involved are restricted to be trees. That is, we characterize the trees $G$ with $p(G)=1$ and prove that $p(G \square H)=p(G)+p(H)$ when both $G$ and $H$ are trees.
In the present article we provide an example of two closed non-$\sigma $-lower porous sets $A, B \subseteq \mathbb R $ such that the product $A\times B$ is lower porous. On the other hand, we prove the following: Let $X$ and $Y$ be topologically complete metric spaces, let $A\subseteq X$ be a non-$\sigma $-lower porous Suslin set and let $B\subseteq Y$ be a non-$\sigma $-porous Suslin set. Then the product $A\times B$ is non-$\sigma $-lower porous. We also provide a brief summary of some basic properties of lower porosity, including a simple characterization of Suslin non-$\sigma $-lower porous sets in topologically complete metric spaces.
ct. Guy and Harary (1967) have shown that, for k > 3, the graph P[2k, k] is homeomorphic to the Möbius ladder M2k, so that its crossing number is one; it is well known that P[2k, 2] is planar. Exoo, Harary and Kabell (1981) have shown hat the crossing number of P[2k + 1, 2] is three, for k ≥ 2. Fiorini (1986) and Richter and Salazar (2002) have shown that P[9, 3] has crossing number two and that P[3k, 3] has crossing number k, provided k ≥ 4. We extend this result by showing that P[3k, k] also has crossing number k for all k ≥ 4.