Strongly Closed Subgraphs in a Distance-Regular Graph with <Emphasis Type="Italic">c</Emphasis><Subscript>2</Subscript> > 1

Let Γ be a distance-regular graph of diameter d ≥ 3 with c ₂ > 1. Let m be an integer with 1 ≤ m ≤ d − 1. We consider the following conditions:

Measurable Sets With Excluded Distances

For a set of distances D = {d ₁,..., d _k } a set A is called D-avoiding if no pair of points of A is at distance d _i for some i. We show that the density of A is exponentially small in k provided the ratios d ₁/d ₂, d ₂/d ₃, …, d _k-1/d _k are all small enough. This resolves a question of Székely, and generalizes a theorem of Furstenberg–Katznelson–Weiss, Falconer–Marstrand, and Bourgain. Several more results on D-avoiding sets are presented. Received: January 2007, Revision: February 2008, Accepted: February 2008     

Sampling in Paley-Wiener spaces on combinatorial graphs

A notion of Paley-Wiener spaces on combinatorial graphs is introduced. It is shown that functions from some of these spaces are uniquely determined by their values on some sets of vertices which are called the uniqueness sets. Such uniqueness sets are described in terms of Poincare-Wirtinger-type inequalities. A reconstruction algorithm of Paley-Wiener functions from uniqueness sets which uses the idea of frames in Hilbert spaces is developed. Special consideration is given to the -dimensional lattice, homogeneous trees, and eigenvalue and eigenfunction problems on finite graphs.

     

Links and cubic 3-polytopes

It is well known that a prime link diagram corresponds to a signed plane graph without cut vertices (Kauffman, 1989). In this paper, we present a new relation between prime links and cubic 3-polytopes. Let be the set of links such that each has a diagram whose corresponding signed plane graph is the graph of a cubic 3-polytope. We show that all nontrivial prime links, except -torus links and -pretzel links, can be obtained from by using some operation of untwining. Furthermore, we define the generalized cubic 3-polytope chains and then show that any nontrivial link can be obtained from by some untwining operations, where is the set of links corresponding to generalized cubic 3-polytope chains. These results are used to simplify the computation of the Kauffman brackets of links so that the computing can be done in a unified way for many infinite families of links.

     

On stable cutsets in claw-free graphs and planar graphs

A stable cutset in a connected graph is a stable set whose deletion disconnects the graph. Let $K_4$ and $K_{1,3}$ (claw) denote the complete (bipartite) graph on 4 and $1+3$ vertices. It is NP-complete to decide whether a line graph (hence a claw-free graph) with maximum degree five or a $K_4$-free graph admits a stable cutset. Here we describe algorithms deciding in polynomial time whether a claw-free graph with maximum degree at most four or whether a (claw, $K_4$)-free graph admits a stable cutset. As a by-product we obtain that the stable cutset problem is polynomially solvable for claw-free planar graphs, and also for planar line graphs.Thus, the computational complexity of the stable cutset problem is completely determined for claw-free graphs with respect to degree constraint, and for claw-free planar graphs. Moreover, we prove that the stable cutset problem remains NP-complete for $K_4$-free planar graphs with maximum degree five.     

Structural and electronic effects involving pyridine rings in 4-methylpyridine Cu4OX6L4 complexes. II. Correlations based on molecular structure of the Cu4OCl6(4-Mepy)4 complex

Correlations involving bond lengths and bond angles in the molecular structure of the Cu₄OCl₆(4-Mepy)₄ complex (4-Mepy = 4-methylpyridine) with four symmetrically independent molecules present in the unit cell showed that the donor-acceptor behavior involving the π-back donation into the pyridine rings of the 4-Mepy ligands is most effectively stimulated by a suitable orientation of the pyridine rings in the trigonal bipyramidal geometry. The pyridine ring planes are almost in parallel orientation with one of the three Cu-Cl bonds. The bond lengths of these Cu-Cl bonds are in a significant linear correlation with the Cu-N bond lengths and the bonds lengths of the pyridine rings. The pyridine rings orientation is affected by distortion of the trigonal bipyramidal geometry to tetragonal pyramidal coordination, by out-of plane pyridine rings deviation and in-plane pyridine rings tilting, by puckering of the pyridine rings and by the effects of the methyl groups. The pyridine rings in at least seven of the sixteen trigonal bipyramidal coordinations exhibit an orientation supporting the π-back bonding between the Cu(II) atoms and the pyridine rings.     

An Enumeration of Certain Projective Ternary Two‐Weight Codes

We detail the enumeration of all two‐intersection sets of the five‐dimensional projective space over the field of order 3 that are invariant under an element of order 7, which include the examples of Hill (1973) and Gulliver (1996). Up to projective equivalence, there are 6,635 such two‐intersection sets.     

Asynchronous cellular automata and pattern classification

This article designs an efficient two‐class pattern classifier utilizing asynchronous cellular automata (ACAs). The two‐state three‐neighborhood one‐dimensional ACAs that converge to fixed points from arbitrary seeds are used here for pattern classification. To design the classifier, (1) we first identify a set of ACAs that always converge to fixed points from any seeds, (2) each ACA should have at least two but not huge number of fixed point attractors, and (3) the convergence time of these ACAs are not to be exponential. To address the second issue, we propose a graph, coined as fixed point graph of an ACA that facilitates in counting the fixed points. We further perform an experimental study to estimate the convergence time of ACAs, and find there are some convergent ACAs which demand exponential convergence time. Finally, we identify there are 73 (out of 256) ACAs which can be effective candidates as pattern classifier. We use each of the candidate ACAs on some standard datasets, and observe the effectiveness of each ACAs as pattern classifier. It is observed that the proposed classifier is very competitive and performs reliably better than many standard existing classifier algorithms. © 2016 Wiley Periodicals, Inc. Complexity 21: 370–386, 2016     

Excluded Minors and the Ribbon Graphs of Knots

In this article we consider minors of ribbon graphs (or, equivalently, cellularly embedded graphs). The theory of minors of ribbon graphs differs from that of graphs in that contracting loops is necessary and doing this can create additional vertices and components. Thus, the ribbon graph minor relation is incompatible with the graph minor relation. We discuss excluded minor characterizations of minor closed families of ribbon graphs. Our main result is an excluded minor characterization of the family of ribbon graphs that represent knot and link diagrams.