Proof of a conjecture on irredundance perfect graphs

Let ir(G) and γ(G) be the irredundance number and the domination number of a graph G, respectively. A graph G is called irredundance perfect if ir(H)=γ(H), for every induced subgraph H of G. In this article we present a result which immediately implies three known conjectures on irredundance perfect graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 292–306, 2002     

Hamiltonian N2‐locally connected claw‐free graphs

A graph G is N₂‐locally connected if for every vertex ν in G, the edges not incident with ν but having at least one end adjacent to ν in G induce a connected graph. In 1990, Ryjá?ek conjectured that every 3‐connected N₂‐locally connected claw‐free graph is Hamiltonian. This conjecture is proved in this note. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 142–146, 2005     

A rigid graph for every set

A graph G is called rigid if the identical mapping V(G)→V(G) is the only homomorphism G→G. In this note we give a simple construction of a rigid oriented graph on every set. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 108–110, 2002     

On disjoint configurations in infinite graphs

For a graph A and a positive integer n, let nA denote the union of n disjoint copies of A; similarly, the union of ?₀ disjoint copies of A is referred to as ?₀A. It is shown that there exist (connected) graphs A and G such that nA is a minor of G for all n??, but ?₀A is not a minor of G. This supplements previous examples showing that analogous statements are true if, instead of minors, isomorphic embeddings or topological minors are considered. The construction of A and G is based on the fact that there exist (infinite) graphs G₁, G₂,… such that G_i is not a minor of G_j for all i ≠ j. In contrast to previous examples concerning isomorphic embeddings and topological minors, the graphs A and G presented here are not locally finite. The following conjecture is suggested: for each locally finite connected graph A and each graph G, if nA is a minor of G for all n ? ?, then ?₀A is a minor of G, too. If true, this would be a far‐reaching generalization of a classical result of R. Halin on families of disjoint one‐way infinite paths in graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 222–229, 2002; DOI 10.1002/jgt.10016     

Highly edge‐connected detachments of graphs and digraphs

Let G = (V,E) be a graph or digraph and r : V → Z₊. An r‐detachment of G is a graph H obtained by ‘splitting’ each vertex ν ∈ V into r(ν) vertices. The vertices ν₁,…,ν_r(ν) obtained by splitting ν are called the pieces of ν in H. Every edge uν ∈ E corresponds to an edge of H connecting some piece of u to some piece of ν. Crispin Nash‐Williams 9 gave necessary and sufficient conditions for a graph to have a k‐edge‐connected r‐detachment. He also solved the version where the degrees of all the pieces are specified. In this paper, we solve the same problems for directed graphs. We also give a simple and self‐contained new proof for the undirected result. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 67–77, 2003     

Large families of mutually embeddable vertex‐transitive graphs

For each infinite cardinal κ, we give examples of 2^κ many non‐isomorphic vertex‐transitive graphs of order κ that are pairwise isomorphic to induced subgraphs of each other. We consider examples of graphs with these properties that are also universal, in the sense that they embed all graphs with smaller orders as induced subgraphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 99–106, 2003     

Formalising the Pathways to Life Using Assembly Spaces

Assembly theory (referred to in prior works as pathway assembly) has been developed to explore the extrinsic information required to distinguish a given object from a random ensemble. In prior work, we explored the key concepts relating to deconstructing an object into its irreducible parts and then evaluating the minimum number of steps required to rebuild it, allowing for the reuse of constructed sub-objects. We have also explored the application of this approach to molecules, as molecular assembly, and how molecular assembly can be inferred experimentally and used for life detection. In this article, we formalise the core assembly concepts mathematically in terms of assembly spaces and related concepts and determine bounds on the assembly index. We explore examples of constructing assembly spaces for mathematical and physical objects and propose that objects with a high assembly index can be uniquely identified as those that must have been produced using directed biological or technological processes rather than purely random processes, thereby defining a new scale of aliveness. We think this approach is needed to help identify the new physical and chemical laws needed to understand what life is, by quantifying what life does.     

Rigorous results on the thermodynamics of the dilute Hopfield model

We study the Hopfield model of an autoassociative memory on a random graph onN vertices where the probability of two vertices being joined by a link isp(N). Assuming thatp(N) goes to zero more slowly thanO(1/N), we prove the following results: (1) If the number of stored patternsm(N) is small enough such thatm(N)/Np(N) 0, asN, then the free energy of this model converges, upon proper rescaling, to that of the standard Curie-Weiss model, for almost all choices of the random graph and the random patterns. (2) If in additionm(N) < ln N/ln 2, we prove that there exists, forT< 1, a Gibbs measure associated to each original pattern, whereas for higher temperatures the Gibbs measure is unique. The basic technical result in the proofs is a uniform bound on the difference between the Hamiltonian on a random graph and its mean value.     

卡氏积图的Laplacian谱半径的上界

对近年来图的Laplacian谱半径上界的研究成果进行了简单梳理.利用2个图的卡氏积图的特征值,讨论了2个循环图的卡氏积图的Laplacian谱半径的上界问题,得到了几个上界,推广了已有文献的结论.