Disjoint Paths in Graphs III,Characterization

Let G be a graph, $ \{a, b, c\}\subseteq V(G) $, and $ \{a', b', c'\}\subseteq V(G) $ such that $ \{a, b, c\}\neq \{a', b', c'\} $. We say that $ (G, \{a, c\}, \{a', c'\}, (b, b')) $ is an obstruction if, for any three vertex disjoint paths from {a, b, c} to {a', b', c'} in G, one path is from b to b'. In this paper we characterize obstructions. As a consequence, we show that no obstruction can be 8-connected, unless b = b' or {a, c} = {a', c'}.AMS Subject Classification: 05C38.     

Hazard Evaluation of Ten Organophosphorus Insecticides Against the Midge,Chironomus riparius via QSAR

Abstract

Toxicities of ten organophosphorus (OP) insecticides were measured against midge larvae (Chironomus riparius) under varying temperature (11, 18, and 25°C) and pH (6, 7, and 8) conditions and with and without sediment. Toxicity usually increased with increasing temperature and was greater in the absence of sediment. No trend was found with varying pH. A series of unidimensional parameters and multidimensional models were used to describe the changes in toxicity. Log K _ow was able to explain about 40–60% of the variability in response data for aqueous exposures while molecular volume and aqueous solubility were less predictive. Likewise, the linear solvation energy relationship (LSER) model only explained 40–70% of the response variability, suggesting that factors other than solubility were most important for producing the observed response. Molecular connectivity was the most useful for describing the variability in the response. In the absence of sediment, ¹χ ^v and ³κ were best able to describe the variation in response among all compounds at each pH (70–90%). In the presence of sediment, even molecular connectivity could not describe the variability until the partitioning potential to sediment was accounted for by assuming equilibrium partitioning. After correcting for partitioning, the same molecular connectivity terms as in the aqueous exposures described most of the variability, 61–87%, except for the 11°C data where correlations were not significant. Molecular connectivity was a better tool than LSER or the unidimensional variables to explain the steric fitness of OP insecticides which was crucial to the toxicity.     

Domination dot-critical graphs with no critical vertices

A graph G is dot-critical if contracting any edge decreases the domination number. It is totally dot-critical if identifying any two vertices decreases the domination number. Burton and Sumner [Discrete Math. 306 (2006) 11-18] posed the problem: Is it true that for k?4, there exists a totally k-dot-critical graph with no critical vertices? In this paper, we show that this problem has a positive answer.     

Characterization of graphs with infinite cyclic edge connectivity

In this paper, we characterize the graphs with infinite cyclic edge connectivity. Then we design an efficient algorithm to determine whether a graph has finite cyclic edge connectivity or infinite cyclic edge connectivity.     

The diameter of paired-domination vertex critical graphs

In this paper we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 32 (1998), 199–206). A paired-dominating set of a graph G with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of G, denoted by γ _pr(G), is the minimum cardinality of a paired-dominating set of G. The graph G is paired-domination vertex critical if for every vertex v of G that is not adjacent to a vertex of degree one, γ _pr(G − v) < γ _pr(G). We characterize the connected graphs with minimum degree one that are paired-domination vertex critical and we obtain sharp bounds on their maximum diameter. We provide an example which shows that the maximum diameter of a paired-domination vertex critical graph is at least 3/2 (γ _pr(G) − 2). For γ _pr(G) ⩽ 8, we show that this lower bound is precisely the maximum diameter of a paired-domination vertex critical graph. The first author was supported in part by the South African National Research Foundation and the University of KwaZulu-Natal, the second author was supported by the Natural Sciences and Engineering Research Council of Canada.     

K1,r-free图中点独立数与其它参数之间的关系

给出了K1，r-free图中点独立数与其它参数如点数，边数，坚韧度，连通度等之间的一些关系。     

An improved molecular connectivity index

Through modification of the delta values of the molecular connectivity indexes, and connecting the quantum chemistry with topology method effectively, the molecular connectivity indexes are converted into quantum-topology indexes. The modified indexes not only keep all information obtained from the original molecular connectivity method but also have their own virtue in application, and at the same time make up some disadvantages of the quantum and molecular connectivity methods.     

On arbitrarily vertex decomposable trees

A tree T is arbitrarily vertex decomposable if for any sequence τ of positive integers adding up to the order of T there is a sequence of vertex-disjoint subtrees of T whose orders are given by τ; from a result by Barth and Fournier it follows that Δ(T)?4. A necessary and a sufficient condition for being an arbitrarily vertex decomposable star-like tree have been exhibited. The conditions seem to be very close to each other.     

哈密尔顿性和部分平方图的独立集

设G是一个图,G的部分平方图G*满足V(G*)=V(G),E(G*)=E(G)∪{uv:uv■E(G),且J(u,v)≠■},这里J(u,v)={w∈N(u)∩N(v):N(w)■N[u]∪N[v]}.利用插点方法,证明了如下结果:设G是k-连通图(k2),b是整数,0min {k,(2b-1+k)/2}(n(Y)-1),则G是哈密尔顿图.同时给出图是1-哈密尔顿的和哈密尔顿连通的相关结果.