Source author record

Randy Davila

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

9works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Computer assisted discovery: Zero forcing vs vertex cover

In this paper, we showcase the process of using an automated conjecturing program called \emph{TxGraffiti} written and maintained by the second author. We begin by proving a conjecture formulated by \emph{TxGraffiti} that for a claw-free graph $G$ , the vertex cover number $β(G)$ is greater than or equal to the zero forcing number $Z(G)$ . Our proof of this result is constructive, and yields a polynomial time algorithm to find a zero forcing set with cardinality $β(G)$ . We also use the output of \emph{TxGraffiti} to construct several infinite families of claw-free graphs for which $Z(G)=β(G)$ . Additionally, inspired by the aforementioned conjecture of \emph{TxGraffiti}, we also prove a more general relation between the zero forcing number and the vertex cover number for any connected graph with maximum degree $Δ\ge 3$ , namely that $Z(G)\leq (Δ-2)β(G)$ +1.

preprint2020arXiv

On a Vizing-type integer domination conjecture

Given a simple graph $G$ , a dominating set in $G$ is a set of vertices $S$ such that every vertex not in $S$ has a neighbor in $S$ . Denote the domination number, which is the size of any minimum dominating set of $G$ , by $γ(G)$ . For any integer $k\ge 1$ , a function $f : V (G) \rightarrow \{0, 1, . . ., k\}$ is called a \emph{ $\{k\}$ -dominating function} if the sum of its function values over any closed neighborhood is at least $k$ . The weight of a $\{k\}$ -dominating function is the sum of its values over all the vertices. The $\{k\}$ -domination number of $G$ , $γ_{\{k\}}(G)$ , is defined to be the minimum weight taken over all $\{k\}$ -domination functions. Brešar, Henning, and Klavžar (On integer domination in graphs and Vizing-like problems. \emph{Taiwanese J. Math.} {10(5)} (2006) pp. 1317--1328) asked whether there exists an integer $k\ge 2$ so that $γ_{\{k\}}(G\square H)\ge γ(G)γ(H)$ . In this note we use the Roman $\{2\}$ -domination number, $γ_{R2}$ of Chellali, Haynes, Hedetniemi, and McRae, (Roman $\{2\}$ -domination. \emph{Discrete Applied Mathematics} {204} (2016) pp. 22-28.) to prove that if $G$ is a claw-free graph and $H$ is an arbitrary graph, then $γ_{\{2\}}(G\square H)\ge γ_{R2}(G\square H)\ge γ(G)γ(H)$ , which also implies the conjecture for all $k\ge 2$ .

preprint2016arXiv

Bounds on the connected forcing number of a graph

In this paper, we study (zero) forcing sets which induce connected subgraphs of a graph. The minimum cardinality of such a set is called the connected forcing number of the graph. We provide sharp upper and lower bounds on the connected forcing number in terms of the minimum degree, maximum degree, girth, and order of the graph.

preprint2016arXiv

Characterizations of the Connected Forcing Number of a Graph

Zero forcing is a dynamic graph coloring process whereby a colored vertex with a single uncolored neighbor forces that neighbor to be colored. This forcing process has been used to approximate certain linear algebraic parameters, as well as to model the spread of diseases and information in social networks. In this paper, we introduce and study the connected forcing process -- a restriction of zero forcing in which the initially colored set of vertices induces a connected subgraph. We show that the connected forcing number -- the cardinality of the smallest initially colored vertex set which forces the entire graph to be colored -- is a sharp upper bound to the maximum nullity, path cover number, and leaf number of the graph. We also give closed formulas and bounds for the connected forcing numbers of several families of graphs including trees, hypercubes, and flower snarks, and characterize graphs with extremal connected forcing numbers.

preprint2016arXiv

The forcing number of graphs with a given girth

In this paper, we study a dynamic coloring of the vertices of a graph $G$ that starts with an initial subset $S$ of colored vertices, with all remaining vertices being non-colored. At each discrete time interval, a colored vertex with exactly one non-colored neighbor forces this non-colored neighbor to be colored. The initial set $S$ is called a forcing set of $G$ if, by iteratively applying the forcing process, every vertex in $G$ becomes colored. The forcing number, originally known as the \emph{zero forcing number}, and denoted $F(G)$ , of $G$ is the cardinality of a smallest forcing set of $G$ . We study lower bounds on the forcing number in terms of its minimum degree and girth, where the girth $g$ of a graph is the length of a shortest cycle in the graph. Let $G$ be a graph with minimum degree $δ\ge 2$ and girth~ $g \ge 3$ . Davila and Kenter [Theory and Applications of Graphs, Volume 2, Issue 2, Article 1, 2015] conjecture that $F(G) \ge δ+ (δ-2)(g-3)$ . This conjecture has recently been proven for $g \le 6$ . The conjecture is also proven when the girth $g \ge 7$ and the minimum degree is sufficiently large. In particular, it holds when $g = 7$ and $δ\ge 481$ , when $g = 8$ and $δ\ge 649$ , when $g = 9$ and $δ\ge 30$ , and when $g = 10$ and $δ\ge 34$ . In this paper, we prove the conjecture for $g \in \{7,8,9,10\}$ and for all values of $δ\ge 2$ .

