图的树宽的分解定理

图的树宽问题是名的ＮＰ－困难问题。其分解原则在确定树宽的一般算法和特殊算法中有重要应用。本给出这方面的若干定理。     

两个完全图的乘积的树宽

本文确定了乘积图Km×Kn的树宽.我们的结果是若m和n都是偶数,且m≥n,或m是奇数而n是偶数,或m和n都是奇数且n≥m,则Km×Kn的树宽是TW(Km×Kn)=n(m+1)/2-1.这恰好是图Km×Kn的带宽.     

Approximation of pathwidth of outerplanar graphs

There exists a polynomial time algorithm to compute the pathwidth of outerplanar graphs, but the large exponent makes this algorithm impractical. In this paper, we give an algorithm that, given a biconnected outerplanar graph G, finds a path decomposition of G of pathwidth at most twice the pathwidth of G plus one. To obtain the result, several relations between the pathwidth of a biconnected outerplanar graph and its dual are established.     

Graphs with Branchwidth at Most Three

In this paper we investigate both the structure of graphs with branchwidth at most three, as well as algorithms to recognise such graphs. We show that a graph has branchwidth at most three if and only if it has treewidth at most three and does not contain the three-dimensional binary cube graph as a minor. A set of four graphs is shown to be the obstruction set for the class of graphs with branchwidth at most three. Moreover, we give a safe and complete set of reduction rules for the graphs with branchwidth at most three. Using this set, a linear time algorithm is given that verifies if a given graph has branchwidth at most three, and, if so, outputs a minimum width branch decomposition.     

图的树宽的结构性结果

图G的树宽是使得G成为一个k-树的子图的最小整数k．树宽的算法性结果在图子式理论及有关领域中已有深入的研究．本文着重讨论其结构性结果，包括拓扑不变性、子式单调性、可分解性、刻画问题、与其它参数的关系及由此引伸出的性质．     

Separator theorems and Turán-type results for planar intersection graphs

We establish several geometric extensions of the Lipton-Tarjan separator theorem for planar graphs. For instance, we show that any collection C of Jordan curves in the plane with a total of m crossings has a partition into three parts C=S∪C₁∪C₂ such that , , and no element of C₁ has a point in common with any element of C₂. These results are used to obtain various properties of intersection patterns of geometric objects in the plane. In particular, we prove that if a graph G can be obtained as the intersection graph of n convex sets in the plane and it contains no complete bipartite graph Kt,t as a subgraph, then the number of edges of G cannot exceed ctn, for a suitable constant ct.     

The most vital nodes with respect to independent set and vertex cover

Given an undirected graph with weights on its vertices, the k most vital nodes independent set (k most vital nodes vertex cover) problem consists of determining a set of k vertices whose removal results in the greatest decrease in the maximum weight of independent sets (minimum weight of vertex covers, respectively). We also consider the complementary problems, minimum node blocker independent set (minimum node blocker vertex cover) that consists of removing a subset of vertices of minimum size such that the maximum weight of independent sets (minimum weight of vertex covers, respectively) in the remaining graph is at most a specified value. We show that these problems are NP-hard on bipartite graphs but polynomial-time solvable on unweighted bipartite graphs. Furthermore, these problems are polynomial also on cographs and graphs of bounded treewidth. Results on the non-existence of ptas are presented, too.     

A new estimate for the vertex number of an edge-regular graph

Given a connected edge-regular graph Γ with parameters (v, k, λ) and b ₁ = k ? λ ? 1, we prove that in the case k ≥ 3b ₁ ?2 either |Γ₂(u)|(k?2b ₁ + 2) < kb ₁ for every vertex u or Γ is a polygon, the edge graph of a trivalent graph without triangles that has diameter greater than 2, the icosahedral graph, the complete multipartite graph K _r×2, the 3 × 3-grid, the triangular graph T(m) with m ≤ 7, the Clebsch graph, or the Schläfli graph.     

ContributionsAn algorithm for the Tutte polynomials of graphs of bounded treewidth

Let k be a fixed, positive integer. We give an algorithm which computes the Tutte polynomial of any graph G of treewidth at most k in time O(n^{2+7 log₂ c}), where c is twice the number of partitions of a set with 3k + 3 elements and n the number of vertices of G.     

A bound on the treewidth of planar even-hole-free graphs

The class of planar graphs has unbounded treewidth, since the k×k grid, ∀k∈N, is planar and has treewidth k. So, it is of interest to determine subclasses of planar graphs which have bounded treewidth. In this paper, we show that if G is an even-hole-free planar graph, then it does not contain a 9×9 grid minor. As a result, we have that even-hole-free planar graphs have treewidth at most 49.     

Distance-Regular Graph with <Emphasis Type="Italic">c</Emphasis><Subscript>2</Subscript> > 1 and <Emphasis Type="Italic">a</Emphasis><Subscript>1</Subscript> = 0 < <Emphasis Type="Italic">a</Emphasis><Subscript>2</Subscript>

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: