On the evaluation at (<Emphasis Type="Italic">j</Emphasis>, <Emphasis Type="Italic">j</Emphasis><Superscript>2</Superscript>) of the Tutte polynomial of a ternary matroid

F. Jaeger has shown that up to a ± sign the evaluation at (j, j ²) of the Tutte polynomial of a ternary matroid can be expressed in terms of the dimension of the bicycle space of a representation over GF(3). We give a short algebraic proof of this result, which moreover yields the exact value of ±, a problem left open in Jaeger's paper. It follows that the computation of t(j, j ²) is of polynomial complexity for a ternary matroid.E. Gioan: C.N.R.S., MontpellierM. Las Vergnas: C.N.R.S., Paris     

树上秘密共享体制的信息率

研究以树G为通道结构的秘密共享体制的最优信息率ρ（G）。得到了ρ（G）＝2／3的要条件。证明了ρ（G）不会介于实数区间（3／5，2／3）中，给出了以树G的阶数表示的ρ（G）的下界，求出两类具有某种结构的树的最优信息率。     

On Vertex Connectivity and Absolute Algebraic Connectivity for Graphs

Let G be a graph on n vertices with vertex connectivity v with 1 ≤ v ≤ n -2. We produce an attainable upper bound on the absolute algebraic connectivity of G in terms of n and v .     

Graph drawings with few slopes

The slope-number of a graph G is the minimum number of distinct edge slopes in a straight-line drawing of G in the plane. We prove that for Δ5 and all large n, there is a Δ-regular n-vertex graph with slope-number at least . This is the best known lower bound on the slope-number of a graph with bounded degree. We prove upper and lower bounds on the slope-number of complete bipartite graphs. We prove a general upper bound on the slope-number of an arbitrary graph in terms of its bandwidth. It follows that the slope-number of interval graphs, cocomparability graphs, and AT-free graphs is at most a function of the maximum degree. We prove that graphs of bounded degree and bounded treewidth have slope-number at most . Finally we prove that every graph has a drawing with one bend per edge, in which the number of slopes is at most one more than the maximum degree. In a companion paper, planar drawings of graphs with few slopes are also considered.     

An algorithm for calculating the independence and vertex-cover polynomials of a graph

The independence polynomial, ω(G,x)=∑w_kx^k, of a graph, G, has coefficients, w_k, that enumerate the ways of selecting k vertices from G so that no two selected vertices share an edge. The independence number of G is the largest value of k for which w_k≠0. Little is known of less straightforward relationships between graph structure and the properties of ω(G,x), in part because of the difficulty of calculating values of w_k for specific graphs. This study presents a new algorithm for these calculations which is both faster than existing ones and easily adaptable to high-level computer languages.     

An Ore-type analogue of the Sauer-Spencer Theorem

Two graphs G₁ and G₂ of order n pack if there exist injective mappings of their vertex sets into [n], such that the images of the edge sets do not intersect. Sauer and Spencer proved that if Δ (G₁) Δ (G₂) < 0.5n, then G₁ and G₂ pack. In this note, we study an Ore-type analogue of the Sauer–Spencer Theorem. Let θ(G) = max{d(u) + d(v): uv∈E(G)}. We show that if θ(G₁)Δ(G₂) < n, then G₁ and G₂ pack. We also characterize the pairs (G₁,G₂) of n-vertex graphs satisfying θ(G₁)Δ(G₂) = n that do not pack. This work was supported in part by NSF grant DMS-0400498. The work of the first author was also partly supported by grant 05-01-00816 of the Russian Foundation for Basic Research.     

Families of Dot-Product Snarks on Orientable Surfaces of Low Genus

We introduce a generalized dot product and provide some embedding conditions under which the genus of a graph does not rise under a dot product with the Petersen graph. Using these conditions, we disprove a conjecture of Tinsley and Watkins on the genus of dot products of the Petersen graph and show that both Grünbaum’s Conjecture and the Berge-Fulkerson Conjecture hold for certain infinite families of snarks. Additionally, we determine the orientable genus of four known snarks and two known snark families, construct a new example of an infinite family of snarks on the torus, and construct ten new examples of infinite families of snarks on the 2-holed torus; these last constructions allow us to show that there are genus-2 snarks of every even order n ≥ 18.     

Splittings of generalized Baumslag–Solitar groups

We study the structure of generalized Baumslag–Solitar groups from the point of view of their (usually non-unique) splittings as fundamental groups of graphs of infinite cyclic groups. We find and characterize certain decompositions of smallest complexity (fully reduced decompositions) and give a simplified proof of the existence of deformations. We also prove a finiteness theorem and solve the isomorphism problem for generalized Baumslag–Solitar groups with no non-trivial integral moduli.      

连通的顶点可迁图的色唯一性

本文给出从一个已知的顶点可迁的非色唯一图出发,构造无穷多个顶点可迁的非色唯一图的一种方法,据此给出若干类无穷多个连通的顶点可迁,但不是色唯一的图簇,从而进一步否定地回答了Chia在[1]中提出的问题.