Narrow Results

Let $K_n$ denote a complete graph on $n$ vertices and $S_k$ denote a complete bipartite graph $K_{1,k}$. A Bowtie $B_l$ is a graph formed by the union of two cycles $C_n$ and $C_m$ intersecting at a common vertex. A decomposition of a graph $G$ is a collection of edge-disjoint subgraphs $H$, such that every edge of G belongs to exactly one $H$. Given non-isomorphic subgraphs $H_1$ and $H_2$ of $G$, a $(H_1,H_2)$ — multi-decomposition of $G$ is the decomposition of $G$ into $a$ copies of $H_1$ and $b$ copies of $H_2$, such that $a{H}_1\oplus b{H}_2=G$, for some integers $a,b\ge 0$. In this paper, the multi-decomposition of $K_n$ into $S_k$ and $B_l$ has been investigated and obtained a necessary and sufficient condition when $k=l=6$. It is proved that for a given positive integer $n$, $K_n$ can be decomposed into $a$ copies of $S_6$ and $b$ copies of $B_6$ for some pair of non-negative integers $(a,b)$ if and only if $6(a+b)=\left(\genfrac{}{}{0.0pt}{}{n}{2}\right)$, for all $n\ge 9$.

For two given graphs G₁ and G₂, the Ramsey number R(G₁, G₂) is the smallest positive integer n such that for any graph G of order n, either G contains G₁ or the complement of G contains G₂. Let S_n denote a star of order n and W_m a wheel of order m + 1. In this paper we show that R(S_n, W₈) = 2n + 1 for n ≥ 5 and n ≡ 1 (mod 2).