Spanning 2-strong tournaments in 3-strong semicomplete digraphs

We prove that every 3-strong semicomplete digraph on at least 5 vertices contains a spanning 2-strong tournament. Our proof is constructive and implies a polynomial algorithm for finding a spanning 2-strong tournament in a given 3-strong semicomplete digraph. We also show that there are infinitely many (2k−2)-strong semicomplete digraphs which contain no spanning k-strong tournament and conjecture that every(2k−1)-strong semicomplete digraph which is not the complete digraph on 2k vertices contains a spanning k-strong tournament.     

On the spanning fan-connectivity of graphs

Let G be a graph. The connectivity of G, κ(G), is the maximum integer k such that there exists a k-container between any two different vertices. A k-container of G between u and v, C_k(u,v), is a set of k-internally-disjoint paths between u and v. A spanning container is a container that spans V(G). A graph G is k^∗-connected if there exists a spanning k-container between any two different vertices. The spanning connectivity of G, κ^∗(G), is the maximum integer k such that G is w^∗-connected for 1≤w≤k if G is 1^∗-connected.Let x be a vertex in G and let U={y₁,y₂,…,y_k} be a subset of V(G) where x is not in U. A spanningk−(x,U)-fan, F_k(x,U), is a set of internally-disjoint paths {P₁,P₂,…,P_k} such that P_i is a path connecting x to y_i for 1≤i≤k and . A graph G is k^∗-fan-connected (or -connected) if there exists a spanning F_k(x,U)-fan for every choice of x and U with |U|=k and x∉U. The spanning fan-connectivity of a graph G, , is defined as the largest integer k such that G is -connected for 1≤w≤k if G is -connected.In this paper, some relationship between κ(G), κ^∗(G), and are discussed. Moreover, some sufficient conditions for a graph to be -connected are presented. Furthermore, we introduce the concept of a spanning pipeline-connectivity and discuss some sufficient conditions for a graph to be k^∗-pipeline-connected.     

Edge colouring by total labellings

We introduce the concept of an edge-colouring total k-labelling. This is a labelling of the vertices and the edges of a graph G with labels 1,2,…,k such that the weights of the edges define a proper edge colouring of G. Here the weight of an edge is the sum of its label and the labels of its two endvertices. We define to be the smallest integer k for which G has an edge-colouring total k-labelling. This parameter has natural upper and lower bounds in terms of the maximum degree Δ of . We improve the upper bound by 1 for every graph and prove . Moreover, we investigate some special classes of graphs.     

Boxicity of Halin graphs

A k-dimensional box is the Cartesian product R₁×R₂×?×R_k where each R_i is a closed interval on the real line. The boxicity of a graph G, denoted as is the minimum integer k such that G is the intersection graph of a collection of k-dimensional boxes. Halin graphs are the graphs formed by taking a tree with no degree 2 vertex and then connecting its leaves to form a cycle in such a way that the graph has a planar embedding. We prove that if G is a Halin graph that is not isomorphic to K₄, then . In fact, we prove the stronger result that if G is a planar graph formed by connecting the leaves of any tree in a simple cycle, then unless G is isomorphic to K₄ (in which case its boxicity is 1).     

Images of locally finite derivations of polynomial algebras in two variables

In this paper we show that the image of any locally finite k-derivation of the polynomial algebra k[x,y] in two variables over a field k of characteristic zero is a Mathieu subspace. We also show that the two-dimensional Jacobian conjecture is equivalent to the statement that the image of every k-derivation D of k[x,y] such that and is a Mathieu subspace of k[x,y].     

Testing the stability of the functional autoregressive process

The functional autoregressive process has become a useful tool in the analysis of functional time series data. It is defined by the equation , in which the observations X_n and errors ε_n are curves, and is an operator. To ensure meaningful inference and prediction based on this model, it is important to verify that the operator does not change with time. We propose a method for testing the constancy of against a change-point alternative which uses the functional principal component analysis. The test statistic is constructed to have a well-known asymptotic distribution, but the asymptotic justification of the procedure is very delicate. We develop a new truncation approach which together with Mensov’s inequality can be used in other problems of functional time series analysis. The estimation of the principal components introduces asymptotically non-negligible terms, which however cancel because of the special form of our test statistic (CUSUM type). The test is implemented using the R package fda, and its finite sample performance is examined by application to credit card transaction data.     

Realizable classes of tetrahedral extensions

Let k be a number field and O_k its ring of integers. Let Γ be the alternating group A₄. Let be a maximal O_k-order in k[Γ] containing O_k[Γ] and its class group. We denote by the set of realizable classes, that is the set of classes such that there exists a Galois extension N/k at most tamely ramified, with Galois group isomorphic to Γ, for which the class of is equal to c, where O_N is the ring of integers of N. In this article we determine and we prove that it is a subgroup of provided that k and the 3rd cyclotomic field of are linearly disjoint, and the class number of k is odd.     

A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem

