On weights of induced paths and cycles in claw‐free and K1,r‐free graphs

Let G be a K_1,r ‐free graph (r ≥ 3) on n vertices. We prove that, for any induced path or induced cycle on k vertices in G (k ≥ 2r − 1 or k ≥ 2r, respectively), the degree sum of its vertices is at most (2r − 2)(n − α) where α is the independence number of G. As a corollary we obtain an upper bound on the length of a longest induced path and a longest induced cycle in a K_1,r ‐free graph. Stronger bounds are given in the special case of claw‐free graphs (i.e., r = 3). Sharpness examples are also presented. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 131–143, 2001     

Rank and biclique partitions of the complement of paths

The problem was posed of determining the biclique partition number of the complement of a Hamiltonian path (Monson, Rees, and Pullman, Bull. Inst. Combinatorics and Appl. 14 (1995), 17–86). We define the complement of a path P, denoted P , as the complement of P in K_m,n where P is a subgraph of K_m,n for some m and n. We give an exact formula for the biclique partition number of the complement of a path. In particular, we solve the problem posed in [9]. We also summarize our more general results on biclique partitions of the complement of forests. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 111–122, 1998     

Generalizations of tournaments: A survey

We survey results concerning various generalizations of tournaments. The reader will see that tournaments are by no means the only class of directed graphs with a very rich structure. We describe, among numerous other topics mostly related to paths and cycles, results on hamiltonian paths and cycles. The reader will see that although these problems are polynomially solvable for all of the classes described, they can be highly nontrivial, even for these “tournament-like” digraphs. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 171–202, 1998     

Gargano,Lewinter and Malerba问题的解

§1　IntroductionLet G be a graph with vertex-set V(G) ={ v1 ,v2 ,...,vn} .A labeling of G is a bijectionL:V(G)→{ 1,2 ,...,n} ,where L (vi) is the label of a vertex vi.A labeled graph is anordered pair (G,L) consisting of a graph G and its labeling L.Definition1.An increasing nonconsecutive path in a labeled graph(G,L) is a path(u1 ,u2 ,...,uk) in G such thatL(ui) + 1相似文献   

Time version of the shortest path problem in a stochastic-flow network

Many studies on hardware framework and routing policy are devoted to reducing the transmission time for a flow network. A time version of the shortest path problem thus arises to find a quickest path, which sends a given amount of data from the unique source to the unique sink with minimum transmission time. More specifically, the capacity of each arc in the flow network is assumed to be deterministic. However, in many real-life networks, such as computer systems, telecommunication systems, etc., the capacity of each arc should be stochastic due to failure, maintenance, etc. Such a network is named a stochastic-flow network. Hence, the minimum transmission time is not a fixed number. We extend the quickest path problem to evaluating the probability that d$d$ units of data can be sent under the time constraint T$T$. Such a probability is named the system reliability. In particular, the data are transmitted through two minimal paths simultaneously in order to reduce the transmission time. A simple algorithm is proposed to generate all (d,T)$(d,T)$-MPs and the system reliability can then be computed in terms of (d,T)$(d,T)$-MPs. Moreover, the optimal pair of minimal paths with highest system reliability could be obtained.     

A fuzzy shortest path with the highest reliability

This paper concentrates on a shortest path problem on a network where arc lengths (costs) are not deterministic numbers, but imprecise ones. Here, costs of the shortest path problem are fuzzy intervals with increasing membership functions, whereas the membership function of the total cost of the shortest path is a fuzzy interval with a decreasing linear membership function. By the max–min criterion suggested in [R.E. Bellman, L.A. Zade, Decision-making in a fuzzy environment, Management Science 17B (1970) 141–164], the fuzzy shortest path problem can be treated as a mixed integer nonlinear programming problem. We show that this problem can be simplified into a bi-level programming problem that is very solvable. Here, we propose an efficient algorithm, based on the parametric shortest path problem for solving the bi-level programming problem. An illustrative example is given to demonstrate our proposed algorithm.     

On the Analyticity of Underlying HKM Paths for Monotone Semidefinite Linear Complementarity Problems

An interior point method (IPM) defines a search direction at an interior point of the feasible region. These search directions form a direction field, which in turn defines a system of ordinary differential equations (ODEs). The solutions of the system of ODEs are called off-central paths, underlying paths lying in the interior of the feasible region. It is known that not all off-central paths are analytic, whether w.r.t. μ or , where μ represents the duality gap, at a solution of a given semidefinite linear complementarity problem, SDLCP (Sim and Zhao, Math. Program. 110:475–499, 2007). In Sim and Zhao (J. Optim. Theory Appl. 137:11–25, 2008), we give a necessary and sufficient condition for when an off-central path is analytic as a function of at a solution of a general SDLCP. It is then natural to ask about the analyticity of a SDLCP off-central path at a solution, as a function of μ. We investigate this in the current paper. Again, we work under the assumption that the given SDLCP satisfies strict complementarity condition.     

Indecomposable permutations, hypermaps and labeled Dyck paths

Hypermaps were introduced as an algebraic tool for the representation of embeddings of graphs on an orientable surface. Recently a bijection was given between hypermaps and indecomposable permutations; this sheds new light on the subject by connecting a hypermap to a simpler object. In this paper, a bijection between indecomposable permutations and labeled Dyck paths is proposed, from which a few enumerative results concerning hypermaps and maps follow. We obtain for instance an inductive formula for the number of hypermaps with n darts, p vertices and q hyperedges; the latter is also the number of indecomposable permutations of Sn with p cycles and q left-to-right maxima. The distribution of these parameters among all permutations is also considered.     

4度循环图的不交路及k-宽直径

研究了4度循环图,构造出其任意两点之间的四条内部点不交路,并且给出其宽直径的一个较好的上界。     

CO2在Cu表面还原成碳氢化合物的DFT计算研究

应用密度泛函理论（DFT）反应能计算及最小能量路径分析研究了CO2在气相和电化学环境中于Cu(111)单晶表面的还原过程。气相中,CO2还原为碳氢化合物的反应路径可能为：CO2(g) + H* → COOH* → (CO +OH)* → CHO*;CHO + H* → CH2O* → (CH2 + O)*;CH2* + 2H* → CH4或2CH2* → C2H4。整个反应由CO2(g) + H* → COOH* → (CO +OH)*,(CO + H)* → CHO*和CH2O* → (CH2 + O)*等几个步骤联合控制。在-0.50V (vs RHE) 以正的电势下,CO2在Cu(111)表面电化学还原主要形成HCOO-和CO吸附物;随着电势逐渐负移,CO2加氢解离形成CO的反应越来越容易,CO成为主要产物;随电势进一步变负,形成碳氢化合物的趋势逐渐变强。与CO2的气相化学还原不同的是,电化学环境下CO质子化形成的CHO中间体倾向于解离形成CH,而在气相中CHO中间体则倾向于进一步质子化形成CH2O中间体。