The connected partition lattice of a graph and the reconstruction conjecture

Previously we showed that many invariants of a graph can be computed from its abstract induced subgraph poset, which is the isomorphism class of the induced subgraph poset, suitably weighted by subgraph counting numbers. In this paper, we study the abstract bond lattice of a graph, which is the isomorphism class of the lattice of distinct unlabelled connected partitions of a graph, suitably weighted by subgraph counting numbers. We show that these two abstract posets can be constructed from each other except in a few trivial cases. The constructions rely on certain generalisations of a lemma of Kocay in graph reconstruction theory to abstract induced subgraph posets. As a corollary, trees are reconstructible from their abstract bond lattice. We show that the chromatic symmetric function and the symmetric Tutte polynomial of a graph can be computed from its abstract induced subgraph poset. Stanley has asked if every tree is determined up to isomorphism by its chromatic symmetric function. We prove a counting lemma, and indicate future directions for a study of Stanley's question.     

Planarization and fragmentability of some classes of graphs

The coefficient of fragmentability of a class of graphs measures the proportion of vertices that need to be removed from the graphs in the class in order to leave behind bounded sized components. We have previously given bounds on this parameter for the class of graphs satisfying a given constant bound on maximum degree. In this paper, we give fragmentability bounds for some classes of graphs of bounded average degree, as well as classes of given thickness, the class of k-colourable graphs, and the class of n-dimensional cubes. In order to establish the fragmentability results for bounded average degree, we prove that the proportion of vertices that must be removed from a graph of average degree at most in order to leave behind a planar subgraph (in fact, a series-parallel subgraph) is at most , provided or the graph is connected and . The proof yields an algorithm for finding large induced planar subgraphs and (under certain conditions) a lower bound on the size of the induced planar subgraph it finds. This bound is similar in form to the one we found for a previous algorithm we developed for that problem, but applies to a larger class of graphs.     

Strongly Closed Subgraphs in a Distance-Regular Graph with <Emphasis Type="Italic">c</Emphasis><Subscript>2</Subscript> > 1

Let Γ be a distance-regular graph of diameter d ≥ 3 with c ₂ > 1. Let m be an integer with 1 ≤ m ≤ d − 1. We consider the following conditions:

A New Method for Enumerating Independent Sets of a Fixed Size in General Graphs

We develop a new method for enumerating independent sets of a fixed size in general graphs, and we use this method to show that a conjecture of Engbers and Galvin [7] holds for all but finitely many graphs. We also use our method to prove special cases of a conjecture of Kahn [13]. In addition, we show that our method is particularly useful for computing the number of independent sets of small sizes in general regular graphs and Moore graphs, and we argue that it can be used in many other cases when dealing with graphs that have numerous structural restrictions.     

应用分子子图指数估计与预测烷烃核磁共振碳谱位移和

系统地研究了核磁共振碳谱(¹³C NMR)与化学位移规律及其定量构谱关系(QSSR).本文研究了一组多元素分子子图指数矢量(VMSG),并发现它与烷烃化学位移和(CCSA)有很好线性相关性.采用多元线性回归(MVLR)进行准确估计与预测,结果良好.     

Crossing properties of graph reliability functions

Let G be a graph and p ϵ (0, 1). Let A(G, p) denote the probability that if each edge of G is selected at random with probability p then the resulting spanning subgraph of G is connected. Then A(G, p) is a polynomial in p. We prove that for every integer k ≥ 1 and every k‐tuple (m₁, m₂, … ,m_k) of positive integers there exist infinitely many pairs of graphs G₁ and G₂ of the same size such that the polynomial A(G₁, p) − A(G₂, p) has exactly k roots x₁ < x₂ < ··· < x_k in (0, 1) such that the multiplicity of x_i is m_i. We also prove the same result for the two‐terminal reliability polynomial, defined as the probability that the random subgraph as above includes a path connecting two specified vertices. These results are based on so‐called A‐ and T‐multiplying constructions that are interesting in themselves. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 206–221, 2000     

Lambda composition

A lambda in a graph G is two edges uv and vw such that uw is not an edge. A subgraph A of G is called a lambda-subgraph if every lambda of G has both or neither of its edges in A. We describe the decomposition of a graph into its lambda subgraphs and use this to prove a decomposition theorem of Gallai (Acta Math. Acad. Sci. Hungar. 18 (1967), 25–66). A corollary is that a graph is perfect if and only if each of its edge-minimal lambda subgraphs is. © 1997 John Wiley & Sons, Inc. J Graph Theory 26:9–16, 1997     

Connected subgraphs with small degree sums in 3‐connected planar graphs

It is well‐known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3‐connected planar graph has an edge xy such that deg(x) + deg (y) ≤ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we show that, for a given positive integer t, every 3‐connected planar graph G with |V(G)| ≥ t has a connected subgraph H of order t such that Σ_x∈V(H) deg_G(x) ≤ 8t − 1. As a tool for proving this result, we consider decompositions of 3‐connected planar graphs into connected subgraphs of order at least t and at most 2t − 1. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 191–203, 1999