On quasi-strongly regular graphs

We study the quasi-strongly regular graphs, which are a combinatorial generalization of the strongly regular and the distance regular graphs. Our main focus is on quasi-strongly regular graphs of grade 2. We prove a “spectral gap”-type result for them which generalizes Seidel's well-known formula for the eigenvalues of a strongly regular graph. We also obtain a number of necessary conditions for the feasibility of parameter sets and some structural results. We propose the heuristic principle that the quasi-strongly regular graphs can be viewed as a “lower-order approximation” to the distance regular graphs. This idea is illustrated by extending a known result from the distance-regular case to the quasi-strongly regular case. Along these lines, we propose a number of conjectures and open problems. Finally, we list the all the proper connected quasi-strongly graphs of grade 2 with up to 12 vertices.     

Eigenvalue interlacing and weight parameters of graphs

Eigenvalue interlacing is a versatile technique for deriving results in algebraic combinatorics. In particular, it has been successfully used for proving a number of results about the relation between the (adjacency matrix or Laplacian) spectrum of a graph and some of its properties. For instance, some characterizations of regular partitions, and bounds for some parameters, such as the independence and chromatic numbers, the diameter, the bandwidth, etc., have been obtained. For each parameter of a graph involving the cardinality of some vertex sets, we can define its corresponding weight parameter by giving some “weights” (that is, the entries of the positive eigenvector) to the vertices and replacing cardinalities by square norms. The key point is that such weights “regularize” the graph, and hence allow us to define a kind of regular partition, called “pseudo-regular,” intended for general graphs. Here we show how to use interlacing for proving results about some weight parameters and pseudo-regular partitions of a graph. For instance, generalizing a well-known result of Lovász, it is shown that the weight Shannon capacity Θ^* of a connected graph Γ, with n vertices and (adjacency matrix) eigenvalues λ₁ > λ₂ … λ_n, satisfies

where Θ is the (standard) Shannon capacity and v is the positive eigenvector normalized to have smallest entry 1. In the special case of regular graphs, the results obtained have some interesting corollaries, such as an upper bound for some of the multiplicities of the eigenvalues of a distance-regular graph. Finally, some results involving the Laplacian spectrum are derived.     

Fuzzy logic in measurements

Our main interest in this paper is to translate from “natural language” into “system theoretical language”. This is of course important since a statement in system theory can be analyzed mathematically or computationally. We assume that, in order to obtain a good translation, “system theoretical language” should have great power of expression. Thus we first propose a new frame of system theory, which includes the concepts of “measurement” as well as “state equation”. And we show that a certain statement in usual conversation, i.e., fuzzy modus ponens with the word “very”, can be translated into a statement in the new frame of system theory. Though our result is merely one example of the translation from “natural language” into “system theoretical language”, we believe that our method is fairly general.     

Combinatorial aspects of geometric graphs

As a special case of our main result, we show that for all L> 0, each k-nearest neighbor graph in d dimensions excludes K_h as a depth L minor if h = Ω(L^d). More generally, we prove that the overlap graphs defined by Miller, Teng, Thurston and Vavasis (1993) have this combinatorial property. By a construction of Plotkin, Rao and Smith (1994), our result implies that overlap graphs have “good” cut-covers, answering an open question of Kaklamanis, Krizanc and Rao (1993). Consequently, overlap graphs can be emulated on hypercube graphs with a constant factor of slow-down and on butterfly graphs with a factor of O(log^* n) slow-down. Therefore, computations on overlap graphs, such as finite element and finite difference methods on “well-conditioned” meshes and image processing on k-nearest neighbor graphs, can be performed on hypercubic parallel machines with a linear speed-up. Our result, in conjunction with a result of Plotkin, Rao and Smith, also yields a combinatorial proof that overlap graphs have separators of sublinear size. We also show that with high probability, the Delaunay diagram, the relative neighborhood graph, and the k-nearest neighbor graph of a random point set exclude K_h as a depth L minor if h = Ω(L^d/2 log n).     

