For an ordered set $W=\{w_1,w_2,\dots ,w_k\}$ of $k$ distinct vertices in a nontrivial connected graph $G$, the metric code of a vertex $v$ of $G$ with respect to $W$ is the $k$-vector
$$\text{code}(v)=(d(v,w_1),d(v,w_2),\dots ,d(v,w_k)),$$
where $d(v,w_i)$ is the distance between $v$ and $w_i$ for $1\le i\le k$. The set $W$ is a local metric set of $G$ if $\text{code}(u)\ne \text{code}(v)$ for every pair $u,v$ of adjacent vertices of $G$. The minimum positive integer $k$ for which $G$ has a local metric set of cardinality $k$ is the local metric dimension $\text{lmd}(G)$ of $G$. We determine the local metric dimensions of joins and compositions of some well-known classes of graphs, namely complete graphs, cycles, and paths. For a nontrivial connected graph $G$, a vertex $v$ of $G$, and an edge $e$ of $G$, where $v$ is not a cut-vertex and $e$ is not a bridge, it is shown that $\text{lmd}(G–v)\le \text{lmd}(G)+\text{deg}(v)$ and $\text{lmd}(G–e)\le \text{lmd}(G)+2.$ The sharpness of these two bounds is studied. We also present several open questions in this area of research.

Let $G$ be a connected graph. In this paper, we introduce the concepts of vertex-to-clique $radius$ $r_1$, vertex-to-clique $diameter$ $d_1$, clique-to-vertex $radius$ $r_2$, clique-to-vertex $diameter$ $d_2$, clique-to-clique $radius$ $r_3$, and clique-to-clique $diameter$ $d_3$ in $G$. We prove that for any connected graph, $r_i\le d_i\le 2r_i+1$ for $i=1,2,3$. We also find expressions for $d_1$, $d_2$, and $d_3$ for a tree $T$ in terms of $r_1$, $r_2$, and $r_3$ respectively, which determine the cardinality of each $Z_i(T)$, where $Z_i(T)$ is the vertex-to-clique, the clique-to-vertex, and the clique-to-clique center respectively of $T$ for $i=1,2,3$. If $G$ is a graph that is not a tree and if $g(G)$ denotes the girth of the graph, then its relation with each of $d_1$, $d_2$, and $d_3$ is discussed. We also characterize the class of graphs $G$ such that $G$ is not a tree, $d_3\ne 0$, and $g(G)=2d_3+3$.

A tournament is an orientation of a complete graph, and a multipartite or $c$-partite tournament is an orientation of a complete $c$-partite graph. If we speak of a path, then we mean a directed path.

Let $D$ be a regular $c$-partite tournament with $r$ vertices in each partite set, and let $X\subseteq V(D)$ be an arbitrary set with exactly $2$ vertices from each partite set. For all $c\ge 4$, the authors determined in a recent article the minimal value $g(c)$ such that $D–X$ is Hamiltonian for every regular multipartite tournament with $r\ge g(c)$. In this paper, we will supplement this result by postulating a given path covering number instead of the Hamiltonicity of the digraph $D–X$. This means, for all $c\ge 4$ and $k\ge 1$, we will determine the minimal value $h(k,c)$ such that $D–X$ can be covered by at most $k$ paths for every regular $c$-partite tournament with $r\ge h(k,c)$. Moreover, we will present the minimal path covering number of $D–X$, if $D$ is a regular $3$-partite tournament and $X$ contains exactly $s$ vertices ($s\ge 2$) from every partite set.

We investigate the problem of decomposing the edges of a connected circulant graph with $n$ vertices and generating set $S$ into isomorphic subgraphs, each having $n$ edges. For $8$-regular circulants, we show that this is always possible when $s+2\le \frac{n}{4}$ for all edge lengths $s\in S$.

This paper continues the results of “Domination Cover Pebbling: Graph Families.” An almost sharp bound for the domination cover pebbling (DCP) number, $\psi (G)$, for graphs $G$ with specified diameter has been computed. For graphs of diameter two, a bound for the ratio between $\lambda (G)$, the cover pebbling number of $G$, and $\psi (G)$ has been computed. A variant of domination cover pebbling, called subversion DCP, is introduced, and preliminary results are discussed.