preprint2016arXiv

The sub- $k$ -domination number of a graph with applications to $k$ -domination

In this paper we introduce and study a new graph invariant derived from the degree sequence of a graph $G$ , called the sub- $k$ -domination number and denoted $sub_k(G)$ . We show that $sub_k(G)$ is a computationally efficient sharp lower bound on the $k$ -domination number of $G$ , and improves on several known lower bounds. We also characterize the sub- $k$ -domination numbers of several families of graphs, provide structural results on sub- $k$ -domination, and explore properties of graphs which are $sub_k(G)$ -critical with respect to addition and deletion of vertices and edges.

preprint2015arXiv

Lower Bounds on the Distance Domination Number of a Graph

For an integer $k \ge 1$ , a (distance) $k$ -dominating set of a connected graph $G$ is a set $S$ of vertices of $G$ such that every vertex of $V(G) \setminus S$ is at distance at most~ $k$ from some vertex of $S$ . The $k$ -domination number, $γ_k(G)$ , of $G$ is the minimum cardinality of a $k$ -dominating set of $G$ . In this paper, we establish lower bounds on the $k$ -domination number of a graph in terms of its diameter, radius and girth. We prove that for connected graphs $G$ and $H$ , $γ_k(G \times H) \ge γ_k(G) + γ_k(H) -1$ , where $G \times H$ denotes the direct product of $G$ and $H$ .

preprint2014arXiv

Bounds for the Zero-Forcing Number of Graphs with Large Girth

We investigate the zero-forcing number for triangle-free graphs. We improve upon the trivial bound, $δ\le Z(G)$ where $δ$ is the minimum degree, in the triangle-free case. In particular, we show that $2 δ- 2 \le Z(G)$ for graphs with girth of at least 5, and this can be further improved when $G$ has a small cut set. Using these results, we are able to prove the Graph Complement Conjecture on minimum rank for a large class of graphs. Lastly, we make a conjecture that the lower bound for $Z(G)$ increases as a function of the girth, $g$ , and $δ$ .

preprint2014arXiv

Upper bounds on the k-forcing number of a graph

Given a simple undirected graph $G$ and a positive integer $k$ , the $k$ -forcing number of $G$ , denoted $F_k(G)$ , is the minimum number of vertices that need to be initially colored so that all vertices eventually become colored during the discrete dynamical process described by the following rule. Starting from an initial set of colored vertices and stopping when all vertices are colored: if a colored vertex has at most $k$ non-colored neighbors, then each of its non-colored neighbors becomes colored. When $k=1$ , this is equivalent to the zero forcing number, usually denoted with $Z(G)$ , a recently introduced invariant that gives an upper bound on the maximum nullity of a graph. In this paper, we give several upper bounds on the $k$ -forcing number. Notable among these, we show that if $G$ is a graph with order $n \ge 2$ and maximum degree $Δ\ge k$ , then $F_k(G) \le \frac{(Δ-k+1)n}{Δ- k + 1 +\min{\{δ,k\}}}$ . This simplifies to, for the zero forcing number case of $k=1$ , $Z(G)=F_1(G) \le \frac{Δn}{Δ+1}$ . Moreover, when $Δ\ge 2$ and the graph is $k$ -connected, we prove that $F_k(G) \leq \frac{(Δ-2)n+2}{Δ+k-2}$ , which is an improvement when $k\leq 2$ , and specializes to, for the zero forcing number case, $Z(G)= F_1(G) \le \frac{(Δ-2)n+2}{Δ-1}$ . These results resolve a problem posed by Meyer about regular bipartite circulant graphs. Finally, we present a relationship between the $k$ -forcing number and the connected $k$ -domination number. As a corollary, we find that the sum of the zero forcing number and connected domination number is at most the order for connected 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.

Randy Davila

Research overview

Is this your work?

9 publications

Computer assisted discovery: Zero forcing vs vertex cover

On a Vizing-type integer domination conjecture

Bounds on the connected forcing number of a graph

Characterizations of the Connected Forcing Number of a Graph

The forcing number of graphs with a given girth

The sub- $k$ -domination number of a graph with applications to $k$ -domination

Lower Bounds on the Distance Domination Number of a Graph

Bounds for the Zero-Forcing Number of Graphs with Large Girth

Upper bounds on the k-forcing number of a graph

See the researcher in context

Building this map preview

Randy Davila

Research overview

Is this your work?

9 publications

Computer assisted discovery: Zero forcing vs vertex cover

On a Vizing-type integer domination conjecture

Bounds on the connected forcing number of a graph

Characterizations of the Connected Forcing Number of a Graph

The forcing number of graphs with a given girth

The sub-kkk-domination number of a graph with applications to kkk-domination

Lower Bounds on the Distance Domination Number of a Graph

Bounds for the Zero-Forcing Number of Graphs with Large Girth

Upper bounds on the k-forcing number of a graph

See the researcher in context

Building this map preview

The sub- $k$ -domination number of a graph with applications to $k$ -domination