BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Michael Henning appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
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.
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.
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$.
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$.