Some Decomposition Invariants of Crowns

Abstract

Suppose \(G\) is a graph. The minimum number of paths (trees, forests, linear forests, star forests, complete bipartite graphs, respectively) needed to decompose the edges of \(G\) is called the path number (tree number, arboricity, linear arboricity, star arboricity and biclique number, respectively) of \(G\). These numbers are denoted by \(p(G), t(G), a(G), la(G), sa(G), r(G)\), respectively. For integers \(1 \leq k \leq n\), let \(C_{n,k}\) be the graph with vertex set \(\{a_1,a_2,\ldots,a_n,b_1,b_2,\ldots,b_n\}\) and edge set \(\{a_ib_j :i=1,2,\ldots ,n,j \equiv i+1,i+2, \ldots ,i+k \text{(mod n)}\}\). We call \(C_{n,k}\) a crown. In this paper, we prove the following results:

1. \(p(C_{n,k}) = \begin{cases}
   n & \text{if \(k\) is odd}, \\
   {(\frac{k}{2})+1} & \text{if \(k\) is even}.
   \end{cases}\)
2. \(a(C_{n,k}) = t(C_{n,k}) = la(C_{n,k}) = \left\lceil \frac{k+1}{2} \right\rceil\) if \(k \geq 2\).
3. For \(k \geq 3\) and \(k \in \{3,5\} \cup \{n-3,n-2,n-1\}\),
   \[sa(C_{n,k}) = \begin{cases}
   \left\lceil \frac{k}{2} \right\rceil + 1 & \text{if \(k\) is odd}, \\
   \left\lceil \frac{k}{2} \right\rceil + 2 & \text{if \(k\) is even}.
   \end{cases}\]
4. \(r(C_{n,k}) = n\) if \(k \leq \frac{n+1}{2}\) or \(\gcd(k,n) = 1\).

Due to (3), (4), we propose the following conjectures.

\(\textbf{Conjecture A}\). For \(3 \leq k \leq n-1\),
\[sa(C_{n,k}) = \begin{cases}
\left\lceil \frac{k}{2} \right\rceil + 1 & \text{if \(k\) is odd}, \\
\left\lceil \frac{k}{2} \right\rceil + 2 & \text{if \(k\) is even}.
\end{cases}\]
\(\textbf{Conjecture B}\). For \(1 \leq k \leq n-1\), \(r(C_{n,k}) = n\).