Source author record

Douglas F. Rall

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

17works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Total isolation game in graphs

The total isolation game is played on a graph $G$ by two players who take turns playing a vertex such that if $S$ is the set of already played vertices, then a vertex can be selected only if it is adjacent to a vertex that belongs to a (nontrivial) component of the graph $G - N_G(S)$ of order at least $2$ or a vertex that is isolated in $G - N_G(S)$ and belongs to the set $S$ , where $N_G(S)$ is the set of vertices adjacent to a vertex in $S$ . Dominator wishes to finish the game with the minimum number of played vertices, while Staller has the opposite goal. The game total isolation number $ι_{\rm gt}(G)$ is the number of moves in the Dominator-start game where both players play optimally. We prove that if $G$ is a connected graph of order $n \ge 3$ , then $ι_{\rm gt}(G) < \frac{5}{6}n$ . Furthermore if $G$ has minimum degree at least $2$ , then we prove that $ι_{\rm gt}(G) \le \frac{3}{4}n$ . More generally, if $G$ is a connected graph of order $n \ge 3$ with minimum degree $δ$ where $δ\ge 2$ , then we prove that $ι_{\rm gt}(G) \le \left( \frac{2δ-1}{3δ-2} \right) n$ . Among other results it is proved that if $G$ is a graph of order $n$ with diameter $2$ , then $ι_{\rm gt}(G) \le \frac{2}{3}n$ .

preprint2022arXiv

On independent domination in direct products

In \cite{nr-1996} Nowakowski and Rall listed a series of conjectures involving several different graph products. In particular, they conjectured that $i(G\times H) \ge i(G)i(H)$ where $i(G)$ is the independent domination number of $G$ and $G\times H$ is the direct product of graphs $G$ and $H$ . We show this conjecture is false, and, in fact, construct pairs of graphs for which $\min\{i(G), i(H)\} - i(G\times H)$ is arbitrarily large. We also give the exact value of $i(G\times K_n)$ when $G$ is either a path or a cycle.

preprint2020arXiv

Domination in digraphs and their products

A dominating (respectively, total dominating) set $S$ of a digraph $D$ is a set of vertices in $D$ such that the union of the closed (respectively, open) out-neighborhoods of vertices in $S$ equals the vertex set of $D$ . The minimum size of a dominating (respectively, total dominating) set of $D$ is the domination (respectively, total domination) number of $D$ , denoted $γ(D)$ (respectively, $γ_t(D)$ ). The maximum number of pairwise disjoint closed (respectively,open) in-neighborhoods of $D$ is denoted by $ρ(D)$ (respectively, $ρ^{\rm o}(D)$ ). We prove that in digraphs whose underlying graphs have girth at least $7$ , the closed (respectively,open) in-neighborhoods enjoy the Helly property, and use these two results to prove that in any ditree $T$ (that is, a digraph whose underlying graph is a tree), $γ_t(T)=ρ^{\rm o}(T)$ and $γ(T)=ρ(T)$ . By using the former equality we then prove that $γ_t(G\times T)=γ_t(G)γ_t(T)$ , where $G$ is any digraph and $T$ is any ditree, each without a source vertex, and $G\times T$ is their direct product. From the equality $γ(T)=ρ(T)$ we derive the bound $γ(G\mathbin{\Box} T)\geγ(G)γ(T)$ , where $G$ is an arbitrary digraph, $T$ an arbitrary ditree and $G\mathbin{\Box} T$ is their Cartesian product. In general digraphs this Vizing-type bound fails, yet we prove that for any digraphs $G$ and $H$ , where $γ(G)\geγ(H)$ , we have $γ(G \mathbin{\Box} H) \ge \frac{1}{2}γ(G)(γ(H) + 1)$ . This inequality is sharp as demonstrated by an infinite family of examples. Ditrees $T$ and digraphs $H$ enjoying $γ(T\mathbin{\Box} H)=γ(T)γ(H)$ are also investigated.

