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{]}^{\ast }$ denote the set of integers $\{-\frac{n-1}{2},\dots ,\frac{n-1}{2}\}$ if $n$ is odd, and $\{-\frac{n}{2},\dots ,\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{]}^{\ast }$, such that the induced vertex labeling $f^{\ast }$ given by $f^{\ast }(u)=\sum _{uv\in E(G)}f(uv)$ is a bijection $f^{\ast }:V(G)\to [p{]}^{\ast }$. 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 $\le 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\ge 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)\ne s(v)$ in ${\mathbb{Z}}_k$ for all pairs $u,v$ of adjacent vertices of $G$. The modular chromatic index ${\chi }_m^{\prime }(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^{\prime }(G)\ge \chi (G)$. In particular, it is shown that if $G$ is a graph with $\chi (G)\equiv 2\mathrm{mod}4$ for which every proper $\chi (G)$-coloring of $G$ results in color classes of odd size, then ${\chi }_m^{\prime }(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\le {\chi }_m^{\prime }(G)\le 3$ and it is determined when each of these two values occurs. There is a discussion on the relationship between ${\chi }_m^{\prime }(G)$ and ${\chi }_m^{\prime }(H)$ when $H$ is a subgraph of $G$.

Let $[n{]}^{\ast }$ denote the set of integers $\{-\frac{n-1}{2},\dots ,\frac{n+1}{2}\}$ if $n$ is odd, and $\{-\frac{n}{2},\dots ,\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{]}^{\ast }$, such that the induced vertex labeling $f^{\ast }$ given by $f^{\ast }(u)=\sum _{uv\in E(G)}f(uv)$ is a bijection $f^{\ast }:V(G)\to [p{]}^{\ast }$. 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^{\ast }:E(G)\to A$ defined by $f^{\ast }(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^{\ast }(e)=a$, respectively. A graph $G$ is $A$-cordial if there exists a vertex labeling $f$ such that $|n_a(f)–n_b(f)|\le 1$ and $|m_a(f)–m_b(f)|\le 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\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{P}_n$, cylinders $P_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{C}_n$, and tori $C_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{C}_n$. For each $m$ and $n$ we determine $\chi ((P_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{P}_n{)}^2)$, $\chi ((P_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{C}_n{)}^2)$, and in some cases $\chi ((C_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{C}_n{)}^2)$ while giving sharp bounds to the latter. We show that $\chi ((C_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{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\ge 5$) and $n$ ($n\ge 5$), we have $5\le \chi ((C_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{C}_n{)}^2)\le 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,\dots ,p–1\}$ such that $f^{+}(E(G))=\{k,k+1,k+2,\dots ,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\le 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.

An efficient method for generating level sequence representations of rooted trees in a well-defined order was developed by Beyer and Hedetniemi. In this paper, we extend Beyer and Hedetniemi’s approach to produce an algorithm for parallel generation of rooted trees. This is accomplished by defining the lexicographic distance between two rooted trees to be the number of rooted trees between them in the ordering of trees produced by the Beyer and Hedetniemi algorithm. Formulas are provided for the lexicographic distance between rooted trees with certain structures. In addition, we present algorithms for ranking and unranking rooted trees based on the ordering of the trees that is induced by the Beyer and Hedetniemi generation algorithm.

A fall coloring of a graph $G$ is a color partition of the vertex set of $G$ in such a way that every vertex of $G$ is a colorful vertex in $G$ (that is, it has at least one neighbor in each of the other color classes). The fall coloring number ${\chi }_f(G)$ of $G$ is the minimum size of a fall color partition of $G$ (when it exists). In this paper, we show that the Mycielskian $\mu (G)$ of any graph $G$ does not have a fall coloring and that the generalized Mycielskian ${\mu }_m(G)$ of a graph $G$ may or may not have a fall coloring. More specifically, we show that if $G$ has a fall coloring, then ${\mu }_{3m}(G)$ has also a fall coloring for $m\ge 1$, and that ${\chi }_f({\mu }_{3m}(G))\le {\chi }_f(G)+1$.

For a positive integer $d$, a set $S$ of positive integers is $differenced-free$ if $|x–y|\ne d$ for all $x,y\in S$. We consider the following Ramsey-theoretical question: Given $d,k,r\in {\mathbb{Z}}^{+}$, what is the smallest integer $n$ such that every $r$-coloring of $[1,n]$ contains a monochromatic $k$-element difference $d$-free set? We provide a formula for this $n$. We then consider the more general problem where the monochromatic $k$-element set must avoid a given set of differences rather than just one difference.

The covering number for a subset of leaves in a finite rooted tree is defined as the number of subtrees which remain after deleting all the paths connecting the root and the other leaves. We find the formula for the total sum (hence the average) of the covering numbers for a given subset of labeled leaves over all unordered binary trees with $n$ leaves.