A family \(\mathcal{G}\) of connected graphs is a family with constant metric dimension if \(\dim(G)\) is finite and does not depend upon the choice of \(G\) in \(\mathcal{G}\).

The metric dimension of some classes of plane graphs has been determined in \([3]\), \([4]\), \([5]\), \([10]\), \([13]\), and \([18]\), while the metric dimension of some classes of convex polytopes has been determined in \([8]\), and a question was raised as an open problem: Is it the case that the graph of every convex polytope has constant metric dimension? In this paper, we study the metric dimension of two classes of convex polytopes. It is shown that these classes of convex polytopes have constant metric dimension and only three vertices chosen appropriately suffice to resolve all the vertices of these classes of convex polytopes. It is natural to ask for the characterization of classes of convex polytopes with constant metric dimension.

The degree set of a graph \( G \) is the set \( S \) consisting of the distinct degrees of vertices in \( G \). In 1977, Kapoor, Polimeni, and Wall \([2]\) determined the least number of vertices among simple graphs with a given degree set. In this note, we look at the analogue problem concerning the least order and the least size of a multigraph with a given degree set.

Let \(\mathcal{P}\) be a graph property and \(G\) a graph. \(G\) is said to be \(\mathcal{P}\)-saturated if \(G\) does not have property \(\mathcal{P}\) but the addition of any edge between non-adjacent vertices of \(G\) results in a graph with property \(\mathcal{P}\). If \(\mathcal{P}\) is a bipartite graph property and \(G\) is a bipartite graph not in \(\mathcal{P}\), but the addition of any edge between non-adjacent vertices in different parts results in a graph in \(\mathcal{P}\), then \(G\) is \(\mathcal{P}\)-bisaturated. We characterize all \(\mathcal{P}\)-saturated graphs, for which \(\mathcal{P}\) is the family of interval graphs, and show that this family is precisely the family of maximally non-chordal graphs. We also present a conjectured characterization of all \(\mathcal{P}\)-bisaturated graphs, in the case where \(\mathcal{P}\) is the family of interval bigraphs, and prove it as far as current forbidden subgraph characterizations allow. We demonstrate that extremal non-interval graphs and extremal non-interval bigraphs are highly related, in that the former is simply a complete graph with \(2K_2\) removed and the latter is a complete bipartite graph with \(3K_2\) removed.

The Stein-Lovasz Theorem can be used to get existence results for some combinatorial problems using constructive methods rather than probabilistic methods. In this paper, we discuss applications of the Stein-Lovasz Theorem to some combinatorial set systems and arrays, including perfect hash families, separating hash families, splitting systems, covering designs, lotto designs and \( A \)-free systems. We also compare some of the bounds obtained from the Stein-Lovasz Theorem to those using the basic probabilistic method.

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.