Covering line graphs with equivalence relations

An equivalence graph is a disjoint union of cliques, and the equivalence number of a graph G is the minimum number of equivalence subgraphs needed to cover the edges of G. We consider the equivalence number of a line graph, giving improved upper and lower bounds: . This disproves a recent conjecture that is at most three for triangle-free G; indeed it can be arbitrarily large.To bound we bound the closely related invariant σ(G), which is the minimum number of orientations of G such that for any two edges e,f incident to some vertex v, both e and f are oriented out of v in some orientation. When G is triangle-free, . We prove that even when G is triangle-free, it is NP-complete to decide whether or not σ(G)≤3.     

Markov interlacing property for exponential polynomials

Let Un be an extended Tchebycheff system on the real line. Given a point , where x₁<?<xn, we denote by the polynomial from Un, which has zeros x₁,…,xn. (It is uniquely determined up to multiplication by a constant.) The system Un has the Markov interlacing property (M) if the assumption that and interlace implies that the zeros of and interlace strictly, unless . We formulate a general condition which ensures the validity of the property (M) for polynomials from Un. We also prove that the condition is satisfied for some known systems, including exponential polynomials and . As a corollary we obtain that property (M) holds true for Müntz polynomials , too.     

Remarks on Hardy spaces defined by non-smooth approximate identity

We study in this paper some relations between Hardy spaces which are defined by non-smooth approximate identity ?(x), and the end-point Triebel-Lizorkin spaces (1?q?∞). First, we prove that for compact ? which satisfies a slightly weaker condition than Fefferman and Stein's condition. Then we prove that non-trivial Hardy space defined by approximate identity ? must contain Besov space . Thirdly, we construct certain functions and a function such that Daubechies wavelet function but .     

On mean distance and girth

We bound the mean distance in a connected graph which is not a tree in terms of its order n and its girth g. On one hand, we show that the mean distance is at most if g is even and at most if g is odd. On the other hand, we prove that the mean distance is at least unless G is an odd cycle. This resolves two conjectures of AutoGraphiX.     

Bi-Sobolev mappings with differential matrices in Orlicz Zygmund classes

Bi-Sobolev mappings have been defined as those homeomorphisms such that f and f−1 belong to . We deduce regularity properties of the distortion of f from the regularity of the differential matrix Df−1 and conversely.     

Inequalities of Nordhaus-Gaddum type for doubly connected domination number

A set S of vertices of a connected graph G is a doubly connected dominating set if every vertex not in S is adjacent to some vertex in S and the subgraphs induced by S and V−S are connected. The doubly connected domination numberγ_cc(G) is the minimum size of such a set. We prove that when G and are both connected of order n, and we describe the two infinite families of extremal graphs achieving the bound.     

Forwarding and optical indices of a graph

Motivated by wavelength-assignment problems for all-to-all traffic in optical networks, we study graph parameters related to sets of paths connecting all pairs of vertices. We consider sets of both undirected and directed paths, under minimisation criteria known as edge congestion and wavelength count; this gives rise to four parameters of a graph G: its edge forwarding index π(G), arc forwarding index , undirected optical index , and directed optical index .In the paper we address two long-standing open problems: whether the equality holds for all graphs, and whether indices π(G) and are hard to compute. For the first problem, we give an example of a family of planar graphs {G_k} such that . For the second problem, we show that determining either π(G) or is NP-hard.     

Facet-inducing web and antiweb inequalities for the graph coloring polytope

For a graph G and its complement , we define the graph coloring polytope P(G) to be the convex hull of the incidence vectors of star partitions of . We examine inequalities whose support graphs are webs and antiwebs appearing as induced subgraphs in G. We show that for an antiweb in G the corresponding inequality is facet-inducing for P(G) if and only if is critical with respect to vertex colorings. An analogous result is also proved for the web inequalities.     

The existence and upper bound for two types of restricted connectivity

In this paper, we study two types of restricted connectivity: κ_k(G) is the cardinality of a minimum vertex cut S such that every component of G−S has at least k vertices; is the cardinality of a minimum vertex cut S such that there are at least two components in G−S of order at least k. In this paper, we give some sufficient conditions for the existence and upper bound of κ_k(G) and/or , and study some properties of these two parameters.     

Efficient algorithms for robust generalized cross-validation spline smoothing

Generalized cross-validation (GCV) is a widely used parameter selection criterion for spline smoothing, but it can give poor results if the sample size n is not sufficiently large. An effective way to overcome this is to use the more stable criterion called robust GCV (RGCV). The main computational effort for the evaluation of the GCV score is the trace of the smoothing matrix, , while the RGCV score requires both and . Since 1985, there has been an efficient O(n) algorithm to compute . This paper develops two pairs of new O(n) algorithms to compute and , which allow the RGCV score to be calculated efficiently. The algorithms involve the differentiation of certain matrix functionals using banded Cholesky decomposition.     

On Γ-convergence of pairs of dual functionals

The paper considers a slightly modified notion of the Γ-convergence of convex functionals in uniformly convex Banach spaces and establishes that under standard coercitivity and growth conditions the Γ-convergence of a sequence of functionals {Fj} to implies that the corresponding sequence of dual functionals converges in an analogous sense to the dual to functional .     

Generalization of transitive fraternal augmentations for directed graphs and its applications

Let be a directed graph. A transitive fraternal augmentation of is a directed graph with the same vertex set, including all the arcs of and such that for any vertices x,y,z,

1.

if and then or (fraternity);

2.

if and then (transitivity).

In this paper, we explore some generalization of the transitive fraternal augmentations for directed graphs and its applications. In particular, we show that the 2-coloring number col₂(G)≤O(∇₁(G)∇₀(G)²), where ∇_k(G) (k≥0) denotes the greatest reduced average density with depth k of a graph G; we give a constructive proof that ∇_k(G) bounds the distance (k+1)-coloring number col_k+1(G) with a function f(∇_k(G)). On the other hand, ∇_k(G)≤(col_2k+1(G))^2k+1. We also show that an inductive generalization of transitive fraternal augmentations can be used to study nonrepetitive colorings of graphs.     

A note on the hardness of Skolem-type sequences

The purpose of this note is to give upper bounds (assuming different from ) on how far the generalizations of Skolem sequences can be taken while still hoping to resolve the existence question. We prove that the existence questions for both multi-Skolem sequences and generalized Skolem sequences are strongly -complete. These results are significant strengthenings and simplifications of the recent -completeness result for generalized multi-Skolem sequences.     

Kripke semantics for provability logic GLP

A well-known polymodal provability logic due to Japaridze is complete w.r.t. the arithmetical semantics where modalities correspond to reflection principles of restricted logical complexity in arithmetic. This system plays an important role in some recent applications of provability algebras in proof theory. However, an obstacle in the study of is that it is incomplete w.r.t. any class of Kripke frames. In this paper we provide a complete Kripke semantics for . First, we isolate a certain subsystem of that is sound and complete w.r.t. a nice class of finite frames. Second, appropriate models for are defined as the limits of chains of finite expansions of models for . The techniques involves unions of n-elementary chains and inverse limits of Kripke models. All the results are obtained by purely modal-logical methods formalizable in elementary arithmetic.