BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
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.
The regular independence number, introduced by Albertson and Boutin in 1990, is the size of a largest set of independent vertices with the same degree. Lower bounds were proven for this invariant, in terms of the order, for trees and planar graphs. In this article, we generalize and extend these results to find lower bounds for the regular k-independence number for trees, forests, planar graphs, k-trees and k-degenerate graphs.
The k-forcing number of a graph is a generalization of the zero forcing number. In this note, we give a greedy algorithm to approximate the k-forcing number of a graph. Using this dynamic approach, we give corollaries which improve upon two theorems from a recent paper of Amos, Caro, Davila and Pepper [2], while also answering an open problem posed by Meyer [9].
Given a simple undirected graph G and a positive integer k, the k-forcing number of G, denoted Fk(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≥2 and maximum degree Δ≥k, then Fk(G)≤Δ−k+1+min{δ,k}(Δ−k+1)n. This simplifies to, for the zero forcing number case of k=1, Z(G)=F1(G)≤Δ+1Δn. Moreover, when Δ≥2 and the graph is k-connected, we prove that Fk(G)≤Δ+k−2(Δ−2)n+2, which is an improvement when k≤2, and specializes to, for the zero forcing number case, Z(G)=F1(G)≤Δ−1(Δ−2)n+2. 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.
We introduce a procedure, called the Degree Sequence Index Strategy (DSI), by which to bound graph invariants by certain indices in the ordered degree sequence. As an illustration of the DSI strategy, we show how it can be used to give new upper and lower bounds on the k-independence and the k-domination numbers. These include, among other things, a double generalization of the annihilation number, a recently introduced upper bound on the independence number. Next, we use the DSI strategy in conjunction with planarity, to generalize some results of Caro and Roddity about independence number in planar graphs. Lastly, for claw-free and K1,r-free graphs, we use DSI to generalize some results of Faudree, Gould, Jacobson, Lesniak and Lindquester.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.