Geometric aspects of 2-walk-regular graphs

A t-walk-regular graph is a graph for which the number of walks of given length between two vertices depends only on the distance between these two vertices, as long as this distance is at most t. Such graphs generalize distance-regular graphs and t-arc-transitive graphs. In this paper, we will focus on 1- and in particular 2-walk-regular graphs, and study analogues of certain results that are important for distance-regular graphs. We will generalize Delsarte?s clique bound to 1-walk-regular graphs, Godsil?s multiplicity bound and Terwilliger?s analysis of the local structure to 2-walk-regular graphs. We will show that 2-walk-regular graphs have a much richer combinatorial structure than 1-walk-regular graphs, for example by proving that there are finitely many non-geometric 2-walk-regular graphs with given smallest eigenvalue and given diameter (a geometric graph is the point graph of a special partial linear space); a result that is analogous to a result on distance-regular graphs. Such a result does not hold for 1-walk-regular graphs, as our construction methods will show.     

Walks and regular integral graphs

We establish a useful correspondence between the closed walks in regular graphs and the walks in infinite regular trees, which, after counting the walks of a given length between vertices at a given distance in an infinite regular tree, provides a lower bound on the number of closed walks in regular graphs. This lower bound is then applied to reduce the number of the feasible spectra of the 4-regular bipartite integral graphs by more than a half.Next, we give the details of the exhaustive computer search on all 4-regular bipartite graphs with up to 24 vertices, which yields a total of 47 integral graphs.     

Comment on “The Steiner number of a graph” by G. Chartrand and P. Zhang: [Discrete Mathematics 242 (2002) 41–54]

We show by counterexample that one of the main results in the paper “The Steiner number of a graph” by Chartrand and Zhang (Disc. Math. 242 (2002) 41–54) does not hold. To be more precise, we prove both that not every Steiner set is a geodetic set and that there are connected graphs whose Steiner number is strictly lower than its geodetic number.     

A quantum mechanical approach to a fuzzy theory

Recently, we proposed a general measurement theory for classical and quantum systems (i.e., “objective fuzzy measurement theory”). In this paper, we propose “subjective fuzzy measurement theory”, which is characterized as the statistical method of the objective fuzzy measurement theory. Our proposal of course has a lot of advantages. For example, we can directly see “membership functions” (= “fuzzy sets”) in this theory. Therefore, we can propose the objective and the subjective methods of membership functions. As one of the consequences, we assert the objective (i.e., individualistic) aspect of Zadeh's theory. Also, as a quantum application, we clarify Heisenberg's uncertainty relation.     

Polynomial algorithms that prove an NP-Hard hypothesis implies an NP-hard conclusion

A number of results in hamiltonian graph theory are of the form “ implies ”, where is a property of graphs that is NP-hard and is a cycle structure property of graphs that is also NP-hard. An example of such a theorem is the well-known Chvátal–Erd s Theorem, which states that every graph G with κ is hamiltonian. Here κ is the vertex connectivity of G and is the cardinality of a largest set of independent vertices of G. In another paper Chvátal points out that the proof of this result is in fact a polynomial time construction that either produces a Hamilton cycle or a set of more than κ independent vertices. In this note we point out that other theorems in hamiltonian graph theory have a similar character. In particular, we present a constructive proof of a well-known theorem of Jung (Ann. Discrete Math. 3 (1978) 129) for graphs on 16 or more vertices.     

Construction of the value function in a pursuit-evasion game with three pursuers and one evader

A differential pursuit-evasion game is considered with three pursuers and one evader. It is assumed that all objects (players) have simple motions and that the game takes place in a plane. The control vectors satisfy geometrical constraints and the evader has a superiority in control resources. The game time is fixed. The value functional is the distance between the evader and the nearest pursuer at the end of the game. The problem of determining the value function of the game for any possible position is solved.

