On the existence of graphs of diameter two and defect two

In the context of the degree/diameter problem, the ‘defect’ of a graph represents the difference between the corresponding Moore bound and its order. Thus, a graph with maximum degree d and diameter two has defect two if its order is n=d²−1. Only four extremal graphs of this type, referred to as (d,2,2)-graphs, are known at present: two of degree d=3 and one of degree d=4 and 5, respectively. In this paper we prove, by using algebraic and spectral techniques, that for all values of the degree d within a certain range, (d,2,2)-graphs do not exist.The enumeration of (d,2,2)-graphs is equivalent to the search of binary symmetric matrices A fulfilling that AJ_n=dJ_n and A²+A+(1−d)I_n=J_n+B, where J_n denotes the all-one matrix and B is the adjacency matrix of a union of graph cycles. In order to get the factorization of the characteristic polynomial of A in Q[x], we consider the polynomials F_i,d(x)=f_i(x²+x+1−d), where f_i(x) denotes the minimal polynomial of the Gauss period , being ζ_i a primitive ith root of unity. We formulate a conjecture on the irreducibility of F_i,d(x) in Q[x] and we show that its proof would imply the nonexistence of (d,2,2)-graphs for any degree d>5.     

Regular separable graphs of minimum order with given diameter

A (d, c, v)-graph G is one which is regular of degree v and has diameter d and connectivity c. G is said to be minimum if it is of minimum order, i.e. has the minimumnumber of points; G is separable if c=1.In this paper, the minimum order of a (d, 1, v)-graph is determined and the construction of all minimum (d, 1, v)-graphs is described.     

Generalization of matching extensions in graphs (III)

Proposing them as a general framework, Liu and Yu (2001) [6] introduced (n,k,d)-graphs to unify the concepts of deficiency of matchings, n-factor-criticality and k-extendability. Let G be a graph and let n,k and d be non-negative integers such that n+2k+d+2?|V(G)| and |V(G)|−n−d is even. If on deleting any n vertices from G the remaining subgraph H of G contains a k-matching and each k-matching can be extended to a defect-d matching in H, then G is called an (n,k,d)-graph. In this paper, we obtain more properties of (n,k,d)-graphs, in particular the recursive relations of (n,k,d)-graphs for distinct parameters n,k and d. Moreover, we provide a characterization for maximal non-(n,k,d)-graphs.     

Extremal results for odd cycles in sparse pseudorandom graphs

We consider extremal problems for subgraphs of pseudorandom graphs. For graphs F and Г the generalized Turán density π _F (Г) denotes the relative density of a maximum subgraph of Г, which contains no copy of F. Extending classical Turán type results for odd cycles, we show that π _F (Г)=1/2 provided F is an odd cycle and Г is a sufficiently pseudorandom graph. In particular, for (n,d,λ)-graphs Г, i.e., n-vertex, d-regular graphs with all non-trivial eigenvalues in the interval [?λ,λ], our result holds for odd cycles of length ?, provided $$\lambda ^{\ell - 2} \ll \frac{{d^{\ell - 1} }} {n}\log (n)^{ - (\ell - 2)(\ell - 3)} .$$ Up to the polylog-factor this verifies a conjecture of Krivelevich, Lee, and Sudakov. For triangles the condition is best possible and was proven previously by Sudakov, Szabó, and Vu, who addressed the case when F is a complete graph. A construction of Alon and Kahale (based on an earlier construction of Alon for triangle-free (n,d;λ)-graphs) shows that our assumption on Г is best possible up to the polylog-factor for every odd ?≥5.     

An approximation algorithm for finding a <Emphasis Type="Italic">d</Emphasis>-regular spanning connected subgraph of maximum weight in a complete graph with random weights of edges

An approximation algorithm is suggested for the problem of finding a d-regular spanning connected subgraph of maximum weight in a complete undirected weighted n-vertex graph. Probabilistic analysis of the algorithm is carried out for the problem with random input data (some weights of edges) in the case of a uniform distribution of the weights of edges and in the case of a minorized type distribution. It is shown that the algorithm finds an asymptotically optimal solution with time complexity O(n ²) when d = o(n). For the minimization version of the problem, an additional restriction on the dispersion of weights of the graph edges is added to the condition of the asymptotical optimality of the modified algorithm.     

Spectrum of the Laplacian on a covering graph with pendant edges I: The one-dimensional lattice and beyond

