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
The dominating graph of a graph H has as its vertices all dominating sets of H, with an edge between two dominating sets if one can be obtained from the other by the addition or deletion of a single vertex of H. In this paper we prove that the dominating graph of any tree has a Hamilton path. We also show how a result about binary strings leads to a proof that the dominating graph of a cycle on n vertices has a Hamilton path if and only if n≡0(mod4).
An X-TAR (token addition/removal) reconfiguration graph has as its vertices sets that satisfy some property X, with an edge between two sets if one is obtained from the other by adding or removing one element. This paper considers the X-TAR graph for X− sets of vertices of a base graph G where the X-sets of G must satisfy certain conditions. Dominating sets, power dominating sets, zero forcing sets, and positive semidefinite zero forcing sets are all examples of X-sets. For graphs G and G′ with no isolated vertices, it is shown that G and G′ have isomorphic X-TAR reconfiguration graphs if and only if there is a relabeling of the vertices of G′ such that G and G′ have exactly the same X-sets. The concept of an X-irrelevant vertex is introduced to facilitate analysis of X-TAR graph isomorphisms. Furthermore, results related to the connectedness of the zero forcing TAR graph are given. We present families of graphs that exceed known lower bounds for connectedness parameters.
This paper begins the study of reconfiguration of zero forcing sets, and more specifically, the zero forcing graph. Given a base graph G, its zero forcing graph, Z(G), is the graph whose vertices are the minimum zero forcing sets of G with an edge between vertices B and B′ of Z(G) if and only if B can be obtained from B′ by changing a single vertex of G. It is shown that the zero forcing graph of a forest is connected, but that many zero forcing graphs are disconnected. We characterize the base graphs whose zero forcing graphs are either a path or the complete graph, and show that the star cannot be a zero forcing graph. We show that computing Z(G) takes 2Θ(n) operations in the worst case for a graph G of order n.
This paper presents infinitely many new examples of triangle-free uniquely 3-edge colorable cubic graphs. The only such graph previously known was given by Tutte in 1976.
Given a graph G, the k-dominating graph of G, Dk(G), is defined to be the graph whose vertices correspond to the dominating sets of G that have cardinality at most k. Two vertices in Dk(G) are adjacent if and only if the corresponding dominating sets of G differ by either adding or deleting a single vertex. The graph Dk(G) aids in studying the reconfiguration problem for dominating sets. In particular, one dominating set can be reconfigured to another by a sequence of single vertex additions and deletions, such that the intermediate set of vertices at each step is a dominating set if and only if they are in the same connected component of Dk(G). In this paper we give conditions that ensure Dk(G) is connected.
Two edge colorings of a graph are {\em edge-Kempe equivalent} if one can be obtained from the other by a series of edge-Kempe switches. This work gives some results for the number of edge-Kempe equivalence classes for cubic graphs. In particular we show every 2-connected planar bipartite cubic graph has exactly one edge-Kempe equivalence class. Additionally, we exhibit infinite families of nonplanar bipartite cubic graphs with a range of numbers of edge-Kempe equivalence classes. Techniques are developed that will be useful for analyzing other classes of graphs as well.
A {\bf map} is a graph that admits an orientation of its edges so that each vertex has out-degree exactly 1. We characterize graphs which admit a decomposition into k edge-disjoint maps after: (1) the addition of {\it any} ℓ edges; (2) the addition of {\it some} ℓ edges. These graphs are identified with classes of {\it sparse} graphs; the results are also given in matroidal terms.
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.