A Characterization of the degree sequences of 2‐trees

A graph G is a 2‐tree if G = K₃, or G has a vertex v of degree 2, whose neighbors are adjacent, and G/ v is a 2‐ tree. A characterization of the degree sequences of 2‐trees is given. This characterization yields a linear‐time algorithm for recognizing and realizing degree sequences of 2‐trees. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:191‐209, 2008     

最小二乘法在地基土工参数获取中的应用

本文利用最小二乘的L-M方法建立了关于地基土工参数的优化计算模型,并基于MATLAB得出计算结果．从而证明利用最小二乘法可有效地获取土工参数．     

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.     

高阶双参量Runge-Kutta方法

构造了仅由两个参量确定的方法类RK,（μ,δ）,一切节点属于区间［0,1］且至少2s－1阶相容的s级RK的方法,如Radau|A,Radau||A,Gauss方法等,均是其特例．此类方法的代数稳定性与A-稳定性均等价于参量的μ的非负性,这一准则改进了Burrage的如下结论：一个满足简化条件B（s）和C（s）的s级RK的方法代数稳定的必要条件是它至少2s—1阶相容．基于此类方法构造了高阶指数拟合的RK公式,且公式是代数稳定的,因而适于求解非线性stiff问题．特别,当用k（k＞1）步方法求解stiff问题时,用拟会得当的RK公式确定k－1个附加初值是行之有效的．     

图的树宽的分解定理

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

图的树宽的结构性结果

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

两个完全图的乘积的树宽

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

Treewidth of Cartesian Products of Highly Connected Graphs

The following theorem is proved: for all k‐connected graphs G and H each with at least n vertices, the treewidth of the cartesian product of G and H is at least . For , this lower bound is asymptotically tight for particular graphs G and H. This theorem generalizes a well‐known result about the treewidth of planar grid graphs.     

k-树的补图的最小填充和树宽

一个图的最小填充问题是寻求边数最少的弦母图,一个图的树宽问题是寻求团数最小的弦母图,这两个问题分别在稀疏矩阵计算及图的算法设计中有非常重要的作用．一个k-树G的补图G称为k-补树．本文给出了k-补树G的最小填充数f(G) 及树宽TW(G)．     

Low Polynomial Exclusion of Planar Graph Patterns

The celebrated grid exclusion theorem states that for every h‐vertex planar graph H , there is a constant such that if a graph G does not contain H as a minor then G has treewidth at most . We are looking for patterns of H where this bound can become a low degree polynomial. We provide such bounds for the following parameterized graphs: the wheel , the double wheel , any graph of pathwidth at most 2 , and the yurt graph .     

Graph Treewidth and Geometric Thickness Parameters

Consider a drawing of a graph G in the plane such that crossing edges are coloured differently. The minimum number of colours, taken over all drawings of G, is the classical graph parameter thickness. By restricting the edges to be straight, we obtain the geometric thickness. By additionally restricting the vertices to be in convex position, we obtain the book thickness. This paper studies the relationship between these parameters and treewidth. Our first main result states that for graphs of treewidth k, the maximum thickness and the maximum geometric thickness both equal ⌈k/2⌉. This says that the lower bound for thickness can be matched by an upper bound, even in the more restrictive geometric setting. Our second main result states that for graphs of treewidth k, the maximum book thickness equals k if k ≤ 2 and equals k + 1 if k ≥ 3. This refutes a conjecture of Ganley and Heath [Discrete Appl. Math. 109(3):215-221, 2001]. Analogous results are proved for outerthickness, arboricity, and star-arboricity.     

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.     

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.     

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.     

Notes on growing a tree in a graph

We study the height of a spanning tree T of a graph G obtained by starting with a single vertex of G and repeatedly selecting, uniformly at random, an edge of G with exactly one endpoint in T and adding this edge to T.     

On giant components and treewidth in the layers model

Given an undirected n‐vertex graph G(V, E) and an integer k, let T_k(G) denote the random vertex induced subgraph of G generated by ordering V according to a random permutation π and including in T_k(G) those vertices with at most k – 1 of their neighbors preceding them in this order. The distribution of subgraphs sampled in this manner is called the layers model with parameter k. The layers model has found applications in studying ?‐degenerate subgraphs, the design of algorithms for the maximum independent set problem, and in bootstrap percolation. In the current work we expand the study of structural properties of the layers model. We prove that there are 3‐regular graphs G for which with high probability T₃(G) has a connected component of size , and moreover, T₃(G) has treewidth . In contrast, T₂(G) is known to be a forest (hence of treewidth 1), and we prove that if G is of bounded degree then with high probability the largest connected component in T₂(G) is of size . We also consider the infinite grid , for which we prove that contains a unique infinite connected component with probability 1. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 524–545, 2016     

Using equality in the Krein conditions to prove nonexistence of certain distance-regular graphs

We prove the nonexistence of a distance-regular graph with intersection array {74,54,15;1,9,60} and of distance-regular graphs with intersection arrays

{4r³+8r²+6r+1,2r(r+1)(2r+1),2r²+2r+1;1,2r(r+1),(2r+1)(2r²+2r+1)}