On the action of a group on a graph, II

This paper is a continuation of the survey by the author (V.I. Trofimov, On the action of a group on a graph, Acta Appl. Math. 29 (1992) 161–170) on some results concerning groups of automorphisms of locally finite vertex-symmetric graphs.     

Partial geometries pg (s, t, 2) with an abelian Singer group and a characterization of the van Lint-Schrijver partial geometry

Let be a proper partial geometry pg(s,t,2), and let G be an abelian group of automorphisms of acting regularly on the points of . Then either t≡2±od s+1 or is a pg(5,5,2) isomorphic to the partial geometry of van Lint and Schrijver (Combinatorica 1 (1981), 63–73). This result is a new step towards the classification of partial geometries with an abelian Singer group and further provides an interesting characterization of the geometry of van Lint and Schrijver.The author is Postdoctoral Fellow of the Fund for Scientific Research Flanders (FWO-Vlaanderen).     

On the sizes of graphs and their powers: The undirected case

Let G be an undirected graph and G^r be its r-th power. We study different issues dealing with the number of edges in G and G^r. In particular, we answer the following question: given an integer r≥2 and all connected graphs G of order n such that G^r≠K_n, what is the minimum number of edges that are added when going from G to G^r, and which are the graphs achieving this bound?     

Lower Bounds for the Eigenvalues of the Dirac Operator: Part II. The Submanifold Dirac Operator

In this paper we generalize the results of Part I to the submanifoldDirac operator. In particular, we give optimal lower bounds for thesubmanifold Dirac operator in terms of the mean curvature and othergeometric invariants as the Yamabe number or the energy-momentum tensor.In the limiting case, we prove that the submanifold is Einstein if thenormal bundle is flat.     

The Subconstituent Algebra of an Association Scheme (Part II)

This is a continuation of an article from the previous issue. In this section, we determine the structure of a thin, irreducible module for the subconstituent algebra of a P- and Q- polynomial association scheme. Such a module is naturally associated with a Leonard system. The isomorphism class of the module is determined by this Leonard system, which in turn is determined by four parameters: the endpoint, the dual endpoint, the diameter, and an additional parameter f. If the module has sufficiently large dimension, the parameter f takes one of a certain set of values indexed by a bounded integer parameter e.     

Claw-free graphs with strongly perfect complements. Fractional and integral version, Part II: Nontrivial strip-structures

Strongly perfect graphs have been studied by several authors (e.g., Berge and Duchet (1984) [1], Ravindra (1984) [7] and Wang (2006) [8]). In a series of two papers, the current paper being the second one, we investigate a fractional relaxation of strong perfection. Motivated by a wireless networking problem, we consider claw-free graphs that are fractionally strongly perfect in the complement. We obtain a forbidden induced subgraph characterization and display graph-theoretic properties of such graphs. It turns out that the forbidden induced subgraphs that characterize claw-free graphs that are fractionally strongly perfect in the complement are precisely the cycle of length 6, all cycles of length at least 8, four particular graphs, and a collection of graphs that are constructed by taking two graphs, each a copy of one of three particular graphs, and joining them in a certain way by a path of arbitrary length. Wang (2006) [8] gave a characterization of strongly perfect claw-free graphs. As a corollary of the results in this paper, we obtain a characterization of claw-free graphs whose complements are strongly perfect.     

Principal minors, Part II: The principal minor assignment problem

The inverse problem of finding a matrix with prescribed principal minors is considered. A condition that implies a constructive algorithm for solving this problem will always succeed is presented. The algorithm is based on reconstructing matrices from their principal submatrices and Schur complements in a recursive manner. Consequences regarding the overdeterminancy of this inverse problem are examined, leading to a faster (polynomial time) version of the algorithmic construction. Care is given in the MATLAB^® implementation of the algorithms regarding numerical stability and accuracy.     

The directed and Rubinov subdifferentials of quasidifferentiable functions, Part II: Calculus

