The distribution of distances in the star graph \( S{T_n} \) (\(1 < n \in \mathbb{Z}\)) is established, and subsequently a threaded binary tree is obtained that realizes an orientation of \( S{T_n} \) whose levels are given by the distances to the identity permutation, via a pruning algorithm followed by a threading algorithm. In the process, the distributions of distances of the efficient dominating sets of \( S{T_n} \) are determined.

A set \(D\) of vertices in a graph \(G = (V, E)\) is a locating-dominating set if for every two vertices \(u, v\) in \(V \setminus D\), the sets \(N(u) \cap D\) and \(N(v) \cap D\) are non-empty and different. We establish two equivalent conditions for trees with unique minimum locating-dominating sets.

Let \( [n]^* \) denote the set of integers \(\{-\frac{n-1}{2}, \ldots, \frac{n-1}{2}\}\) if \(n\) is odd, and \(\{-\frac{n}{2}, \ldots, \frac{n}{2}\} \setminus \{0\}\) if \(n\) is even. A super edge-graceful labeling \(f\) of a graph \(G\) of order \(p\) and size \(q\) is a bijection \(f : E(G) \to [q]^*\), such that the induced vertex labeling \(f^*\) given by \(f^*(u) = \sum_{uv \in E(G)} f(uv)\) is a bijection \(f^* : V(G) \to [p]^*\). A graph is super edge-graceful if it has a super edge-graceful labeling. We prove that total stars and total cycles are super edge-graceful.

A total dominating function (TDF) of a graph \( G = (V, E) \) is a function \( f : V \to [0,1] \) such that for all \( v \in V \), the sum of the function values over the open neighborhood of \( v \) is at least one. A minimal total dominating function (MTDF) \( f \) is a TDF such that \( f \) is not a TDF if the value of \( f(v) \) is decreased for any \( v \in V \). A convex combination of two MTDFs \( f \) and \( g \) of a graph \( G \) is given by \( h_\lambda = \lambda f + (1-\lambda)g \), where \( 0 < \lambda < 1 \). A basic minimal total dominating function (BMTDF) is an MTDF which cannot be expressed as a convex combination of two or more different MTDFs. In this paper, we study the structure of the set of all minimal total dominating functions (\(\mathfrak{F}_T\)) of some classes of graphs and characterize the graphs having \(\mathfrak{F}_T\) isomorphic to one simplex.

Vertex elimination orderings play a central role in many portions of graph theory and are exemplified by the so-called `perfect elimination orderings’ of chordal graphs. But perfect elimination orderings and chordal graphs enjoy many special advantages that overlap in more general settings: the random way that simplicial vertices can be chosen, always having a choice of simplicial vertices, the hereditary nature of being simplicial, and the neutral effect of deleting a simplicial vertex on whether the graph is chordal. A graph metatheory of vertex elimination formalizes such distinctions for general vertex elimination and examines them with simple theorems and delineating counterexamples.

In this paper we give a survey of all graphs of order \(\leq 5\) which are difference graphs and we show that some families of graphs are difference graphs.

The edge-bandwidth of a graph \( G \) is the smallest number \( b \) for which there exists an injective labeling of \( E(G) \) with integers such that the difference between the labels of any pair of adjacent edges is at most \( b \). The edge-bandwidth of a torus (a product of two cycles) has been computed within an additive error of \( 5 \). In this paper, we improve the upper bound, reducing the error to \( 3 \).

Let \( G \) be a connected graph of order 3 or more and \( c : E(G) \to \mathbb{Z}_k \) (\( k \geq 2 \)) an edge coloring of \( G \) where adjacent edges may be colored the same. The color sum \( s(v) \) of a vertex \( v \) of \( G \) is the sum in \( \mathbb{Z}_k \) of the colors of the edges incident with \( v \). An edge coloring \( c \) is a modular neighbor-distinguishing \( k \)-edge coloring of \( G \) if \( s(u) \neq s(v) \) in \( \mathbb{Z}_k \) for all pairs \( u, v \) of adjacent vertices of \( G \). The modular chromatic index \( \chi_m'(G) \) of \( G \) is the minimum \( k \) for which \( G \) has a modular neighbor-distinguishing \( k \)-edge coloring. For every graph \( G \), it follows that \( \chi_m'(G) \geq \chi(G) \). In particular, it is shown that if \( G \) is a graph with \( \chi(G) \equiv 2 \mod 4 \) for which every proper \( \chi(G) \)-coloring of \( G \) results in color classes of odd size, then \( \chi_m'(G) > \chi(G) \). The modular chromatic indices of several well-known classes of graphs are determined. It is shown that if \( G \) is a connected bipartite graph, then \( 2 \leq \chi_m'(G) \leq 3 \) and it is determined when each of these two values occurs. There is a discussion on the relationship between \( \chi_m'(G) \) and \( \chi_m'(H) \) when \( H \) is a subgraph of \( G \).

Let \( [n]^* \) denote the set of integers \(\{-\frac{n-1}{2}, \ldots, \frac{n+1}{2}\}\) if \( n \) is odd, and \(\{-\frac{n}{2}, \ldots, \frac{n}{2}\} \setminus \{0\}\) if \( n \) is even. A super edge-graceful labeling \( f \) of a graph \( G \) of order \( p \) and size \( q \) is a bijection \( f : E(G) \to [q]^* \), such that the induced vertex labeling \( f^* \) given by \( f^*(u) = \sum_{uv \in E(G)} f(uv) \) is a bijection \( f^* : V(G) \to [p]^* \). A graph is super edge-graceful if it has a super edge-graceful labeling. We prove that all complete tripartite graphs \( K_{a,b,c} \), except \( K_{1,1,2} \), are super edge-graceful.

Suppose \( G \) is a graph with vertex set \( V(G) \) and edge set \( E(G) \), and let \( A \) be an additive Abelian group. A vertex labeling \( f: V(G) \to A \) induces an edge labeling \( f^*: E(G) \to A \) defined by \( f^*(xy) = f(x) + f(y) \). For \( a \in A \), let \( n_a(f) \) and \( m_a(f) \) be the number of vertices \( v \) and edges \( e \) with \( f(v) = a \) and \( f^*(e) = a \), respectively. A graph \( G \) is \( A \)-cordial if there exists a vertex labeling \( f \) such that \( |n_a(f) – n_b(f)| \leq 1 \) and \( |m_a(f) – m_b(f)| \leq 1 \) for all \( a, b \in A \). When \( A = \mathbb{Z}_k \), we say that \( G \) is \( k \)-cordial instead of \( \mathbb{Z}_k \)-cordial. In this paper, we investigate certain regular graphs and ladder graphs that are \( 4 \)-cordial and we give a complete characterization of the \( 4 \)-cordiality of the complete \( 4 \)-partite graph. An open problem about which complete multipartite graphs are not \( 4 \)-cordial is given.