Application of computer algebra to Jones polynomials

In this paper we apply computer algebra (Maple) techniques to calculate Jones polynomial of graphs of K(2,q)-Torus knots. For this purpose, a computer program was developed. When a positive integer q is given, the program calculate Jones polynomial of graph of K(2,q)-Torus knots.     

On the Maximum Number of Cliques in a Graph

A clique is a set of pairwise adjacent vertices in a graph. We determine the maximum number of cliques in a graph for the following graph classes: (1) graphs with n vertices and m edges; (2) graphs with n vertices, m edges, and maximum degree Δ; (3) d-degenerate graphs with n vertices and m edges; (4) planar graphs with n vertices and m edges; and (5) graphs with n vertices and no K₅-minor or no K_3,3-minor. For example, the maximum number of cliques in a planar graph with n vertices is 8(n − 2). Research supported by a Marie Curie Fellowship of the European Community under contract 023865, and by the projects MCYT-FEDER BFM2003-00368 and Gen. Cat 2001SGR00224.     

轮图的广义Mycielski图的邻强边色数

设图 G(V,E)为简单图 ,V(Mn(G) ) |{ v0 1,v0 2 ,… ,v0 p;v11,v12 ,… ,v1p,… ,vn1,vn2 ,… ,vnp}E(Mn(G) ) =E(G)∪ { vijv(i+ 1) k|v0 jv0 k ∈ E(G) ,1≤ j,k≤ p ,i =0 ,1,… ,n - 1}称 Mn(G)为 G的 n广义 Mycielski图 ,n为自然数 .本文得到了轮的广义 Mycielski图的临强边色数 .     

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.