A graph $G$ has a representation modulo $n$ if there exists an injective map $f:V(G)\to \{0,1,\dots ,n-1\}$ such that vertices $u$ and $v$ are adjacent if and only if $f(u)–f(v)$ is relatively prime to $n$. The representation number $rep(G)$ is the smallest $n$ such that $G$ has a representation modulo $n$. In 2000, Evans, Isaak, and Narayan determined the representation number of a complete graph minus a path. In this paper, we refine their methods and apply them to the family of complete graphs minus a disjoint union of paths.

Let $G=(V,E)$ be a graph and $\overline{G}$ be the complement of $G$. The complementary prism of $G$, denoted $G\overline{G}$, is the graph formed from the disjoint union of $G$ and $\overline{G}$ by adding the edges of a perfect matching between the corresponding vertices of $G$ and $\overline{G}$. A set $D\subseteq V(G)$ is a locating-dominating set of $G$ if for every $u\in V(G)\setminus D$, its neighborhood $N(u)\cap D$ is nonempty and distinct from $N(v)\cap D$ for all $v\in V(G)\setminus D$ where $v\ne u$. The locating-domination number of $G$ is the minimum cardinality of a locating-dominating set of $G$. In this paper, we study locating-domination of complementary prisms. We determine the locating-domination number of $G\overline{G}$ for specific graphs $G$ and characterize the complementary prisms with small locating-domination numbers. We also present upper and lower bounds on the locating-domination numbers of complementary prisms, and we show that all values between these bounds are achievable.

A disjoint multiple paths problem asks if there exist paths between a given set of vertices. Constraints are applied so that paths are not allowed to share vertices (vertex disjoint multiple paths) or share edges (edge disjoint multiple paths). The vertex disjoint multiple paths problem is one of the classic NP-complete problems presented by Karp [1]. The edge disjoint multiple paths problem is also NP-complete since it is easily transformed from the vertex disjoint multiple paths problem. Because of its importance in electronic circuit design, studies are done for restricted cases. The edge disjoint multiple paths problem remains NP-complete for acyclic graphs and planar graphs. Furthermore, the edge disjoint multiple paths problem remains NP-complete if the graph is limited to an undirected mesh.

In this paper, the edge disjoint multiple paths problem when constructed over a directed mesh is discussed. We found that the multiple paths problem remains NP-complete in this special case. Three polynomial time algorithms are presented in which the following restrictions are made: (i) disjoint paths with the same origin row, the same destination row, distinct origin columns, and distinct destination columns, (ii) disjoint paths with the same origin column, the same destination column, distinct origin rows, and distinct destination rows, and (iii) disjoint paths with the same origin row, distinct origin columns, and distinct destination rows.

We discuss a transform on the set of rational functions over the finite field ${\mathbb{F}}_q$. For a subclass of these functions, the transform yields a polynomial and its factorization as a product of the set of monic irreducible polynomials, all of which share a common property $P$ that depends on the choice of rational function. A general formula is derived from the factorization for the number of monic irreducible polynomials of degree $n$ having property $P$. However, it is also possible in some instances to exploit the properties of the factorization to obtain a “closed” form of the answer more directly. We illustrate the method with four examples, two of which appear in the literature. In particular, we give alternative proofs for a result of L. Carlitz on the number of monic irreducible self-reciprocal polynomials and a remarkable result of S. D. Cohen on the number of $(r,m)$-polynomials, that is, monic irreducible polynomials of the form $f(x^r)$ of degree $mr$. We also give a generalization of the factorization of $x^{q-1}–1$ over ${\mathbb{F}}_q$ that includes the factorization of $x^{(q-1{)}^2}–1$. The new results concern translation invariant polynomials, which lead to a consideration of the orders of elements in ${\overline{\mathbb{F}}}_q$, the algebraic closure of ${\mathbb{F}}_q$. We show that there are an infinite number of $\theta \in {\overline{\mathbb{F}}}_q$ such that $\text{ord}(\theta )$ and $\text{ord}(r(\theta ))$ are related, in the sense that given one, one can infer information about the other.

Let $G$ be a graph with $v$ vertices. If there exists a collection of lists of colors $\{S_1,S_2,\dots ,S_v\}$ on its vertices, each of size $k$, such that there exists a unique proper coloring for $G$ from this list of colors, then $G$ is called a $uniquelyk-listcolorablegraph$. In this note, we present a uniquely $3$-list colorable, planar, and $K_4$-free graph. It is a counterexample to a conjecture by Ch. Eslahchi, M. Ghebleh, and H. Hajiabolhassan [3].

