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