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
For each nonnegative integer i, let ai be the number of i-subsets of V(G) that induce an acyclic subgraph of a given graph G. We define A(G,x)=∑i≥0aixi (the generating function for ai) to be the acyclic polynomial for G. After presenting some properties of these polynomials, we investigate the nature and location of their roots.
An ℓ-cycle system F of a graph Γ is a set of ℓ-cycles which partition the edge set of Γ. Two such cycle systems F and F′ are said to be {\em orthogonal} if no two distinct cycles from F∪F′ share more than one edge. Orthogonal cycle systems naturally arise from face 2-colourable polyehdra and in higher genus from Heffter arrays with certain orderings. A set of pairwise orthogonal ℓ-cycle systems of Γ is said to be a set of mutually orthogonal cycle systems of Γ. Let μ(ℓ,n) (respectively, μ′(ℓ,n)) be the maximum integer μ such that there exists a set of μ mutually orthogonal (cyclic) ℓ-cycle systems of the complete graph Kn. We show that if ℓ≥4 is even and n≡1(mod2ℓ), then μ′(ℓ,n), and hence μ(ℓ,n), is bounded below by a constant multiple of n/ℓ2. In contrast, we obtain the following upper bounds: μ(ℓ,n)≤n−2; μ(ℓ,n)≤(n−2)(n−3)/(2(ℓ−3)) when ℓ≥4; μ(ℓ,n)≤1 when ℓ>n/2; and μ′(ℓ,n)≤n−3 when n≥4. We also obtain computational results for small values of n and ℓ.
Suppose we have a network that is represented by a graph G. Potentially a fire (or other type of contagion) might erupt at some vertex of G. We are able to respond to this outbreak by establishing a firebreak at k other vertices of G, so that the fire cannot pass through these fortified vertices. The question that now arises is which k vertices will result in the greatest number of vertices being saved from the fire, assuming that the fire will spread to every vertex that is not fully behind the k vertices of the firebreak. This is the essence of the {\sc Firebreak} decision problem, which is the focus of this paper. We establish that the problem is intractable on the class of split graphs as well as on the class of bipartite graphs, but can be solved in linear time when restricted to graphs having constant-bounded treewidth, or in polynomial time when restricted to intersection graphs. We also consider some closely related problems.
Given a combinatorial design D with block set B, the block-intersection graph (BIG) of D is the graph that has B as its vertex set, where two vertices B1∈B and B2∈B are adjacent if and only if ∣B1∩B2∣>0. The i-block-intersection graph (i-BIG) of D is the graph that has B as its vertex set, where two vertices B1∈B and B2∈B are adjacent if and only if ∣B1∩B2∣=i. In this paper several constructions are obtained that start with twofold triple systems (TTSs) with Hamiltonian 2-BIGs and result in larger TTSs that also have Hamiltonian 2-BIGs. These constructions collectively enable us to determine the complete spectrum of TTSs with Hamiltonian 2-BIGs (equivalently TTSs with cyclic 2-intersecting Gray codes) as well as the complete spectrum for TTSs with 2-BIGs that have Hamilton paths (i.e., for TTSs with 2-intersecting Gray codes). In order to prove these spectrum results, we sometimes require ingredient TTSs that have large partial parallel classes; we prove lower bounds on the sizes of partial parallel clasess in arbitrary TTSs, and then construct larger TTSs with both cyclic 2-intersecting Gray codes and parallel classes.
A weak c-colouring of a balanced incomplete block design (BIBD) is a colouring of the points of the design with c colours in such a way that no block of the design has all of its vertices receive the same colour. A BIBD is said to be weakly c-chromatic if c is the smallest number of colours with which the design can be weakly coloured. In this paper we show that for all c≥2 and k≥3 with (c,k)=(2,3), the obvious necessary conditions for the existence of a (v,k,λ)-BIBD are asymptotically sufficient for the existence of a weakly c-chromatic (v,k,λ)-BIBD.
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.