Three possible cases for the relative arrangement of the players at an arbitrary time are studied: “one-after-one”, “two-after-one”, “three-after-one-in-the-middle” and “three-after-one”. For each of the relative arrangements of the players a guaranteed result function is constructed. In the first three cases the function is expressed analytically. In the fourth case a piecewise-programmed construction is presented with one switchover, on the basis of which the value of the function is determined numerically. The guaranteed result function is shown to be identical with the game value function. When the initial pursuer positions are fixed in an arbitrary manner there are four game domains depending on their relative positions. The boundary between the “three-after-one-in-the-middle” domain and the “three-after-one” domain is found numerically, and the remaining boundaries are interior Nicomedean conchoids, lines and circles. Programs are written that construct singular manifolds and the value function level lines.     

A Family of Partial Geometric Designs from Three‐Class Association Schemes

In this paper, we show that partial geometric designs can be constructed from certain three‐class association schemes and ternary linear codes with dual distance three. In particular, we obtain a family of partial geometric designs from the three‐class association schemes introduced by Kageyama, Saha, and Das in their article [“Reduction of the number of associate classes of hypercubic association schemes,” Ann Inst Statist Math 30 (1978)]. We also give a list of directed strongly regular graphs arising from the partial geometric designs obtained in this paper.     

An experimental comparison of four graph drawing algorithms

In this paper we present an extensive experimental study comparing four general-purpose graph drawing algorithms. The four algorithms take as input general graphs (with no restrictions whatsoever on connectivity, planarity, etc.) and construct orthogonal grid drawings, which are widely used in software and database visualization applications. The test data (available by anonymous ftp) are 11,582 graphs, ranging from 10 to 100 vertices, which have been generated from a core set of 112 graphs used in “real-life” software engineering and database applications. The experiments provide a detailed quantitative evaluation of the performance of the four algorithms, and show that they exhibit trade-offs between “aesthetic” properties (e.g., crossings, bends, edge length) and running time.     

Generic pairs of SU-rank 1 structures

For a supersimple SU-rank 1 theory T we introduce the notion of a generic elementary pair of models of T (generic T-pair). We show that the theory T^* of all generic T-pairs is complete and supersimple. In the strongly minimal case, T^* coincides with the theory of infinite dimensional pairs, which was used in (S. Buechler, Pseudoprojective strongly minimal sets are locally projective, J. Symbolic Logic 56(4) (1991) 1184–1194) to study the geometric properties of T. In our SU-rank 1 setting, we use T^* for the same purpose. In particular, we obtain a characterization of linearity for SU-rank 1 structures by giving several equivalent conditions on T^*, find a “weak” version of local modularity which is equivalent to linearity, show that linearity coincides with 1-basedness, and use the generic pairs to “recover” projective geometries over division rings from non-trivial linear SU-rank 1 structures.     

Polygonal chains cannot lock in 4D

We prove that, in all dimensions d4, every simple open polygonal chain and every tree may be straightened, and every simple closed polygonal chain may be convexified. These reconfigurations can be achieved by algorithms that use polynomial time in the number of vertices, and result in a polynomial number of “moves”. These results contrast to those known for d=2, where trees can “lock”, and for d=3, where open and closed chains can lock.     

Ovoids of generalized quadrangles of order and Delsarte cocliques in related strongly regular graphs

We investigate strongly regular graphs for which Hoffman's ratio bound and Cvetcović's inertia bound are equal. This means that , where v is the number of vertices, k is the regularity, is the smallest eigenvalue, and is the multiplicity of . We show that Delsarte cocliques do not exist for all Taylor's 2‐graphs and for point graphs of generalized quadrangles of order for infinitely many q. For cases where equality may hold, we show that for nearly all parameter sets, there are at most two Delsarte cocliques.     

Planar and axially symmetric configurations which are circumvented with the maximum critical mach number

