Let \(G\) be a graph with vertex set \(V(G)\) and edge set \(E(G)\). A \((p, q)\)-graph \(G = (V, E)\) is said to be \(AL(k)\)-traversal if there exists a sequence of vertices \(\{v_1, v_2, \ldots, v_p\}\) such that for each \(i = 1, 2, \ldots, p-1\), the distance between \(v_i\) and \(v_{i+1}\) is equal to \(k\). We call a graph \(G\) a \(k\)-steps Hamiltonian graph if it has an \(AL(k)\)-traversal in \(G\) and the distance between \(v_p\) and \(v_1\) is \(k\). In this paper, we completely classify whether a subdivision graph of a cycle with a chord is \(2\)-steps Hamiltonian.

A triple system is decomposable if the blocks can be partitioned into two sets, each of which is itself a triple system. It is cyclically decomposable if the resulting triple systems are themselves cyclic. In this paper, we prove that a cyclic two-fold triple system is cyclically indecomposable if and only if it is indecomposable. Moreover, we construct cyclic three-fold triple systems of order $v$ which are cyclically indecomposable but decomposable for all \(v \equiv 3 \mod 6\). The only known example of a cyclic three-fold triple system of order \(v \equiv 1 \mod 6\) that is cyclically indecomposable but decomposable was a triple system on 19 points. We present a construction which yields infinitely many such triple systems of order \(v \equiv 1 \mod 6\). We also give several examples of cyclically indecomposable but decomposable cyclic four-fold triple systems and few constructions that yield infinitely many such triple systems.

The spectrum problem for decomposition of trees with up to eight edges was introduced and solved in 1978 by Huang and Rosa. Additionally, the packing problem was settled for all trees with up to six edges by Roditty. For the first time, we consider obtaining all possible leaves in a maximum tree-packing of \(K_n\), which we refer to as the spectrum problem for packings of complete graphs. In particular, we completely solve this problem for trees with at most five edges. The packing designs are used in developing optimal error-correcting codes, which have applications in biology, such as in DNA sequencing.

Let \(G\) be a graph with vertex set \(V(G)\) and edge set \(E(G)\). A labeling \(f\) of a graph \(G\) is said to be edge-friendly if \(|e_f(0) – e_f(1)| \leq 1\), where \(e_f(i) = \text{card}\{e \in E(G) : f(e) = i\}\). An edge-friendly labeling \(f : E(G) \to \mathbb{Z}_2\) induces a partial vertex labeling \(f^+ : V(G) \to A\) defined by \(f^+(x) = 0\) if the edges incident to \(x\) are labeled \(0\) more than \(1\). Similarly, \(f^+(x) = 1\) if the edges incident to \(x\) are labeled \(1\) more than \(0\). \(f^+(x)\) is not defined if the edges incident to \(x\) are labeled \(1\) and \(0\) equally. The edge-balance index set of the graph \(G\), \(EBI(G)\), is defined as \(\{|v_f(0) – v_f(1)| : \text{the edge labeling } f \text{ is edge-friendly}\}\), where \(v_f(i) = \text{card}\{v \in V(G) : f^+(v) = i\}\).

An \(n\)-wheel is a graph consisting of \(n\) cycles, with each vertex of the cycles connected to one central hub vertex. The edge-balance index sets of \(n\)-wheels are presented.

A set of vertices \(W\) \({locally\; resolves}\) a graph \(G\) if every pair of adjacent vertices is uniquely determined by its coordinate of distances to the vertices in \(W\). The minimum cardinality of a local resolving set of \(G\) is called the \({local\; metric\; dimension}\) of \(G\). A graph \(G\) is called a \(k\)-regular graph if every vertex of \(G\) is adjacent to \(k\) other vertices of \(G\). In this paper, we determine the local metric dimension of an \((n-3)\)-regular graph \(G\) of order \(n\), where \(n \geq 5\).