preprint2020arXiv

General $d$ -position sets

The general $d$ -position number ${\rm gp}_d(G)$ of a graph $G$ is the cardinality of a largest set $S$ for which no three distinct vertices from $S$ lie on a common geodesic of length at most $d$ . This new graph parameter generalizes the well studied general position number. We first give some results concerning the monotonic behavior of ${\rm gp}_d(G)$ with respect to the suitable values of $d$ . We show that the decision problem concerning finding ${\rm gp}_d(G)$ is NP-complete for any value of $d$ . The value of ${\rm gp}_d(G)$ when $G$ is a path or a cycle is computed and a structural characterization of general $d$ -position sets is shown. Moreover, we present some relationships with other topics including strong resolving graphs and dissociation sets. We finish our exposition by proving that ${\rm gp}_d(G)$ is infinite whenever $G$ is an infinite graph and $d$ is a finite integer.

preprint2020arXiv

On graphs having one size of maximal open packings

A set $P$ of vertices in a graph $G$ is an open packing if no two distinct vertices in $P$ have a common neighbor. Among all maximal open packings in $G$ , the smallest cardinality is denoted $ρ^{\rm o}_L(G)$ and the largest cardinality is $ρ^{\rm o}(G)$ . There exist graphs for which these two invariants are arbitrarily far apart. In this paper we begin the investigation of the class of graphs that have one size of maximal open packings. By presenting a method of constructing such graphs we show that every graph is the induced subgraph of a graph in this class. The main result of the paper is a structural characterization of those $G$ that do not have a cycle of order less than $15$ and for which $ρ^{\rm o}_L(G)=ρ^{\rm o}(G)$ .

preprint2020arXiv

The Enclaveless Competition Game

For a subset $S$ of vertices in a graph $G$ , a vertex $v \in S$ is an enclave of $S$ if $v$ and all of its neighbors are in $S$ , where a neighbor of $v$ is a vertex adjacent to $v$ . A set $S$ is enclaveless if it does not contain any enclaves. The enclaveless number $Ψ(G)$ of $G$ is the maximum cardinality of an enclaveless set in $G$ . As first observed in 1997 by Slater [J. Res. Nat. Bur. Standards 82 (1977), 197--202], if $G$ is a graph with $n$ vertices, then $γ(G) + Ψ(G) = n$ where $γ(G)$ is the well-studied domination number of $G$ . In this paper, we continue the study of the competition-enclaveless game introduced in 2001 by Phillips and Slater [Graph Theory Notes N. Y. 41 (2001), 37--41] and defined as follows. Two players take turns in constructing a maximal enclaveless set $S$ , where one player, Maximizer, tries to maximize $|S|$ and one player, Minimizer, tries to minimize~ $|S|$ . The competition-enclaveless game number $Ψ_g^+(G)$ of $G$ is the number of vertices played when Maximizer starts the game and both players play optimally. We study among other problems the conjecture that if $G$ is an isolate-free graph of order $n$ , then $Ψ_g^+(G) \ge \frac{1}{2}n$ . We prove this conjecture for regular graphs and for claw-free graphs.

preprint2016arXiv

On minimum identifying codes in some Cartesian product graphs

An identifying code in a graph is a dominating set that also has the property that the closed neighborhood of each vertex in the graph has a distinct intersection with the set. The minimum cardinality of an identifying code, or ID code, in a graph $G$ is called the ID code number of $G$ and is denoted $\gid(G)$. In this paper, we give upper and lower bounds for the ID code number of the prism of a graph, or $G\Box K_2$ . In particular, we show that $\gid(G \Box K_2) \ge \gid(G)$ and we show that this bound is sharp. We also give upper and lower bounds for the ID code number of grid graphs and a general upper bound for $\gid(G\Box K_2)$.

preprint2016arXiv

Packing chromatic number under local changes in a graph

