A forest in which every component is a path is called a path forest. A family of path forests whose edge sets form a partition of the edge set of a graph \(G\) is called a path decomposition of a graph \(G\). The minimum number of path forests in a path decomposition of a graph \(G\) is the linear arboricity of \(G\) and denoted by \(\ell(G)\). If we restrict the number of edges in each path to be at most \(k\) then we obtain a special decomposition. The minimum number of path forests in this type of decomposition is called the linear \(k\)-arboricity and denoted by \(\ell\alpha_k(G)\). In this paper we concentrate on the special type of path decomposition and we obtain the answers for \(\ell\alpha_2(G)\) when \(G\) is \(K_{n,n}\). We note here that if we restrict the size to be one, the number \(\ell\alpha_1(G)\) is just the chromatic index of \(G\).

Primal graphs and primary graphs are defined and compared. All primary stars, paths, circuits, wheels, theta graphs, caterpillars, and echinoids are found, as are all primary graphs of the form \(K_{2,n}\) with \(n \leq 927\).

Let \(K(n | t)\) denote the complete multigraph containing \(n\) vertices and exactly \(t\) edges between every pair of distinct vertices, and let \(f(m,t)\) be the minimum number of complete bipartite subgraphs into which the edges of \(K(n|t)\) can be decomposed. Pritikin [3] proved that \(f(n;t) \geq \max\{n-1,t\}\), and that \(f(m;2) = n\) if \(n = 2,3,5\), and \(f(m;2) = n-1\), otherwise. In this paper, for \(t \geq 3\) using Hadamard designs, skew-Hadamard matrices and symmetric conference matrices [6], we give some complete multigraph families \(K(n|t)\) with \(f(n;t) = n-1\).

Let \(G\) be a graph with \(r \geq 0\) special vertices, \(b_1, \ldots, b_r\), called pins. \(G\) can be composed with another graph \(H\) by identifying each \(b_i\) with another vertex \(a_i\) of \(H\). The resulting graph is denoted \(H \circ G\). Let \(\Pi\) denote a decision problem on graphs. We consider the problem of constructing a “small” minor \(G^*\) of \(G\) that is “equivalent” to \(G\) with respect to the problem \(\Pi\). Specifically, \(G^*\) should satisfy the following:

(C1) \(G^b\) has the same pins as \(G\).

(C2) \(\Pi(H \circ G^b) = \Pi(H \circ G)\) for every \(H\) for which \(H \circ G\) is defined.

(C3) \(|V(G^b)| + |E(G^b)| \leq c \cdot p\), where \(p\) is the number of pins of \(G\), \\and \(c\) is a constant depending only on \(\Pi\).

(C4) \(G^b\) is a minor of \(G\).

We provide linear-time algorithms for constructing such graphs when \(\Pi\) stands for either series-parallelness or outer-planarity. These algorithms lead to linear-time algorithms that determine whether a hierarchical graph is series-parallel or outer-planar and to linear-space algorithms for generating a forbidden subgraph of a hierarchical graph, when one exists.

In this paper, we prove that if \(G\) is a 3-connected planar graph and contains no vertex of degree \(4\), then \(G\) is edge reconstructible. This generalizes a result of J. Lauri [J1].

In this paper, we present a new generalization of the self-complementary graphs, called the \(t\)-sc graphs. Various properties of this class of graphs are studied, generalizing earlier results on self-complementary graphs. Certain existential results on \(t\)-sc graphs are presented, followed by the construction of some infinite classes of \(t\)-sc graphs. Finally, the notion of \(t\)-sc graphs is linked with the notion of factorization, leading to a generalization of \(r\)-partite self-complementary graphs.

In [1], we introduced the generalized exponent for primitive matrices. In this paper, the generalized exponents of tournament matrices are derived.

We provide graceful labelings for prisms \(C_{2m} \times P_n\), with even cycles, for all \(n \geq 2\), and prisms \(C_{2m+1} \times P_n\), with odd cycles when \(3 \leq mn \leq 12\). Further, we verify that the windmill graph \(K^{(m)}_{4}\) is graceful for \(r \leq 22\), and that the square of a path \(P_n\) is graceful for \(n \leq 32\).

In this paper, a composition result, \(viz\)., the number of \(r\)-compositions of \(n\) dominated by the \(r\)-compositions of \(m\) (\(m \geq n\)) subject to certain restrictions, has been derived by the method of induction.