Metal π-complexes of cyclooctatetraenes: I. Reinvestigation of the crystal structure of the 1:1 adduct of cyclooctatetraene and silver nitrate

Redetermination of the crystal structure of C₈H₈ · AgNO₃ from new Mo-K_α diffractometer data has rectified all the unsatisfactory aspects of the previous study. The structure consists of strongly-bonded Ag¹-C₈H₈ units linked by weaker metal-ligand interactions to form infinite chains parallel to the c axis; neighboring chains are cross-linked by bridging nitrate groups to form corrugated sheets normal to the a axis. Crystals are monoclinic, space group P2₁/a, with a = 16.796(3), b = 8.932(2), c = 5.860(1) Å, β = 90.72(1)°, and Z = 4. The structure was refined to a conventional R value of 0.039 for 1382 unique observed data.     

Numerical analysis for factorial data analysis. Part I: Numerical software — the package INDA for microcomputers

A large collection of factorial data analysis methods can be characterized by the following matrices: X , the k x n matrix of data, and A, B the symmetric positive definite matrices of size n, k which represent the chosen norms of ?ⁿ, ?^k, respectively. All methods amount to computing the largest eigenvalues of U = XAX^TB or the largest singular values of E = B^1/2XA^1/2 . In Part I of this paper we begin by a geometrical and probabilistic interpretation of the various methods, showing how U and E are defined in each case. We then define the computational kernel for factorial data analysis. We conclude by devising the numerical aspects of software implementation for this kernel on microcomputers and presenting the package INDA.     

Parity vertex colouring of plane graphs

A proper vertex colouring of a 2-connected plane graph G is a parity vertex colouring if for each face f and each colour c, either no vertex or an odd number of vertices incident with f is coloured with c. The minimum number of colours used in such a colouring of G is denoted by χ_p(G).In this paper, we prove that χ_p(G)≤118 for every 2-connected plane graph G.     

Parity vertex coloring of outerplane graphs

A proper vertex coloring of a 2-connected plane graph G is a parity vertex coloring if for each face f and each color c, the total number of vertices of color c incident with f is odd or zero. The minimum number of colors used in such a coloring of G is denoted by χ_p(G).In this paper we prove that χ_p(G)≤12 for every 2-connected outerplane graph G. We show that there is a 2-connected outerplane graph G such that χ_p(G)=10. If a 2-connected outerplane graph G is bipartite, then χ_p(G)≤8, moreover, this bound is best possible.     

Ohba’s conjecture for graphs with independence number five

Ohba has conjectured that if G is a k-chromatic graph with at most 2k+1 vertices, then the list chromatic number or choosability of G is equal to its chromatic number χ(G), which is k. It is known that this holds if G has independence number at most three. It is proved here that it holds if G has independence number at most five. In particular, and equivalently, it holds if G is a complete k-partite graph and each part has at most five vertices.     

The most vital nodes with respect to independent set and vertex cover

Given an undirected graph with weights on its vertices, the k most vital nodes independent set (k most vital nodes vertex cover) problem consists of determining a set of k vertices whose removal results in the greatest decrease in the maximum weight of independent sets (minimum weight of vertex covers, respectively). We also consider the complementary problems, minimum node blocker independent set (minimum node blocker vertex cover) that consists of removing a subset of vertices of minimum size such that the maximum weight of independent sets (minimum weight of vertex covers, respectively) in the remaining graph is at most a specified value. We show that these problems are NP-hard on bipartite graphs but polynomial-time solvable on unweighted bipartite graphs. Furthermore, these problems are polynomial also on cographs and graphs of bounded treewidth. Results on the non-existence of ptas are presented, too.     

Vertex splitting and the recognition of trapezoid graphs

Trapezoid graphs are the intersection family of trapezoids where every trapezoid has a pair of opposite sides lying on two parallel lines. These graphs have received considerable attention and lie strictly between permutation graphs (where the trapezoids are lines) and cocomparability graphs (the complement has a transitive orientation). The operation of “vertex splitting”, introduced in (Cheah and Corneil, 1996) [3], first augments a given graph G and then transforms the augmented graph by replacing each of the original graph’s vertices by a pair of new vertices. This “splitted graph” is a permutation graph with special properties if and only if G is a trapezoid graph. Recently vertex splitting has been used to show that the recognition problems for both tolerance and bounded tolerance graphs is NP-complete (Mertzios et al., 2010) [11]. Unfortunately, the vertex splitting trapezoid graph recognition algorithm presented in (Cheah and Corneil, 1996) [3] is not correct. In this paper, we present a new way of augmenting the given graph and using vertex splitting such that the resulting algorithm is simpler and faster than the one reported in (Cheah and Corneil, 1996) [3].     

Circular vertex arboricity

The vertex arboricity va(G) of graph G is defined as the minimum of subsets in a partition of the vertex set of G so that each subset induces an acyclic subgraph and has been widely studied. We define the concept of circular vertex arboricity va_c(G) of graph G, which is a natural generalization of vertex arboricity. We give some basic properties of circular vertex arboricity and study the circular vertex arboricity of planar graphs.     

Random Sums of Independent Indicators and Generalized Reduced Processes

We consider a random sum of independent and identically distributed Bernoulli random variables. We prove several limit theorems for this sum under some natural assumptions. Using these limit theorems a generalized version of the reduced critical Galton-Watson process will be studied. In particular we find limit distributions for the number of individuals in a given generation the number of whose descendants after some generations exceeds a fixed or increasing level. An application to study of the number of “big” trees in a forest containing a random number of trees will also be discussed.