The packing chromatic number $χ_ρ(G)$ of a graph $G$ is the smallest integer $k$ such that there exists a $k$ -vertex coloring of $G$ in which any two vertices receiving color $i$ are at distance at least $i+1$ . It is proved that in the class of subcubic graphs the packing chromatic number is bigger than $13$ , thus answering an open problem from [Gastineau, Togni, $S$ -packing colorings of cubic graphs, Discrete Math.\ 339 (2016) 2461--2470]. In addition, the packing chromatic number is investigated with respect to several local operations. In particular, if $S_e(G)$ is the graph obtained from a graph $G$ by subdividing its edge $e$ , then $\left\lfloor χ_ρ(G)/2 \right\rfloor +1 \le χ_ρ(S_e(G)) \le χ_ρ(G)+1$ .

preprint2016arXiv

Packing chromatic number, $(1,1,2,2)$ -colorings, and characterizing the Petersen graph

The packing chromatic number $χ_ρ(G)$ of a graph $G$ is the smallest integer $k$ such that the vertex set of $G$ can be partitioned into sets $Π_1,\ldots,Π_k$ , where $Π_i$ , $i\in [k]$ , is an $i$ -packing. The following conjecture is posed and studied: if $G$ is a subcubic graph, then $χ_ρ(S(G))\le 5$ , where $S(G)$ is the subdivision of $G$ . The conjecture is proved for all generalized prisms of cycles. To get this result it is proved that if $G$ is a generalized prism of a cycle, then $G$ is $(1,1,2,2)$ -colorable if and only if $G$ is not the Petersen graph. The validity of the conjecture is further proved for graphs that can be obtained from generalized prisms in such a way that one of the two $n$ -cycles in the edge set of a generalized prism is replaced by a union of cycles among which at most one is a 5-cycle. The packing chromatic number of graphs obtained by subdividing each of its edges a fixed number of times is also considered.

preprint2016arXiv

Total Dominating Sequences in Graphs

A vertex in a graph totally dominates another vertex if they are adjacent. A sequence of vertices in a graph $G$ is called a total dominating sequence if every vertex $v$ in the sequence totally dominates at least one vertex that was not totally dominated by any vertex that precedes $v$ in the sequence, and at the end all vertices of $G$ are totally dominated. While the length of a shortest such sequence is the total domination number of $G$ , in this paper we investigate total dominating sequences of maximum length, which we call the Grundy total domination number, $γ_{\rm gr}^t(G)$ , of $G$ . We provide a characterization of the graphs $G$ for which $γ_{\rm gr}^t(G)=|V(G)|$ and of those for which $γ_{\rm gr}^t(G)=2$ . We show that if $T$ is a nontrivial tree of order~ $n$ with no vertex with two or more leaf-neighbors, then $γ_{\rm gr}^t(T) \ge \frac{2}{3}(n+1)$ , and characterize the extremal trees. We also prove that for $k \ge 3$ , if $G$ is a connected $k$ -regular graph of order~ $n$ different from $K_{k,k}$ , then $γ_{\rm gr}^t(G) \ge (n + \lceil \frac{k}{2} \rceil - 2)/(k-1)$ if $G$ is not bipartite and $γ_{\rm gr}^t(G) \ge (n + 2\lceil \frac{k}{2} \rceil - 4)/(k-1)$ if $G$ is bipartite. The Grundy total domination number is proven to be bounded from above by two times the Grundy domination number, while the former invariant can be arbitrarily smaller than the latter. Finally, a natural connection with edge covering sequences in hypergraphs is established, which in particular yields the NP-completeness of the decision version of the Grundy total domination number.

preprint2016arXiv

Trees with Equal Total Domination and Game Total Domination Numbers