In this paper, we focus on the directed minimum degree spanning tree problem and the minimum time broadcast problem. Firstly, we propose a polynomial time algorithm for the minimum degree spanning tree problem in directed acyclic graphs. The algorithm starts with an arbitrary spanning tree, and iteratively reduces the number of vertices of maximum degree. We can prove that the algorithm must reduce a vertex of the maximum degree for each phase, and finally result in an optimal tree. The algorithm terminates in O(mnlogn) time, where m and n are the numbers of edges and vertices of the graph, respectively. Moreover, we apply the new algorithm to the minimum time broadcast problem. Two consequences for directed acyclic graphs are: (1) the problem under the vertex-disjoint paths mode can be approximated within a factor of of the optimum in O(mnlogn)-time; (2) the problem under the edge-disjoint paths mode can be approximated within a factor of O(Δ^*/logΔ^*) of the optimum in O(mnlogn)-time, where Δ^* is the minimum k such that there is a spanning tree of the graph with maximum degree k.     

Distance irredundance and connected domination numbers of a graph

Let k be a positive integer and G be a connected graph. This paper considers the relations among four graph theoretical parameters: the k-domination number γ_k(G), the connected k-domination number ; the k-independent domination number and the k-irredundance number ir_k(G). The authors prove that if an ir_k-set X is a k-independent set of G, then , and that for k?2, if ir_k(G)=1, if ir_k(G) is odd, and if ir_k(G) is even, which generalize some known results.     

On Gibbs measures of P-adic Potts model on the cayley tree

We consider a nearest-neighbor p-adic Potts (with q ≥ 2 spin values and coupling constant J ? _p) model on the Cayley tree of order k ≥ 1. It is proved that a phase transition occurs at k = 2, q ? p and p ≥ 3 (resp. q ? 2², p = 2). It is established that for p-adic Potts model at k ≥ 3 a phase transition may occur only at q ? p if p ≥ 3 and q ? 2² if p = 2.     

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.     

Some identities involving theta functions

Let (|q|<1). For k∈N it is shown that there exist k rational numbers A(k,0),…,A(k,k−1) such that

     

A subexponential algorithm for the coloured tree partition problem

Given a tree of n vertices and a list of feasible colours for each vertex, the coloured tree partition problem (CTPP) consists in partitioning the tree into p vertex-disjoint subtrees of minimum total cost, and assigning to each subtree a different colour, which must be feasible for all of its vertices. The problem is strongly NP-hard on general graphs, as well as on grid and bipartite graphs. This paper deals with the previously open case of tree graphs, showing that it is strongly NP-complete to determine whether a feasible solution exists. It presents reduction, decomposition and bounding procedures to simplify the problem and an exact algorithm of complexity (with ) for the special case in which a vertex of each subtree is given.     

Ratio asymptotic of Hermite-Padé orthogonal polynomials for Nikishin systems. II

We prove ratio asymptotic for sequences of multiple orthogonal polynomials with respect to a Nikishin system of measures N(σ₁,…,σm) such that for each k, σk has constant sign on its support consisting on an interval , on which almost everywhere, and a set without accumulation points in .     

The Erdös-Sós conjecture for spiders

A classical result on extremal graph theory is the Erdös-Gallai theorem: if a graph on n vertices has more than edges, then it contains a path of k edges. Motivated by the result, Erdös and Sós conjectured that under the same condition, the graph should contain every tree of k edges. A spider is a rooted tree in which each vertex has degree one or two, except for the root. A leg of a spider is a path from the root to a vertex of degree one. Thus, a path is a spider of 1 or 2 legs. From the motivation, it is natural to consider spiders of 3 legs. In this paper, we prove that if a graph on n vertices has more than edges, then it contains every k-edge spider of 3 legs, and also, every k-edge spider with no leg of length more than 4, which strengthens a result of Wo?niak on spiders of diameter at most 4.     

A characterization of k-hyponormality via weak subnormality

An operator T acting on a Hilbert space is said to be weakly subnormal if there exists an extension acting on such that for all . When such partially normal extensions exist, we denote by m.p.n.e.(T) the minimal one. On the other hand, for k?1, T is said to be k-hyponormal if the operator matrix is positive. We prove that a 2-hyponormal operator T always satisfies the inequality T∗[T∗,T]T?‖T‖2[T∗,T], and as a result T is automatically weakly subnormal. Thus, a hyponormal operator T is 2-hyponormal if and only if there exists B such that BA∗=A∗T and is hyponormal, where A:=[T∗,T]1/2. More generally, we prove that T is (k+1)-hyponormal if and and only if T is weakly subnormal and m.p.n.e.(T) is k-hyponormal. As an application, we obtain a matricial representation of the minimal normal extension of a subnormal operator as a block staircase matrix.     

Optimality conditions for Hunter’s bound

The bound known as Hunter’s bound states that , where T designates the heaviest spanning tree of the graph on n nodes with edge weights p_i,j. We prove that Hunter’s bound is optimal if and only if the input probabilities are given on a tree.