We continue the study of the directed subdifferential for quasidifferentiable functions started in [R. Baier, E. Farkhi, V. Roshchina, The directed and Rubinov subdifferentials of quasidifferentiable functions, Part I: Definition and examples (this journal)]. Calculus rules for the directed subdifferentials of sum, product, quotient, maximum and minimum of quasidifferentiable functions are derived. The relation between the Rubinov subdifferential and the subdifferentials of Clarke, Dini, Michel-Penot, and Mordukhovich is discussed. Important properties implying the claims of Ioffe’s axioms as well as necessary and sufficient optimality conditions for the directed subdifferential are obtained.     

The correlations of finite Desarguesian planes, Part III: The classification (II)

This paper continues the classification of the correlations of planes of odd nonsquare order. Part I (Generalities) included introductory definitions and results (Section 1), algebraic preliminaries (Section 2), as well as a discussion of equivalent correlations (Section 3) and of their general properties (Section 4). The classification proper revolves around a special polynomial which can have one, two, or q + 1 zeros, or no zeros at all, and each of these four possibilities leads to different families of correlations. Part II contained Section 5, devoted to the cases in which the correlation is defined by a diagonal matrix (Subsection 5.1) or the polynomial in the preceding paragraph possesses q + 1 zeros (Subsection 5.2), one zero (Subsection 5.3) and two zeros (Subsection 5.4). Subsection 5.5 presented certain results to be used in the subsequent sections. The present article contains Section 6, devoted to the case in which the above-mentioned polynomial has no zeros.     

The correlations of finite Desarguesian planes, Part II: The classification (I)

This paper continues the classification of the correlations of planes of odd nonsquare order. Part I (Generalities) – see reference [1]-included introductory definitions and results (Section 1), algebraic preliminaries (Section 2), as well as a discussion of equivalent correlations (Section 3) and of their general properties (Section 4). The classification proper revolves around a special polynomial which can have one, two, or q + 1 zeros, or no zeros at all, and each of these four possibilities leads to different families of correlations. The present article contains Section 5, devoted to the cases in which the correlation is defined by a diagonal matrix (Subsection 5.1) or the polynomial in the preceding paragraph possesses q + 1 zeros (Subsection 5.2), one zero (Subsection 5.3) and two zeros (Subsection 5.4). Subsection 5.5 presents certain results to be used in the subsequent sections.     

Erratum: The average degree of an edge-chromatic critical graph II

In the article “The average degree of an edge-chromatic critical graph II” by Douglas R. Woodall (J. Graph Theory 56 (2007), 194-218), it was claimed that the average degree of an edge-chromatic critical graph with maximum degree $\mathrm{\Delta }$ is at least $\text{◂⋅▸}\frac{2}{3}\left(\mathrm{\Delta }+1\right)$ if $\mathrm{\Delta }⩾2$, at least $\text{◂+▸}\frac{2}{3}\mathrm{\Delta }+1$ if $\mathrm{\Delta }⩾8$, and at least $\text{◂⋅▸}\frac{2}{3}\left(\mathrm{\Delta }+2\right)$ if $\mathrm{\Delta }⩾15$. Unfortunately there were mistakes in the proof of the last two of these results, which are now proved only if $\mathrm{\Delta }⩾18$ and $\mathrm{\Delta }⩾30$, respectively.     

Lower Bounds for the Eigenvalues of the Dirac Operator: Part I. The Hypersurface Dirac Operator

We give optimal lower bounds for the hypersurface Diracoperator in terms of the Yamabe number, the energy-momentum tensor andthe mean curvature. In the limiting case, we prove that the hypersurfaceis an Einstein manifold with constant mean curvature.     

Cooperative game theoretic centrality analysis of terrorist networks: The cases of Jemaah Islamiyah and Al Qaeda

The identification of key players in a terrorist organization aids in preventing attacks, the efficient allocation of surveillance measures, and the destabilization of the corresponding network. In this paper, we introduce a game theoretic approach to identify key players in terrorist networks. In particular we use the Shapley value as a measure of importance in cooperative games that are specifically designed to reflect the context of the terrorist organization at hand. The advantage of this approach is that both the structure of the terrorist network, which usually reflects a communication and interaction structure, as well as non-network features, i.e., individual based parameters such as financial means or bomb building skills, can be taken into account. The application of our methodology to the analysis results in rankings of the terrorists in the network. We illustrate our methodology through two case studies: Jemaah Islamiyah’s Bali bombing and Al Qaedas 9/11 attack, which lead to new insights in the operational networks responsible for these attacks.     

