Let \(G\) be a connected (multi)graph. We define the leaf-exchange spanning tree graph \( {T_l}\) of \(G\) as the graph with vertex set \(V_l = \{T|T \text{ is a spanning tree of } G\}\) and edge set \(E_l = \{(T, T’)|E(T)\Delta E(T’) = \{e, f\}, e \in E(T), f \in E(T’) \text{ and } e \text{ and } f \text{ are incident with a vertex } v \text{ of degree } 1 \text{ in } T \text{ and } T’\}\). \({T}(G)\) is a spanning subgraph of the so-called spanning tree graph of \(G\), and of the adjacency spanning tree graph of \(G\), which were studied by several authors. A variation on the leaf-exchange spanning tree graph appeared in recent work on basis graphs of branching greedoids. We characterize the graphs which have a connected leaf-exchange spanning tree graph and give a lower bound on the connectivity of \( {T_l}(G)\) for a \(3\)-connected graph \(G\).

The fine structure of a directed triple system of index \(\lambda\) is the vector \((c_1,c_2,\ldots,c_\lambda)\), where \(c_i\) is the number of directed triples appearing precisely \(i\) times in the system. We determine necessary and sufficient conditions for a vector to be the fine structure of a directed triple system of index \(3\) for \(v \equiv 0\) or \(1 \pmod{3}\).

Let \(p\) denote the circumference of a two-connected graph \(G\). We construct a hamiltonian cycle in \(G^2\) which contains more than \(p/2\) edges of \(G\). Using this construction we prove some properties of hamiltonian cycles in the square of \(G\).

For a connected graph \(G\) that is not a cycle, a path or a claw, let its \(k\)-iterated line graph have the diameter \(diam_k\), and the radius \(r_k\). Then \(diam_{k+1} = diam_k + 1\) for sufficiently large \(k\). Moreover, \(\{r_k\}\) also tends to infinity and the sequence \(\{diam_k – r_k – \sqrt{2\log_2 k}\}\) is bounded.

In \([1]\) it is proved that each \(4\)-critical plane graph contains either a \(4\)- or a \(5\)-cycle or otherwise a face of size between \(6\) and \(11\).

For nonempty graphs \(G\) and \(H\), \(H\) is said to be \(G\)-decomposable (written \(G|H\)) if \(E(H)\) can be partitioned into sets \(E_1, \ldots, E_n\) such that the subgraph induced by each \(E_i\) is isomorphic to \(G\). If \(H\) is a graph of minimum size such that \(F|H\) and \(G|H\), then \(H\) is called a least common multiple of \(F\) and \(G\). The size of such a least common multiple is denoted by \(\mathrm{lcm}(F,G)\). We show that if \(F\) and \(G\) are bipartite, then \(\mathrm{lcm}(F,G) \leq |V(F)|\cdot|V(G)|\), where equality holds if \((|V(F)|,|V(G)|) = 1\). We also determine \(\mathrm{lcm}(F,G)\) exactly if \(F\) and \(G\) are cycles or if \(F = P_m, G = K_n\), where \(n\) is odd and \((m-1,\frac{1}{2}(n-1)) = 1\), in the latter case extending a result in [{8}].

Let \(G\) be a graph. A vertex subversion strategy of \(G\), \(S\), is a set of vertices in \(G\) whose closed neighborhood is deleted from \(G\). The survival-subgraph is denoted by \(G/S\). The vertex-neighbor-integrity of \(G\), \(\mathrm{VNI}(G)\), is defined to be \(\mathrm{VNI}(G) = \displaystyle\min_{S\subseteq V(G)} \{|S| + w(G/S)\}\), where \(S\) is any vertex subversion strategy of \(G\), and \(w(G/S)\) is the maximum order of the components of \(G/S\). In this paper, we show the minimum and the maximum vertex-neighbor-integrity among all trees with any fixed order, and also show that for any integer \(l\) between the extreme values there is a tree with the vertex-neighbor-integrity \(l\).

Let \(G\) be a graph of size \(\binom{n+1}{2}\) for some integer \(n \geq 2\). Then \(G\) is said to have an ascending star subgraph decomposition if \(G\) can be decomposed into \(n\) subgraphs \(G_1, G_2, \ldots, G_n\) such that each \(G_i\) is a star of size \(i\) with \(1 \leq i \leq n\). We shall prove in this paper that a star forest with size \(\binom{n+1}{2}\) possesses an ascending star subgraph decomposition under some conditions on the number of components or the size of components.

Let \(G\) and \(H\) be connected graphs and let \(G \square H\) be the Cartesian product of \(G\) by \(H\). A lower and an upper bound for the independence number of the Cartesian product of graphs is proved for the case, where one of the factors is bipartite. Cartesian products with one factor being an odd path or an odd cycle are considered as well.

It is proved in particular that if \(S_1 + S_2\) is a largest 2-independent set of a graph \(G\), such that \(|S_2|\) is as small as possible and if \(|S_2| \leq n+2\), then \(\alpha(G \square P_{2n+1}) = (n+1)|S_1| + n|S_2|\). A similar result is shown for the Cartesian product with an odd cycle. It is finally proved that \(\alpha(C_{2k+1} \square C_{2n+1}) = k(2n+1)\), extending a result of Jha and Slutzki.