Some remarks on the geodetic number of a graph

A set of vertices D of a graph G is geodetic if every vertex of G lies on a shortest path between two not necessarily distinct vertices in D. The geodetic number of G is the minimum cardinality of a geodetic set of G.We prove that it is NP-complete to decide for a given chordal or chordal bipartite graph G and a given integer k whether G has a geodetic set of cardinality at most k. Furthermore, we prove an upper bound on the geodetic number of graphs without short cycles and study the geodetic number of cographs, split graphs, and unit interval graphs.     

Cover-incomparability graphs and chordal graphs

The problem of recognizing cover-incomparability graphs (i.e. the graphs obtained from posets as the edge-union of their covering and incomparability graph) was shown to be NP-complete in general [J. Maxová, P. Pavlíkova, A. Turzík, On the complexity of cover-incomparability graphs of posets, Order 26 (2009) 229-236], while it is for instance clearly polynomial within trees. In this paper we concentrate on (classes of) chordal graphs, and show that any cover-incomparability graph that is a chordal graph is an interval graph. We characterize the posets whose cover-incomparability graph is a block graph, and a split graph, respectively, and also characterize the cover-incomparability graphs among block and split graphs, respectively. The latter characterizations yield linear time algorithms for the recognition of block and split graphs, respectively, that are cover-incomparability graphs.     

Improved lower bounds for the Split Delivery Vehicle Routing Problem

This paper presents an algorithm to obtain lower bounds for the Split Delivery Vehicle Routing Problem. An extended formulation over a large set of variables is provided and valid inequalities are identified. The algorithm combined column and cut generation and improved the best known lower bounds for all instances from the literature. Some reasonably sized instances are solved to optimality for the first time.     

Split-By-Nilpotent Extensions Algebras and Stratifying Systems

Let Γ and Λ be artin algebras such that Γ is a split-by-nilpotent extension of Λ by a two sided ideal I of Γ. Consider the change of rings functors G: =_ΓΓ_Λ ?_Λ ? and F: =_ΛΛ_Γ ?_Γ ?. In this article, by assuming that I _Λ is projective, we find the necessary and sufficient conditions under which a stratifying system (Θ, ≤) in modΛ can be lifted to a stratifying system (GΘ, ≤) in mod(Γ). Furthermore, by using the functors F and G, we study the relationship between their filtered categories of modules; and some connections with their corresponding standardly stratified algebras are stated (see Theorem 5.12, Theorem 5.15 and Theorem 5.18). Finally, a sufficient condition is given for stratifying systems in mod(Γ) in such a way that they can be restricted, through the functor F, to stratifying systems in mod(Λ).     

The Join of Split Graphs Whose Regular Endomorphisms Form a Monoid

In this paper, the regular endomorphisms of the join of split graphs are investigated. We give a condition under which the regular endomorphisms of the join of split graphs form a monoid.     

基于裂开型核酸适体非标记荧光法检测ATP

基于裂开型核酸适体序列短、能有效降低因探针形成二级结构产生假阳性信号等优点,选择裂开型核酸适体作为特异性识别探针,核酸染料噻唑橙（TO）为信号探针,用单壁碳纳米管（SWCNTs）降低背景信号,利用“适配体-目标分子-适配体”的“三明治”夹心方式,建立了一种检测ATP的新方法。在pH 8.0的Tris-HCl缓冲溶液中,裂开成两段的ATP适体特异性识别ATP分子,生成稳定的“适配体-ATP-适配体”复合结构。单壁碳纳米管对该复合结构的吸附力较弱,因此该复合物游离在溶液中,TO与其结合而产生强荧光。当不存在ATP时,核酸适体探针以单链状态存在,可通过π-π共轭作用结合到SWCNTs表面,进而不能与TO结合,TO游离在溶液中荧光非常微弱。反应体系中ATP浓度越高,形成的“适配体-ATP-适配体”夹心识别结构复合物越多,检测到的荧光强度越大,据此实现对ATP的检测。在优化实验条件下,在最大荧光发射波长550 nm处,ATP的浓度在9.0×10-9～1.0×10-7 mol·L-1范围内与ΔF/F₀值成线性关系,r=0.996 4。该方法加标回收率为95.2%～104%,相对标准偏差（RSD）为1.02%～4.54%,检出限达到2.67×10-9 mol·L-1。该方法基于功能核酸对目标物亲合力强、选择识别性高的特点,对ATP的检测表现出很好的选择性,实验结果表明,当相对误差控制在±5%以内时,200倍的UTP,GTP和CTP均不干扰ATP的测定。另外,该方法操作简单、快速、无需标记、灵敏准确,可用于血清样品中ATP的测定,在快速检测小分子物质领域中有较好的应用前景。     

基于力的多边形的分置式斯特林制冷机的动力分析

动力分析是斯特林制冷机动力设计与调试实践中的关键一环。本文利用力的多边形描述了分置式斯特林制冷机中压缩活塞和排出器振子的运动方程,并将分析结果与实验结果进行对比,分析和讨论了分置式斯特林制冷机中重要的运行参数(如工作频率、固有频率、弹簧刚度、冷头温度、压缩腔和膨胀腔的PV功等)之间的相互影响。     

An empirical study on the benefit of split loads with the pickup and delivery problem

Splitting loads such that the delivery of certain loads is completed in multiple trips rather than one trip has been shown to have benefit for both the classic Vehicle Routing Problem (VRP) and the Pickup and Delivery Problem (PDP). However, the magnitude of the benefit may be affected by various problem characteristics. In this paper, we characterize those real world environments in which split loads are most likely to be beneficial. Based on practitioner interest, we determine how the benefit is affected by the mean load size and variance, number of origins relative to the number of destinations, the percentage of origin–destination pairs with a load requiring service, and the clustering of origin and destination locations. We find that the magnitude of benefit is greatest for load sizes just over one half vehicle capacity as these loads can not be combined without splitting, while they are the easiest to combine on a vehicle with splitting; increases as the number of loads sharing an origin or destination increases because there are more potential load combinations to split at each stop; and increases as the average distance from an origin to a destination increases because splitting loads reduces the trips from origins to destinations.     

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation

We study complexity and approximation of min weighted node coloring in planar, bipartite and split graphs. We show that this problem is NP-hard in planar graphs, even if they are triangle-free and their maximum degree is bounded above by 4. Then, we prove that min weighted node coloring is NP-hard in P₈-free bipartite graphs, but polynomial for P₅-free bipartite graphs. We next focus on approximability in general bipartite graphs and improve earlier approximation results by giving approximation ratios matching inapproximability bounds. We next deal with min weighted edge coloring in bipartite graphs. We show that this problem remains strongly NP-hard, even in the case where the input graph is both cubic and planar. Furthermore, we provide an inapproximability bound of 7/6−ε, for any ε>0 and we give an approximation algorithm with the same ratio. Finally, we show that min weighted node coloring in split graphs can be solved by a polynomial time approximation scheme.