Upper and lower bounds are given for the toughness of generalized Petersen graphs. A lower bound of \(1\) is established for \(t(G(n,k))\) for all \(n\) and \(k\). This bound of \(1\) is shown to be sharp if \(n = 2k\) or if \(n\) is even and \(k\) is odd. The upper bounds depend on the parity of \(k\). For \(k\) odd, the upper bound \(\frac{n}{n-\frac{n+1}{2}}\) is established. For \(k\) even, the value \(\frac{2k}{2k-1}\) is shown to be an asymptotic upper bound. Computer verification shows the reasonableness of these bounds for small values of \(n\) and \(k\).

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

Let \(G = (V, E)\) be a graph and \(A\) a non-trivial Abelian group, and let \(\mathcal{F}(G, A)\) denote the set of all functions \(f: E(G) \to A\). Denote by \(D\) an orientation of \(E(G)\). Then \(G\) is \(A\)-colorable if and only if for every \(f \in \mathcal{F}(G, A)\) there exists an \(A\)-coloring \(c: V(G) \to A\) such that for every \(e = (x,y) \in E(G)\) (assumed to be directed from \(x\) to \(y\)), \(c(x) – c(y) \neq f(e)\). If \(G\) is a graph, we define its group chromatic number \(\chi_1(G)\) to be the minimum number \(m\) for which \(G\) is \(A\)-colorable for any Abelian group \(A\) of order \(\geq m\) under the orientation \(D\). In this paper, we investigated the properties of the group chromatic number, proved the Brooks Type theorem for \(\chi_1(G)\), and characterized all bipartite graphs with group chromatic number at most \(3\), among other things.

A signed graph is an unoriented graph with a given partition \(E = E^+ \bigcup E^-\) of its edge-set. We define the arc signed graph \({A}(G)\) of an oriented graph \(G\) (G has no multiple arcs, opposite arcs, and loops). The arc signed graphs are similar to the line graphs. We prove both a Krausz-type characterization and a forbidden induced subgraph characterization (like the theorem of Beineke and Robertson on line graphs). Unlike line graphs, there are infinitely many minimal forbidden induced subgraphs for the arc signed graphs. Nevertheless, the arc signed graphs are polynomially recognizable. Also, we obtain a result similar to Whitney’s theorem on line graphs.