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
A λKv is a complete graph on v vertices with λ edges between each pair of the v vertices. A (λ+μ)Kv+u−λKv is a (λ+μ)Kv+u with the edge set of λKv removed. Decomposing a (λ+μ)Kv+u−λKv into edge-disjoint m-cycles has been studied by many people. To date, there is a complete solution for m=4 and partial results when m=3 or m=5. In this paper, we are able to solve this problem for all even cycle lengths as long as u,v≥m+2.
In a graph G, let μG(xy) denote the number of edges between x and y in G. Let λKv,u be the graph (V∪U,E) with ∣V∣=v, ∣U∣=u, and \[ μ_G(xy)=\begin{cases} λ&\mbox{if $x\in U$ and $y\in V$ or if $x\in V$ and $y\in U$}\\ 0 &\mbox{otherwise.} \\ \end{cases} \] Let M be a sequence of non-negative integers m1,m2,…,mn. An (M)-cycle decomposition of a graph G is a partition of the edge set into cycles of lengths m1,m2,…,mn. In this paper, we establish necessary and sufficient conditions for the existence of an (M)-cycle decomposition of λKv,u.
The graph of overlapping permutations is a directed graph that is an analogue to the De Bruijn graph. It consists of vertices that are permutations of length n and edges that are permutations of length n+1 in which an edge a1⋯an+1 would connect the standardization of a1⋯an to the standardization of a2⋯an+1. We examine properties of this graph to determine where directed cycles can exist, to count the number of directed 2-cycles within the graph, and to enumerate the vertices that are contained within closed walks and directed cycles of more general lengths.
The main technique used to edge-colour graphs requiring Δ+2 or more colours is the method of Tashkinov trees. We present a specific limit to this method, in terms of Kempe changes. We also provide a new Tashkinov tree extension.
Following standard terminology, λKv is a multigraph on v vertices such that λ edges join each pair of vertices. Let (λ+μ)Kv+u−λKv be the graph (V∪U,E) with ∣V∣=v, ∣U∣=u, and (λ+μ)−λ=μ edges between the vertices x and y if x and y both lie in V and λ+μ edges between x and y otherwise. The main result of this paper establishes necessary and sufficient conditions for an m-path decomposition of (λ+μ)Kv+u−λKv.
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 subk(G). We show that subk(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 subk(G)-critical with respect to addition and deletion of vertices and edges.
The Hamilton-Waterloo Problem (HWP) in the case of Cm-factors and Cn-factors asks if Kv, where v is odd (or Kv−F, where F is a 1-factor and v is even), can be decomposed into r copies of a 2-factor made either entirely of m-cycles and s copies of a 2-factor made entirely of n-cycles. In this paper, we give some general constructions for such decompositions and apply them to the case where m=3 and n=3x. We settle the problem for odd v, except for a finite number of x values. When v is even, we make significant progress on the problem, although open cases are left. In particular, the difficult case of v even and s=1 is left open for many situations.
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.