A note on the Path Kernel Conjecture

Let τ(G) denote the number of vertices in a longest path in a graph G=(V,E). A subset K of V is called a P_n-kernel of G if τ(G[K])≤n−1 and every vertex v∈V?K is adjacent to an end-vertex of a path of order n−1 in G[K]. It is known that every graph has a P_n-kernel for every positive integer n≤9. R. Aldred and C. Thomassen in [R.E.L. Aldred, C. Thomassen, Graphs with not all possible path-kernels, Discrete Math. 285 (2004) 297-300] proved that there exists a graph which contains no P₃₆₄-kernel. In this paper, we generalise this result. We construct a graph with no P₁₅₅-kernel and for each integer l≥0 we provide a construction of a graph G containing no P_τ(G)−l-kernel.     

GRASP and path relinking for project scheduling under partially renewable resources

Recently, in the field of project scheduling problems the concept of partially renewable resources has been introduced. Theoretically, it is a generalization of both renewable and non-renewable resources. From an applied point of view, partially renewable resources allow us to model a large variety of situations that do not fit into classical models, but can be found in real problems in timetabling and labor scheduling. In this paper, we develop some preprocessing techniques and several heuristic algorithms for the problem. Preprocessing significantly reduces the dimension of the problems, therefore improving the efficiency of solution procedures. Heuristic algorithms based on GRASP and Path relinking are then developed and tested on existing test instances, obtaining excellent results.     

A note on characterizations of the Natvig structure functions

In this note some new characterization results for multistate systems are obtained. In particular, a new characterization of the Natvig class of multistate systems is presented, which provides us an easy-to-use method of classifying multistate systems. Examples are given to illustrate our results.     

Decidable (= separable) objects and morphisms in lextensive categories

After investigating all conceivable properties of decidable objects and maps in left exact categories with well-behaved finite sums (‘lextensive categories’), we give a characterization in such categories of decidable morphisms which are (finite) coverings (in an appropriate sense). Finally, we give two applications of this result, to separable algebras and to local homeomorphisms. In both cases it explains categorically the advantage of two well-known notions — strongly separable algebras and local homeomorphisms with path lifting property, respectively.     

Interlaboratory comparisons – demonstrating degree of equivalence

 The role of matrix reference materials in the process of demonstrating the degree of equivalence of measurement results obtained from intercomparisons is outlined, reviewing exemplary selected experience gained at BAM regarding the determination of organic contaminants in environmental matrices. The specific characteristics of reference materials employed in the process of demonstrating equivalence between laboratories in the course of proficiency testing as well as the development, comparison and validation of methods are elaborated. The demand is for series of appropriately characterised samples which are fit for the purpose and it is seen from representative examples that the utilisation of such tailor-made RM designed to tackle the specific need of an analytical problem dominates over certified matrix reference materials in this context. Concluding, the role of certified matrix reference materials in quality assurance is briefly looked at both from the user’s and providers’ points of view. Received: 9 September 2002 Accepted: 16 December 2002 Presented at CERMM-3, Central European Reference Materials and Measurements Conference: The function of reference materials in the measurement process, May 30–June 1, 2002, Rogaška Slatina, Slovenia Correspondence to R. Becker     

Bounding the distance among longest paths in a connected graph

It is easy to see that in a connected graph any $2$ longest paths have a vertex in common. For $k\ge 7$, Skupień in 1966 obtained a connected graph in which some $k$ longest paths have no common vertex, but every $k?1$ longest paths have a common vertex. It is not known whether every $3$ longest paths in a connected graph have a common vertex and similarly for 4, 5, and $6$ longest path. Fujita et al. in 2015 give an upper bound on distance among $3$ longest paths in a connected graph. In this paper we give a similar upper bound on distance between $4$ longest paths and also for $k$ longest paths, in general.     

Algebraic Properties of the Path Ideal of a Tree

The path ideal (of length t ≥ 2) of a directed graph Γ is the monomial ideal, denoted I _t (Γ), whose generators correspond to the directed paths of length t in Γ. We study some of the algebraic properties of I _t (Γ) when Γ is a tree. We first show that I _t (Γ) is the facet ideal of a simplicial tree. As a consequence, the quotient ring R/I _t (Γ) is always sequentially Cohen–Macaulay, and the Betti numbers of R/I _t (Γ) do not depend upon the characteristic of the field. We study the case of the line graph in greater detail at the end of the article. We give an exact formula for the projective dimension of these ideals, and in some cases, we compute their arithmetical rank.     

固定合作规模网络的平均路径长度

本文提出了一种特殊的合作网络,称之为固定合作规模网络．我们重点研究了这类网络的平均路径长度,通过建立微分方程,得到平均路径长度的增加速度近似与网络规模的对数成正比．     

我国高端工程机械产业基地评选研究

分析了高端工程机械产业基地应具有的特点;给出了高端工程机械产业基地评选的基本原则;建立了合理的候选高端工程机械产业基地评价指标体系及评价方法,并将该方法应用于我国高端工程机械产业基地的评价与选择.研究结果表明:在国内高端工程机械行业已形成10个主要产业集群的情况下,若在全国范围内设立三个高端工程机械战略性新兴产业基地,则这些基地应分别在徐州、柳州和长沙组建.