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.

The square \( G^2 \) of a graph \( G \) is a graph with the same vertex set as \( G \) in which two vertices are joined by an edge if their distance in \( G \) is at most two. For a graph \( G \), \( \chi(G^2) \), which is also known as the distance two coloring number of \( G \), is studied. We study coloring the square of grids \( P_m \Box P_n \), cylinders \( P_m \Box C_n \), and tori \( C_m \Box C_n \). For each \( m \) and \( n \) we determine \( \chi((P_m \Box P_n)^2) \), \( \chi((P_m \Box C_n)^2) \), and in some cases \( \chi((C_m \Box C_n)^2) \) while giving sharp bounds to the latter. We show that \( \chi((C_m \Box C_n)^2) \) is at most \( 8 \) except when \( m = n = 3 \), in which case the value is \( 9 \). Moreover, we conjecture that for every \( m \) (\( m \geq 5 \)) and \( n \) (\( n \geq 5 \)), we have \( 5 \leq \chi((C_m \Box C_n)^2) \leq 7 \).

Given any positive integer \( k \), a \((p,q)\)-graph \( G = (V, E) \) is strongly \( k \)-indexable if there exists a bijection \( f : V \to \{0,1,2,\ldots,p – 1\} \) such that \( f^+(E(G)) = \{k,k+1,k+2,\ldots,k+q-1\} \) where \( f^+(uv) = f(u) + f(v) \) for any edge \( uv \in E \); in particular, \( G \) is said to be strongly indexable when \( k = 1 \). For any strongly \( k \)-indexable \((p, q)\)-graph \( G \), \( q \leq 2p – 3 \) and if, in particular, \( q = 2p – 3 \) then \( G \) is called a maximal strongly indexable graph. In this paper, necessary conditions for an Eulerian \((p,q)\)-graph \( G \) to be strongly \( k \)-indexable have been obtained. Our main focus is to initiate a study of maximal strongly indexable graphs and, on this front, we strengthen a result of G. Ringel on certain outerplanar graphs.

Let \( G \) be a connected graph. A vertex \( r \) resolves a pair \( u,v \) of vertices of \( G \) if \( u \) and \( v \) are different distances from \( r \). A set \( R \) of vertices of \( G \) is a resolving set for \( G \) if every pair of vertices of \( G \) is resolved by some vertex of \( R \). The smallest cardinality of a resolving set is called the metric dimension of \( G \). A vertex \( r \) strongly resolves a pair \( u,v \) of vertices of \( G \) if there is some shortest \( u-r \) path that contains \( v \) or a shortest \( v-r \) path that contains \( u \). A set \( S \) of vertices of \( G \) is a strong resolving set for \( G \) if every pair of vertices of \( G \) is strongly resolved by some vertex of \( S \); and the smallest cardinality of a strong resolving set of \( G \) is called the strong dimension of \( G \). The problems of finding the metric dimension and strong dimension are NP-hard. Both the metric and strong dimension can be found efficiently for trees. In this paper, we present efficient solutions for finding the strong dimension of distance-hereditary graphs, a class of graphs that contains the trees.