The structure of planar and axially symmetric configurations which, by satisfying a number of geometrical constraints, are circumvented in a boundless space or in a cylindrical channel by an ideal (non-viscous and non-thermally conducting) gas with a maximal critical Mach number M* is found. The analysis is carried out using the “rectilinearity property” of a sonic line in “subsonic” flows (SF), the “principle of a maximum” for an SF and “comparison theorems” which are either taken from /1/ or serve as a generalization of the corresponding assertions from /1/. Following /1/, configurations are considered which have a plane or axis of symmetry parallel to the velocity V_∞ of the approach stream, while flows in which (including the boundary) the Mach number M 1 are said to be “subsonic”. As usual, by M* we mean a value of M_∞ such that the inequality M1, which is satisfied in the whole stream when M_∞ M*, is violated when M_∞>M*.

The configurations investigated include closed bodies and the leading (trailing) parts of a semi-infinite plate or a circular cylinder in an unbounded flow and in a channel as well as lattices of symmetric profiles. Both in /1/, where the structure of closed planar and axially symmetric bodies was found, as well as in /2/, where such bodies were constructed numerically, the generatrices of all the configurations investigated contain the end planes or the segments replacing them of the maximum permissible slope (in modulus) and the “free” streamlines with M 1. Now, however, unlike in /1, 2/, segments of the horizontals are added to it in the general case. Furthermore, in the case of flows in channels and lattices, the configurations which have been found can be circumvented with the development of finite domains of advancing sonic flow.     

Landmarks in graphs

Navigation can be studied in a graph-structured framework in which the navigating agent (which we shall assume to be a point robot) moves from node to node of a “graph space”. The robot can locate itself by the presence of distinctively labeled “landmark” nodes in the graph space. For a robot navigating in Euclidean space, visual detection of a distinctive landmark provides information about the direction to the landmark, and allows the robot to determine its position by triangulation. On a graph, however, there is neither the concept of direction nor that of visibility. Instead, we shall assume that a robot navigating on a graph can sense the distances to a set of landmarks.

Evidently, if the robot knows its distances to a sufficiently large set of landmarks, its position on the graph is uniquely determined. This suggests the following problem: given a graph, what are the fewest number of landmarks needed, and where should they be located, so that the distances to the landmarks uniquely determine the robot's position on the graph? This is actually a classical problem about metric spaces. A minimum set of landmarks which uniquely determine the robot's position is called a “metric basis”, and the minimum number of landmarks is called the “metric dimension” of the graph. In this paper we present some results about this problem. Our main new results are that the metric dimension of a graph with n nodes can be approximated in polynomial time within a factor of O(log n), and some properties of graphs with metric dimension two.     

Multi-step quasi-Newton methods for optimization

Quasi-Newton methods update, at each iteration, the existing Hessian approximation (or its inverse) by means of data deriving from the step just completed. We show how “multi-step” methods (employing, in addition, data from previous iterations) may be constructed by means of interpolating polynomials, leading to a generalization of the “secant” (or “quasi-Newton”) equation. The issue of positive-definiteness in the Hessian approximation is addressed and shown to depend on a generalized version of the condition which is required to hold in the original “single-step” methods. The results of extensive numerical experimentation indicate strongly that computational advantages can accrue from such an approach (by comparison with “single-step” methods), particularly as the dimension of the problem increases.     

Pseudo-Strong Regularity Around a Set

A generalization of strong regularity around a vertex subset C of a graph Γ, which makes sense even if Γis non-regular, is studied. Such a structure appears, together with a kind of distance-regularity around C , when an spectral bound concerning the so-called predistance polynomial of C is attained. As a main consequence of these results, it is shown that a regular (connected) graph Γwith d + 1 distinct eigenvalues is distance-regular, and its distance- d graph Γ d is strongly regular with parameters a = c , if and only if the number of vertices at distance d from each vertex satisfies an expression which depends only on the order of Γand the different eigenvalues of Γ.