In this paper, we examine covering graphs that are obtained from the d  -dimensional integer lattice by adding pendant edges. In the case of d=1$d=1$, we show that the Laplacian on the graph has a spectral gap and establish a necessary and sufficient condition under which the Laplacian has no eigenvalues. In the case of d=2$d=2$, we show that there exists an arrangement of the pendant edges such that the Laplacian has no spectral gap.     

Geometric properties of Poisson matchings

Suppose that red and blue points occur as independent Poisson processes of equal intensity in ${\mathbb {R}^d}$ , and that the red points are matched to the blue points via straight edges in a translation-invariant way. We address several closely related properties of such matchings. We prove that there exist matchings that locally minimize total edge length in d?=?1 and d??? 3, but not in the strip ${\mathbb {R}\times[0,1]}$ . We prove that there exist matchings in which every bounded set intersects only finitely many edges in d ?? 2, but not in d = 1 or in the strip. It is unknown whether there exists a matching with no crossings in d = 2, but we prove positive answers to various relaxations of this question. Several open problems are presented.     

Generalization of matching extensions in graphs (II)

Proposed as a general framework, Liu and Yu [Generalization of matching extensions in graphs, Discrete Math. 231 (2001) 311-320.] introduced (n,k,d)-graphs to unify the concepts of deficiency of matchings, n-factor-criticality and k-extendability. Let G be a graph and let n,k and d be non-negative integers such that n+2k+d?|V(G)|-2 and |V(G)|-n-d is even. If when deleting any n vertices from G, the remaining subgraph H of G contains a k-matching and each such k-matching can be extended to a defect-d matching in H, then G is called an (n,k,d)-graph. Liu and Yu's Papee's paper, the recursive relations for distinct parameters n,k and d were presented and the impact of adding or deleting an edge also was discussed for the case d=0. In this paper, we continue the study begun by Liu and Yu and obtain new recursive results for (n,k,d)-graphs in the general case d?0.     

A matching problem with side conditions

Given a graph G, a 2-matching is an assignment of nonnegative integers to the edges of G such that for each node i of G, the sum of the values on the edges incident with i is at most 2. A triangle-free 2-matching is a 2-matching such that no cycle of size 3 in G has the value 1 assigned to all of its edges. In this paper we describe explicity the convex hull of triangle-free 2-matchings by means of its extreme points and of its facets. We give a polynomially bounded algorithm which maximizes a linear function over the set of triangle-free 2-matchings. Finally we discuss some related problems.     

More on “Connected (n, m)-graphs with minimum and maximum zeroth-order general Randi? index”

Let G be a graph and d(u) denote the degree of a vertex u in G. The zeroth-order general Randi? index ⁰R_α(G) of the graph G is defined as ∑_u∈V(G)d(u)^α, where the summation goes over all vertices of G and α is an arbitrary real number. In this paper we correct the proof of the main Theorem 3.5 of the paper by Hu et al. [Y. Hu, X. Li, Y. Shi, T. Xu, Connected (n,m)-graphs with minimum and maximum zeroth-order general Randi? index, Discrete Appl. Math. 155 (8) (2007) 1044-1054] and give a more general Theorem. We finally characterize ¹ for α<0 the connected G(n,m)-graphs with maximum value ⁰R_α(G(n,m)), where G(n,m) is a simple connected graph with n vertices and m edges.     

Optimal on-line flow time with resource augmentation

We study the problem of scheduling n jobs that arrive over time. We consider a non-preemptive setting on a single machine. The goal is to minimize the total flow time. We use extra resource competitive analysis: an optimal off-line algorithm which schedules jobs on a single machine is compared to a more powerful on-line algorithm that has ? machines. We design an algorithm of competitive ratio , where Δ is the maximum ratio between two job sizes, and provide a lower bound which shows that the algorithm is optimal up to a constant factor for any constant ?. The algorithm works for a hard version of the problem where the sizes of the smallest and the largest jobs are not known in advance, only Δ and n are known. This gives a trade-off between the resource augmentation and the competitive ratio.We also consider scheduling on parallel identical machines. In this case the optimal off-line algorithm has m machines and the on-line algorithm has ?m machines. We give a lower bound for this case. Next, we give lower bounds for algorithms using resource augmentation on the speed. Finally, we consider scheduling with hard deadlines, and scheduling so as to minimize the total completion time.     

Hypersurfaces in P n with 1-parameter symmetry groups II

