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.

Let \(G\) be a simple graph with \(n\) vertices. Let \(L(G)\) denote the line graph of \(G\). We show that if \(\kappa'(G) > 2\) and if for every pair of nonadjacent vertices \(v,u \in V(G)\), \(d(v) + d(u) > \frac{2n}{3} – 2\), then for any pair of vertices \(e, e’ \in V(L(G))\), either \(L(G)\) has a Hamilton \((e, e’)\)-path, or \(\{e, e’\}\) is a vertex-cut of \(L(G)\). When \(G\) is a triangle-free graph, this bound can be reduced to \(\frac{n}{3}\). These bounds are all best possible and they partially improve prior results in [J.Graph Theory 10(1986),411-425] and [Discrete Math.76(1989)95-116].

The link length of a walk in a multidimensional grid is the number of straight line segments constituting the walk. Alternatively, it is the number of turns that a mobile unit needs to perform in traversing the walk. A rectilinear walk consists of straight line segments which are parallel to the main axis. We wish to construct rectilinear walks with minimal link length traversing grids. If \(G\) denotes the multidimensional grid, let \(s(G)\) be the minimal link length of a rectilinear walk traversing all the vertices of \(G\). In this paper, we develop an asymptotically optimal algorithm for constructing rectilinear walks traversing all the vertices of complete multidimensional grids and analyze the worst-case behavior of \(s(G)\), when \(G\) is a multidimensional grid.

We proved that if a graph \(G\) of minimum valency \(\delta=6\alpha + 5\), with \(\alpha\) a non-negative integer, can triangulate a surface \(\Sigma\) with \(\chi(\Sigma) = -\alpha n + \beta\), where \(\beta \in \{0, 1, 2\}\), then \(G\) is edge reconstructible.

We introduce a concept of “pseudo dual” pseudographs which can be thought of as generalizing some of the recent work on iterated clique graphs. In particular, we characterize those pseudographs which have pseudo duals and show that they encompass several natural families of intersection pseudographs.

Let \(G\) be a simple graph, \(a\) and \(b\) integers and \(f: E(G) \to \{a,a+1,\ldots,b\}\) an integer-valued function with \(\sum_{e\in E(G)} f(e) \equiv 0 \pmod{2}\). We prove the following results:(1) If \(b \geq a \geq 2\), \(G\) is connected and \(\delta(G) \geq \max\left[\frac{b}{2}+2, \frac{(a+b+2)^2}{8a}\right]\), then the line graph \(L(G)\) of \(G\) has an \(f\)-factor;(2) If \(b\geq a \geq 2\), \(G\) is connected and \(\delta(L(G)) \geq \frac{(a+2b+2)^2}{8a}\), then \(L(G)\) has an \(f\)-factor.

We show that a cubic graph is \(\frac{3}{2}\)-tough if and only if it is equal to \(K_4\) or \(K_3 \times K_3\) or else is the inflation of a 3-connected cubic graph.

A directed triple system of order \(v\), denoted \(DT S(v)\), is said to be \(k\)-near-rotational if it admits an automorphism consisting of \(3\) fixed points and \(k\) cycles of length \(\frac{v-3}{3}\). In this paper, we give necessary and sufficient conditions for the existence of \(k\)-near-rotational \(DT S(v)\)s.

A correspondence between decompositions of complete directed graphs with loops into collections of closed trails which partition the edge set of the graph and the variety of all column latin groupoids is established. Subvarieties which consist of column latin groupoids arising from decompositions where only certain trail lengths occur are examined. For all positive integers \(m\), the set of values of \(n\) for which the complete directed graph with loops on a vertex set of cardinality \(n\) can be decomposed in this manner such that all the closed trails have length \(m\) is shown to be the set of all \(n\) for which \(m\) divides \(n^2\).

Let \(X\) be a graph and let \(\alpha(X)\) and \(\alpha'(X)\) denote the domination number and independent domination number of \(X\), respectively. We show that for every triple \((m,k,n)\), \(m \geq 5\), \(2 \leq k \leq m\), \(n > 1\), there exist \(m\)-regular \(k\)-connected graphs \(X\) with \(\alpha'(X) – \alpha(X) > n\). The same also holds for \(m = 4\) and \(k \in \{2,4\}\).

Let \(k\) be an integer greater than one. A set \(S\) of integers is called \(k\)-multiple-free (or \(k\)-MF for short) if \(x \in S\) implies \(kx \notin S\). Let \(f_k(n) = \max\{|A| : A \subseteq [1,n] \text{ is } k\text{-MF}\}\). A subset \(A\) of \([1,n]\) with \(|A| = f_k(n)\) is called a maximal \(k\)-MF subset of \([1,n]\). In this paper, we give a recurrence relation and a formula for \(f_k(n)\). In addition, we give a method for constructing a maximal \(k\)-MF subset of \([1,n]\).

This paper concerns the domination numbers \(\gamma_{k,n}\) for the complete \(k \times n\) grid graphs for \(1 \leq k \leq 10\) and \(n \geq 1\). These numbers were previously established for \(1 \leq k \leq 4\). Here we present dominating sets for \(5 \leq k \leq 10\) and \(n \geq 1\). This gives upper bounds for \(\gamma_{k,n}\) for \(k\) in this range. We discuss evidence that indicates that these upper bounds are also lower bounds.

By a graph we mean an undirected simple graph. The genus \(\gamma(G)\) of a graph \(G\) is the minimum genus of the orientable surface on which \(G\) is embeddable. The thickness \(\Theta(G)\) of \(G\) is the minimum number of planar subgraphs whose union is \(G\).

In [1], it is proved that, if \(\gamma(G) = 1\), then \(\Theta(G) = 2\). If \(\gamma(G) = 2\), the known best upper bound on \(\Theta(G)\) is \(4\) and, as far as the author knows, the known best lower bound is \(2\). In this paper, we prove that, if \(\gamma(G) = 2\), then \(\Theta(G) \leq 3\).

A generalization of (binary) balanced incomplete block designs is to allow a treatment to occur in a block more than once, that is, instead of having blocks of the design as sets, allow multisets as blocks. Such a generalization is referred to as an \(n\)-ary design. There are at least three such generalizations studied in the literature. The present note studies the relationship between these three definitions. We also give some results for the special case when \(n\) is \(3\).

We investigate searching strategies for the set \(\{1, \ldots, n\}\) assuming a fixed bound on the number of erroneous answers and forbidding repetition of questions. This setting models the situation when different processors provide answers to different tests and at most \(k\) processors are faulty. We show for what values of \(k\) the search is feasible and provide optimal testing strategies if at most one unit is faulty.

Ramsey’s Theorem implies that for any graph \(H\) there is a least integer \(r = r(H)\) such that if \(G\) is any graph of order at least \(r\) then either \(G\) or its complement contains \(H\) as a subgraph. For \(n<r\) and \(0 \leq e \leq \frac{1}{2}n(n-1)\), let \(f(e) =1\) {if every graph \(G\) of order \(n\) and size \(e\) is such that either \(G\) or \(\overline{G}\) contains \(H\),} and let \(f(e)=0\) {otherwise.} This associates with the pair \((H,n)\) a binary sequence \(S(H,n)\). By an interval of \(S(H,n)\) we mean a maximal string of equal terms. We show that there exist infinitely many pairs \((H,n)\) for which \(S(H,n)\) has seven intervals.

In this paper the existence of the \(12140\) non-isomorphic symmetric \((49,16,5)\) designs with an involutory homology (this is a special kind of involution acting on a design) is propagated. The automorphism groups are cyclic of orders \(2\), \(4\), \(8\), or \(10\). \(218\) designs are self-dual. The \(40\) designs with an automorphism group of order \(10\) were already given in [2]. A computer (IBM \(3090\)) was used for about \(36\) hours CPU time. According to [2,4] now there are known \(12146\) symmetric \((49,16,5)\) designs.

This paper deals with the joint distributions of some characteristics of the two-dimensional simple symmetric random walk in which a particle at any stage moves one unit in any one of the four directions, namely, north, south, east, and west with equal probability.

In \(1974\), G. Chartrand and R.E. Pippert first defined locally connected and locally \(n\)-connected graphs and obtained some interesting results. In this paper we first extend these concepts to digraphs. We obtain generalizations of some results of Chartrand and Pippert and establish relationships between local connectedness and global connectedness in digraphs.

An infinite countable Steiner triple system is called universal if any countable Steiner triple system can be embedded into it. The main result of this paper is the proof of non-existence of a universal Steiner triple system.

The fact is proven by constructing a family \(\mathcal{S}\) of size \(2^{\omega}\) of infinite countable Steiner triple systems so that no finite Steiner triple system can be embedded into any of the systems from \(\mathcal{S}\) and no infinite countable Steiner triple system can be embedded into any two of the systems from \(\mathcal{S}\) (it follows that the systems from \(\mathcal{S}\) are pairwise non-isomorphic).

A Steiner triple system is called rigid if the only automorphism it admits is the trivial one — the identity. An additional result presented in this paper is a construction of a family of size \(2^{\omega}\) of pairwise non-isomorphic infinite countable rigid Steiner triple systems.

A graph \(G\) having a \(1\)-factor is called \(n\)-extendable if every matching of size \(n\) extends to a 1-factor. We show that
if \(G\) is a connected graph of order \(2p (p \geq 3)\), and g and n are integers, \(1 \leq n < q < p\), such that every induced connected subgraph of order \(2q\) is \(n\)-extendable, then \(G\) is n-extendable.