On translation planes of orderq 3 that admit a collineation group of orderq 3, II

Let II be a translation plane of orderq ³ with kernel GF(q) that admits a collineation groupG of orderq ³ in the linear translation complement such thatG fixes a point at infinity and acts transitively on the remaining points at infinity.In this paper, we show that any such translation plane II is one of the following types of planes:     

Improper Coloring of Sparse Graphs with a Given Girth,II: Constructions

A graph G is ‐colorable if can be partitioned into two sets and so that the maximum degree of is at most j and of is at most k. While the problem of verifying whether a graph is (0, 0)‐colorable is easy, the similar problem with in place of (0, 0) is NP‐complete for all nonnegative j and k with . Let denote the supremum of all x such that for some constant every graph G with girth g and for every is ‐colorable. It was proved recently that . In a companion paper, we find the exact value . In this article, we show that increasing g from 5 further on does not increase much. Our constructions show that for every g, . We also find exact values of for all g and all .     

C(m,3)的交叉数

众所周知,任何一类非平凡图交叉数的精确值的确定都是非常困难的．作者证明了对任意k(?)2,h∈{0,1,2},循环图C(3k h,3)的交叉数为k h,但C(6,3),C(7,3)的交叉数都是1．C(5,3)的交叉数也是1．     

On geodesic structures of weakly median graphs—II: Compactness, the role of isometric rays

We prove that the vertex set of a K_ℵ0-free weakly median graph G endowed with the weak topology associated with the geodesic convexity on V(G) is compact if and only if G has one of the following equivalent properties: (1) G contains no isometric rays; (2) any chain of interval of G ordered by inclusion is finite; (3) every self-contraction of G fixes a non-empty finite regular weakly median subgraph of G. We study the self-contractions of K_ℵ0-free weakly median graphs which fix no finite set of vertices. We also follow a suggestion of Imrich and Klavzar [Product Graphs, Wiley, New York, 2000] by defining different centers of such a graph G, each of them giving rise to a non-empty finite regular weakly median subgraph of G which is fixed by all automorphisms of G.     

The diffeomorphic types of the complements of arrangements in ??3 II

For any arrangement of hyperplanes in ℂℙ³, we introduce the soul of this arrangement. The soul, which is a pseudo-complex, is determined by the combinatorics of the arrangement of hyperplanes. In this paper, we give a sufficient combinatoric condition for two arrangements of hyperplanes to be diffeomorphic to each other. In particular we have found sufficient conditions on combinatorics for the arrangement of hyperplanes whose moduli space is connected. This generalizes our previous result on hyperplane point arrangements in ℂℙ³. This work was partially supported by NSA grant and NSF grant     

The Subconstituent Algebra of an Association Scheme, (Part I)

We introduce a method for studying commutative association schemes with many vanishing intersection numbers and/or Krein parameters, and apply the method to the P- and Q-polynomial schemes. Let Y denote any commutative association scheme, and fix any vertex x of Y. We introduce a non-commutative, associative, semi-simple -algebra T = T(x) whose structure reflects the combinatorial structure of Y. We call T the subconstituent algebra of Y with respect to x. Roughly speaking, T is a combinatorial analog of the centralizer algebra of the stabilizer of x in the automorphism group of Y.In general, the structure of T is not determined by the intersection numbers of Y, but these parameters do give some information. Indeed, we find a relation among the generators of T for each vanishing intersection number or Krein parameter.We identify a class of irreducible T-moduIes whose structure is especially simple, and say the members of this class are thin. Expanding on this, we say Y is thin if every irreducible T(y)-module is thin for every vertex y of Y. We compute the possible thin, irreducible T-modules when Y is P- and Q-polynomial. The ones with sufficiently large dimension are indexed by four bounded integer parameters. If Y is assumed to be thin, then sufficiently large dimension means dimension at least four.We give a combinatorial characterization of the thin P- and Q-polynomial schemes, and supply a number of examples of these objects. For each example, we show which irreducible T-modules actually occur.We close with some conjectures and open problems.