We assume V a hypersurface of degree d in ${P^n({\mathbb C})}$ with isolated singularities and not a cone, admitting a group G of linear symmetries. In earlier work we treated the case when G is semi-simple; here we analyse the unipotent case. Our first main result lists the possible groups G. In each case we discuss the geometry of the action, reduce V to a normal form, find the singular points, study their nature, and calculate the Milnor numbers. The Tjurina number τ(V) ≤ (d ? 1) ^n–2(d ² ? 3d + 3): we call V oversymmetric if this value is attained. We calculate τ in many cases, and characterise the oversymmetric situations. In particular, we list all the cases with dim(G) = 2 which are the oversymmetric cases with d = 3.     

Finding small regular graphs of girths 6, 8 and 12 as subgraphs of cages

Small k-regular graphs of girth g where g=6,8,12 are obtained as subgraphs of minimal cages. More precisely, we obtain (k,6)-graphs on 2(kq−1) vertices, (k,8)-graphs on 2k(q²−1) vertices and (k,12)-graphs on 2kq²(q²−1), where q is a prime power and k is a positive integer such that q≥k≥3. Some of these graphs have the smallest number of vertices known so far among the regular graphs with girth g=6,8,12.     

Efficient implementation of a shifting algorithm

An efficient implementation of the shifting algorithm [2] for min-max tree partitioning is given. The complexity is reduced from ORk³ + kn) to O(Rk(k + log d) + n) where a tree of n vertices, radius, of R edges, and maximum degree d is partitioned into k + 1 subtrees. The improvement is mainly due to the new junction tree data structure which suggests a succinct representation for subsets of edges, of a given tree, that preserves the interrelation betqween the edges on the tree.     

On the risk of estimates for block decreasing densities

A density f=f(x₁,…,x_d) on [0,∞)^d is block decreasing if for each j∈{1,…,d}, it is a decreasing function of x_j, when all other components are held fixed. Let us consider the class of all block decreasing densities on [0,1]^d bounded by B. We shall study the minimax risk over this class using n i.i.d. observations, the loss being measured by the L₁ distance between the estimate and the true density. We prove that if S=log(1+B), lower bounds for the risk are of the form C(S^d/n)^1/(d+2), where C is a function of d only. We also prove that a suitable histogram with unequal bin widths as well as a variable kernel estimate achieve the optimal multivariate rate. We present a procedure for choosing all parameters in the kernel estimate automatically without loosing the minimax optimality, even if B and the support of f are unknown.     

The measure problem for rectangular ranges in d-space

Klee recently posed the question: find an efficient algorithm for computing the measure of a set of n intervals on the line, and the analog for n hyperrectangles (ranges) in d-space. The one-dimensional case is easily solved in O(n log n) and Bentley has proved an O(n^d?1log n) algorithm for dimension d ≥ 2. We present an algorithm for Klee's measure problem that has a worst-case running time of only O(n^d?1) for d?3. While Bentley's algorithm is based on segment trees and requires only linear storage for any dimension, the new method is based on quad-trees and requires quadratic storage for d > 2.     

The Fractional Clifford-Fourier Kernel

The Clifford-Fourier transform was introduced by Brackx, De Schepper and Sommen who subsequently computed its kernel in dimension d=2. Here we compute the kernel of a fractional version of the transform when d=2 and 4. In doing so we solve appropriate wave-type problems on spheres in two and four dimensions. We also give formulae for the solutions of these problems in all even dimensions and hence a means of computing the fractional Clifford-Fourier kernels in even dimensions.     

Nilpotency indices,degrees of iterations of affine triangular automorphisms,and Schubert calculus

Let f be a triangular automorphism of the affine N-space of degree d with Jacobian 1 over a \({\mathbb{Q}}\) -algebra R. We introduce a weighted nilpotency index ν(f) for f, and give a bound of deg(f ⁿ ) in terms of N, d and ν(f) for all \({n \in \mathbb{Z}}\) . When N = 2, our formula, combined with computation of the Hilbert series of certain graded algebras, yields the estimate deg(f ⁿ ) ≤ d ² ? d + 1 for all \({n \in \mathbb{Z}}\) . If n varies through all integers, this estimate turns out to be sharp and is related, somewhat unexpectedly, to the Schubert calculus on the Grassmannian G(d ? 1, 2d ? 2). Numerical computation for small degrees suggests that this estimate restricted to the inverse degree (i.e. n = ?1) is also sharp if d ≥ 3.