For any integers $k,d\ge 1$, a $(p,q)$-graph $G$ with vertex set $V(G)$ and edge set $E(G)$, where $p=|V(G)|$ and $q=|E(G)|$, is said to be $(k,d)$-strongly indexable (in short $(\mathbf{\text{k, d}})$-\textbf{SI}) if there exists a pair of functions $(f,f^{+})$ that assigns integer labels to the vertices and edges, i.e., $f:V(G)\to \{0,1,\dots ,p-1\}$ and $f^{+}:E(G)\to \{k,k+d,k+2d,\dots ,k+(q-1)d\}$, such that $f^{+}(u,v)=f(u)+f(v)$ for any $(u,v)\in E(G)$. We determine here classes of spiders that are $(1,2)$-SI graphs. We show that every given $(1,2)$-SI spider can be extended to an $(1,2)$-SI spider with arbitrarily many legs.

In this paper, we obtain some new results, using inequalities such as Hölder and Minkowski, etc., on the existence of balanced arrays (B-arrays) with two levels and of strength six. We then discuss the use of these results to obtain the maximum number of constraints for B-arrays with given values of the parameter vector ${\underset{\_}{\mu }}^{\prime }$. We also include some illustrative examples.

A construction of a minimum cycle basis for the wreath product of a star by a path, two stars and a star by a wheel is given. Moreover, the basis numbers of these products are determined.

For any $h\in \mathbb{N}$, a graph $G=(V,E)$ is said to be $h$-magic if there exists a labeling $l:E(G)\to {\mathbb{Z}}_h\setminus \{0\}$ such that the induced vertex labeling $l^{+}:V(G)\to {\mathbb{Z}}_h$, defined by

$$l^{+}(v)=\sum _{uv\in E(G)}l(uv),$$

is a constant map. When this constant is $0$, we call $G$ a zero-sum $h$-magic graph. The null set of $G$ is the set of all natural numbers $h\in \mathbb{N}$ for which $G$ admits a zero-sum $h$-magic labeling. A graph $G$ is said to be uniformly null if every magic labeling of $G$ induces a zero sum. In this paper, we will identify the null sets of certain planar graphs such as wheels and fans.

In this paper, we find six new weighing matrices of order $2n$ and weight $2n-9$ constructed from two circulants, by establishing various patterns on the locations of the nine zeros in a potential solution.

In the past few years, several studies have appeared that relate to the existence of $\mathbb{Z}$-cyclic directed-triplewhist tournaments and $\mathbb{Z}$-cyclic ordered-triplewhist tournaments. In these studies, the number of players in the tournament is taken to be a prime $p$ of the form $p\equiv 2^k+1(\mathrm{mod}{2}^k+1)$, where $k\ge 2$. For the cases $k=2,3,4$ it has been shown [6,4,5,12] that $\mathbb{Z}$-cyclic directed-triplewhist tournaments and $\mathbb{Z}$-cyclic ordered-triplewhist tournaments exist for all such primes except for the impossible cases $p=5,13,17$. For the cases $k=5,6,7$ it has been shown [13] that $\mathbb{Z}$-cyclic directed-triplewhist tournaments exist for all such primes less than $\mathrm{3,200,000}$ and that $\mathbb{Z}$-cyclic ordered-triplewhist tournaments exist for all such primes less than $\mathrm{3,200,000}$ with the exception that existence or non-existence of these designs for $p=97,193,449,577,641,1409$ is an open question. Here the case $k=8$ is considered. It is established that $\mathbb{Z}$-cyclic directed-triplewhist tournaments and $\mathbb{Z}$-cyclic ordered-triplewhist tournaments exist for all primes $p\equiv 257(\mathrm{mod}512)$, $p\le \mathrm{6,944,177}$, except possibly for $p=257,769,3329$. For $p=3329$ we are able to construct a $\mathbb{Z}$-cyclic directed-triplewhist tournament, but the existence of a $\mathbb{Z}$-cyclic ordered-triplewhist tournament remains an open question. Furthermore, for each type of design it is conjectured that our basic constructions will produce these designs whenever $p>\mathrm{5,299,457}$.

The domination graph of a digraph $D$, denoted $\text{dom}(D)$, is created using the vertex set of $D$ and edge $uv\in E(\text{dom}(D))$ whenever $(u,z)\in A(D)$ or $(v,z)\in A(D)$ for any other vertex $z\in V(D)$. Specifically, we consider directed graphs whose underlying graphs are isomorphic to their domination graphs. In particular, digraphs are completely characterized where $U{G}^c(D)$ is the union of two disjoint paths.