Let \(\mathcal{G}_n\) be the set of all simple loopless undirected graphs on \(n\) vertices. Let \(T\) be a linear mapping, \(T: \mathcal{G}_n \to \mathcal{G}_n\), such that the dot product dimension of \(T(G)\) is the same as the dot product dimension of \(G\) for any \(G \in \mathcal{G}_n\). We show that \(T\) is necessarily a vertex permutation. Similar results are obtained for mappings that preserve sets of graphs with specified dot product dimensions.

A permutation \(\pi\) on a set of positive integers \(\{a_1, a_2, \ldots, a_n\}\) is said to be graphical if there exists a graph containing exactly \(a_i\) vertices of degree \(\pi(a_i)\) for each \(i\) (\(1 \leq i \leq n\)). It has been shown that for positive integers with \(a_1 < a_2 < \ldots < a_n\), if \(\pi(a_n) = a_n\), then the permutation \(\pi\) is graphical if and only if the sum \(\sum_{i=1}^n a_i \pi(a_i)\) is even and \(a_n \leq \sum_{i=1}^{n-1} a_i\pi(a_i)\).

We use a criterion of Tripathi and Vijay to provide a new proof of this result and to establish a similar result for permutations \(\pi\) such that \(\pi(a_{n-1}) = a_n\). We prove that such a permutation is graphical if and only if the sum \(\sum_{i=1}^n a_i \pi(a_i)\) is even and \(a_na_{n-1} \leq a_{n-1}(a_{n-1} – 1) + \sum_{i\neq n-1} a_i\pi(a_i)\). We also consider permutations such that \(\pi(a_n) = a_{n-1}\) and, more generally, those such that \(\pi(a_n) = a_{n-j}\) for some \(j\) (\(1 < j < n\)).

A \(k\)-labeling of a graph is a labeling of the vertices of the graph by \(k\)-tuples of non-negative integers such that two vertices of \(G\) are adjacent if and only if their label \(k\)-tuples differ in each coordinate. The dimension of a graph \(G\) is the least \(k\) such that \(G\) has a \(k\)-labeling.

Lovász et al. showed that for \(n \geq 3\), the dimension of a path of length \(n\) is \((\log_2 n)^+\). Lovász et al. and Evans et al. determined the dimension of a cycle of length \(n\) for most values of \(n\). In the present paper, we obtain the dimension of a caterpillar or provide close bounds for it in various cases.

We consider a discrete-time dynamic problem in graphs in which the goal is to maintain a dominating set over an infinite sequence of time steps. At each time step, a specified vertex in the current dominating set must be replaced by a neighbor. In one version of the problem, the only change to the current dominating set is replacement of the specified vertex. In another version of the problem, other vertices in the dominating set can also be replaced by neighbors. A variety of results are presented relating these new parameters to the eternal domination number, domination number, and independence number of a graph.

The Turán number \(ex(m, G)\) of the graph \(G\) is the maximum number of edges of an \(m\)-vertex simple graph having no \(G\) as a subgraph. A \emph{star} \(S_r\) is the complete bipartite graph \(K_{1,r}\) (or a tree with one internal vertex and \(r\) leaves) and \(pS_r\) denotes the disjoint union of \(p\) copies of \(S_r\). A result of Lidický et al. (Electron. J. Combin. \(20(2)(2013) P62\)) implies that \(ex(m,pS_r) = \left\lfloor\frac{(m-p+1)(r-1)}{2}\right\rfloor + (p-1)m – \binom{p}{2}\) for \(m\) sufficiently large. In this paper, we give another proof and show that \(ex(m,pS_r) = \left\lfloor \frac{(m-p+1)(r-1)}{2}\right\rfloor + (p-1)m – \binom{p}{2}\) for all \(r \geq 1\), \(p \geq 1\), and \(m \geq \frac{1}{2}r^2p(p – 1) + p – 2 + \max\{rp, r^2 + 2r\}\).