In this paper, we continue the study of the total domination game in graphs introduced in [Graphs Combin. 31(5) (2015), 1453--1462], where the players Dominator and Staller alternately select vertices of $G$ . Each vertex chosen must strictly increase the number of vertices totally dominated, where a vertex totally dominates another vertex if they are neighbors. This process eventually produces a total dominating set $S$ of $G$ in which every vertex is totally dominated by a vertex in $S$ . Dominator wishes to minimize the number of vertices chosen, while Staller wishes to maximize it. The game total domination number, $γ_{\rm tg}(G)$ , (respectively, Staller-start game total domination number, $γ_{\rm tg}'(G)$ ) of $G$ is the number of vertices chosen when Dominator (respectively, Staller) starts the game and both players play optimally. For general graphs $G$ , sometimes $γ_{\rm tg}(G) > γ_{\rm tg}'(G)$ . We show that if $G$ is a forest with no isolated vertex, then $γ_{\rm tg}(G) \le γ_{\rm tg}'(G)$ . Using this result, we characterize the trees with equal total domination and game total domination number.

preprint2015arXiv

Progress Towards the Total Domination Game $\frac{3}{4}$ -Conjecture

In this paper, we continue the study of the total domination game in graphs introduced in [Graphs Combin. 31(5) (2015), 1453--1462], where the players Dominator and Staller alternately select vertices of $G$ . Each vertex chosen must strictly increase the number of vertices totally dominated, where a vertex totally dominates another vertex if they are neighbors. This process eventually produces a total dominating set $S$ of $G$ in which every vertex is totally dominated by a vertex in $S$ . Dominator wishes to minimize the number of vertices chosen, while Staller wishes to maximize it. The game total domination number, $γ_{\rm tg}(G)$ , of $G$ is the number of vertices chosen when Dominator starts the game and both players play optimally. Henning, Klavžar and Rall [Combinatorica, to appear] posted the $\frac{3}{4}$ -Game Total Domination Conjecture that states that if $G$ is a graph on $n$ vertices in which every component contains at least three vertices, then $γ_{\rm tg}(G) \le \frac{3}{4}n$ . In this paper, we prove this conjecture over the class of graphs $G$ that satisfy both the condition that the degree sum of adjacent vertices in $G$ is at least $4$ and the condition that no two vertices of degree $1$ are at distance $4$ apart in $G$ . In particular, we prove that by adopting a greedy strategy, Dominator can complete the total domination game played in a graph with minimum degree at least $2$ in at most $3n/4$ moves.

preprint2013arXiv

Domination game played on trees and spanning subgraphs

The domination game is played on a graph G. Vertices are chosen, one at a time, by two players Dominator and Staller. Each chosen vertex must enlarge the set of vertices of G dominated to that point in the game. Both players use an optimal strategy---Dominator plays so as to end the game as quickly as possible while Staller plays in such a way that the game lasts as many steps as possible. The game domination number of G is the number of vertices chosen when Dominator starts the game and the Staller-start game domination number of G when Staller starts the game. In this paper these two games are studied when played on trees and spanning subgraphs. A lower bound for the game domination number of a tree in terms of the order and maximum degree is proved and shown to be asymptotically tight. It is shown that for every k, there is a tree T with game domination number k and Staller-start game domination number k+1, and it is conjectured that there is no tree with game domination number k and Staller-start game domination number k-1. A relation between the game domination number of a graph and its spanning subgraphs is considered. It is proved that for any positive integer n, there exists a graph G and its spanning tree T such that the game domination number of G is at least n more than the game domination number of T. Moreover, there exist 3-connected graphs G having a spanning subgraph such that the game domination number of the spanning subgraph is arbitrarily smaller than that of G.

preprint2013arXiv

Rainbow domination in the lexicographic product of graphs

Let k be a positive integer and let f be a map from V(G) to the set of all subsets of {1,2,3,...,k}. The function f is called a k-rainbow dominating function of G provided that whenever u is a vertex of G such that f(u) is the empty set, then for each integer r in {1,2,3,...,k} there is a neighbor x of u such that f(x) contains r. The k-rainbow domination number of G is the minimum sum (over all the vertices of G) of the cardinalities of the subsets assigned by a k-rainbow dominating function of G. The k-rainbow domination number of G is the ordinary domination number of the Cartesian product of G and a complete graph of order k. We focus on the 2-rainbow domination number of the lexicographic product of graphs and prove sharp lower and upper bounds for this number. In fact, we prove the exact value of the 2-rainbow domination number of the lexicographic product of G with H in terms of domination invariants of G, except for the case when H has 2-rainbow domination number 3 and there is a minimum 2-rainbow dominating function of H such that some vertex in H is assigned the label {1,2}.

preprint2012arXiv

Identifying codes of the direct product of two cliques

An identifying code in a graph is a dominating set that also has the property that the closed neighborhood of each vertex in the graph has a distinct intersection with the set. It was recently shown by Gravier, Moncel and Semri that the minimum cardinality of an identifying code for the Cartesian product of two cliques of the same order n is the floor of 3n/2. We consider identifying codes of the direct product of two cliques. In particular, we answer a question of Klavzar and determine the minimum cardinality of an identifying code for the direct product of any two cliques.

preprint2012arXiv

On the Cartesian product of non well-covered graphs

A graph is well-covered if every maximal independent set has the same cardinality, namely the vertex independence number. We answer a question of Topp and Volkmann and prove that if the Cartesian product of two graphs is well-covered, then at least one of them must be well-covered.

preprint2011arXiv

On graphs having maximal independent sets of exactly $t$ distinct cardinalities

For a given positive integer t we consider graphs having maximal independent sets of precisely t distinct cardinalities and restrict our attention to those that have no vertices of degree one. In the situation when t is four or larger and the length of the shortest cycle is at least 6t-6, we completely characterize such graphs.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Douglas F. Rall

Research overview

Is this your work?

17 publications

Total isolation game in graphs

On independent domination in direct products

Domination in digraphs and their products

General $d$ -position sets

On graphs having one size of maximal open packings

The Enclaveless Competition Game

On minimum identifying codes in some Cartesian product graphs

Packing chromatic number under local changes in a graph

Packing chromatic number, $(1,1,2,2)$ -colorings, and characterizing the Petersen graph

Total Dominating Sequences in Graphs

Trees with Equal Total Domination and Game Total Domination Numbers

Progress Towards the Total Domination Game $\frac{3}{4}$ -Conjecture

Domination game played on trees and spanning subgraphs

Rainbow domination in the lexicographic product of graphs

Identifying codes of the direct product of two cliques

On the Cartesian product of non well-covered graphs

On graphs having maximal independent sets of exactly $t$ distinct cardinalities

See the researcher in context

Building this map preview

Douglas F. Rall

Research overview

Is this your work?

17 publications

Total isolation game in graphs

On independent domination in direct products

Domination in digraphs and their products

General ddd-position sets

On graphs having one size of maximal open packings

The Enclaveless Competition Game

On minimum identifying codes in some Cartesian product graphs

Packing chromatic number under local changes in a graph

Packing chromatic number, (1,1,2,2)(1,1,2,2)(1,1,2,2)-colorings, and characterizing the Petersen graph

Total Dominating Sequences in Graphs

Trees with Equal Total Domination and Game Total Domination Numbers

Progress Towards the Total Domination Game 34\frac{3}{4}43​-Conjecture

Domination game played on trees and spanning subgraphs

Rainbow domination in the lexicographic product of graphs

Identifying codes of the direct product of two cliques

On the Cartesian product of non well-covered graphs

On graphs having maximal independent sets of exactly ttt distinct cardinalities

See the researcher in context

Building this map preview

General $d$ -position sets

Packing chromatic number, $(1,1,2,2)$ -colorings, and characterizing the Petersen graph

Progress Towards the Total Domination Game $\frac{3}{4}$ -Conjecture

On graphs having maximal independent sets of exactly $t$ distinct cardinalities