全变换图的基本性质

我们引入了四对变换图,其中有一对是全图和它的补图。我们研究这些变换图的基本性质。     

Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs

We study a variation of the vertex cover problem where it is required that the graph induced by the vertex cover is connected. We prove that this problem is polynomial in chordal graphs, has a PTAS in planar graphs, is APX-hard in bipartite graphs and is 5/3-approximable in any class of graphs where the vertex cover problem is polynomial (in particular in bipartite graphs). Finally, dealing with hypergraphs, we study the complexity and the approximability of two natural generalizations.     

Partitioning Perfect Graphs into Stars

The partition of graphs into “nice” subgraphs is a central algorithmic problem with strong ties to matching theory. We study the partitioning of undirected graphs into same‐size stars, a problem known to be NP‐complete even for the case of stars on three vertices. We perform a thorough computational complexity study of the problem on subclasses of perfect graphs and identify several polynomial‐time solvable cases, for example, on interval graphs and bipartite permutation graphs, and also NP‐complete cases, for example, on grid graphs and chordal graphs.     

新的Q整图类K_n~(-tk2)

在他人研究整图,Laplace整图和Seidel-整图的基础上,刻画了Q整图新类.对图类K-tk2n的无符号拉普拉斯特征多项式进行研究分析,应用矩阵的初等变换,给出了图类K-tk2n是Q整图的充分必要条件,得到了新的Q整图类K-tk2n及其Q谱.     

Graphs with the maximum or minimum number of 1-factors

Recently Alon and Friedland have shown that graphs which are the union of complete regular bipartite graphs have the maximum number of 1-factors over all graphs with the same degree sequence. We identify two families of graphs that have the maximum number of 1-factors over all graphs with the same number of vertices and edges: the almost regular graphs which are unions of complete regular bipartite graphs, and complete graphs with a matching removed. The first family is determined using the Alon and Friedland bound. For the second family, we show that a graph transformation which is known to increase network reliability also increases the number of 1-factors. In fact, more is true: this graph transformation increases the number of k-factors for all k≥1, and “in reverse” also shows that in general, threshold graphs have the fewest k-factors. We are then able to determine precisely which threshold graphs have the fewest 1-factors. We conjecture that the same graphs have the fewest k-factors for all k≥2 as well.     

Covering partially directed graphs with directed paths

We consider graphs which contain both directed and undirected edges (partially directed graphs). We show that the problem of covering the edges of such graphs with a minimum number of edge-disjoint directed paths respecting the orientations of the directed edges is polynomially solvable. We exhibit a good characterization for this problem in the form of a min-max theorem. We introduce a more general problem including weights on possible orientations of the undirected edges. We show that this more general weighted formulation is equivalent to the weighted bipartite b-factor problem. This implies the existence of a strongly polynomial algorithm for this weighted generalization of Euler's problem to partially directed graphs (compare this with the negative results for the mixed Chinese postman problem). We also provide a compact linear programming formulation for the weighted generalization that we propose.     

两类广义控制问题的NP-完全性

研究两类广义控制问题的复杂性: k-步长控制问题和k-距离控制问题, 证明了k-步长控制问题在弦图和平面二部图上都是NP-完全的. 作为上述结果的推论, 给出了k-距离控制问题在弦图和二部图上NP-完全性的新的证明, 并进一步证明了k-距离控制问题在平面二部图上也是NP-完全的.     

Feasibility of motion planning on acyclic and strongly connected directed graphs

Motion planning is a fundamental problem of robotics with applications in many areas of computer science and beyond. Its restriction to graphs has been investigated in the literature, for it allows one to concentrate on the combinatorial problem abstracting from geometric considerations. In this paper, we consider motion planning over directed graphs, which are of interest for asymmetric communication networks. Directed graphs generalize undirected graphs, while introducing a new source of complexity to the motion planning problem: moves are not reversible. We first consider the class of acyclic directed graphs and show that the feasibility can be solved in time linear in the product of the number of vertices and the number of arcs. We then turn to strongly connected directed graphs. We first prove a structural theorem for decomposing strongly connected directed graphs into strongly biconnected components. Based on the structural decomposition, we show that the feasibility of motion planning on strongly connected directed graphs can be decided in linear time.     

Online Bounded Coloring of Permutation and Overlap Graphs

We consider a track assignment problem in a train depot leading to an online bounded coloring problem on permutation graphs or on overlap graphs. For permutation graphs we study the competitiveness of a First Fit-based algorithm and we show it matches the competitive ratio of the problem. For overlap graphs, even the unbounded case does not admit a constant competitive ratio.     

Chromatic properties of hamiltonian graphs

We study the problem of the location of real zeros of chromatic polynomials for some families of graphs. In particular, a problem presented by Thomassen (see [On the number of hamiltonian cycles in bipartite graphs, Combin. Probab. Comput. 5 (1996) 437–442.]) is discussed and a result for hamiltonian graphs is presented. An open problem is stated for 2-connected graphs with a hamiltonian path.     

Hereditary Efficiently Dominatable Graphs

An efficient dominating set (or perfect code) in a graph is a set of vertices the closed neighborhoods of which partition the graph's vertex set. We introduce graphs that are hereditary efficiently dominatable in that sense that every induced subgraph of the graph contains an efficient dominating set. We prove a decomposition theorem for (bull, fork, C₄)‐free graphs, based on which we characterize, in terms of forbidden induced subgraphs, the class of hereditary efficiently dominatable graphs. We also give a decomposition theorem for hereditary efficiently dominatable graphs and examine some algorithmic aspects of such graphs. In particular, we give a polynomial time algorithm for finding an efficient dominating set (if one exists) in a class of graphs properly containing the class of hereditary efficiently dominatable graphs by reducing the problem to the maximum weight independent set problem in claw‐free graphs.     

Maximum induced matching problem on hhd-free graphs

We show that the maximum induced matching problem can be solved on hhd-free graphs in O(m²) time; hhd-free graphs generalize chordal graphs and the previous best bound was O(m³). Then, we consider a technique used by Brandstädt and Hoàng (2008) [4] to solve the problem on chordal graphs. Extending this, we show that for a subclass of hhd-free graphs that is more general than chordal graphs the problem can be solved in linear time. We also present examples to demonstrate the tightness of our results.     

The vertex isoperimetric problem for the powers of the diamond graph

We introduce a new graph for all whose cartesian powers the vertex isoperimetric problem has nested solutions. This is the fourth kind of graphs with this property besides the well-studied graphs like hypercubes, grids, and tori. In contrast to the mentioned graphs, our graph is not bipartite. We present an exact solution to the vertex isoperimetric problem on our graph by introducing a new class of orders that unifies all known isoperimetric orders defined on the cartesian powers of graphs.     

The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs

This paper deals with the isomorphism problem of directed path graphs and rooted directed path graphs. Both graph classes belong to the class of chordal graphs, and for both classes the relative complexity of the isomorphism problem is yet unknown. We prove that deciding isomorphism of directed path graphs is isomorphism complete, whereas for rooted directed path graphs we present a polynomial-time isomorphism algorithm.     

On the determination of the sound field in a layer : PMM vol. 38, n 6, 1974, pp. 1129–1132

We consider a method for determining the sound field in a two-dimensional layer. The method we present combines the usual method of reflected plane waves with a summation from graphs. It makes it comparatively easy to take into account the complex interference pattern due to the transformation of the various waves at the boundaries of the layer and to obtain integral relations for the sound potentials. When the layer thickness tends to infinity, the problem reduces to one concerning the reflection of sound waves at the interface of two media. We study the potentials of normal waves in the case of a harmonic source in a solid.     

The complexity of dissociation set problems in graphs

A subset of vertices in a graph is called a dissociation set if it induces a subgraph with a vertex degree of at most 1. The maximum dissociation set problem, i.e., the problem of finding a dissociation set of maximum size in a given graph is known to be NP-hard for bipartite graphs. We show that the maximum dissociation set problem is NP-hard for planar line graphs of planar bipartite graphs. In addition, we describe several polynomially solvable cases for the problem under consideration. One of them deals with the subclass of the so-called chair-free graphs. Furthermore, the related problem of finding a maximal (by inclusion) dissociation set of minimum size in a given graph is studied, and NP-hardness results for this problem, namely for weakly chordal and bipartite graphs, are derived. Finally, we provide inapproximability results for the dissociation set problems mentioned above.     

Computing inertia sets using atoms

We consider the problem of computing inertia sets for graphs. By using tools for combining the inertia sets of smaller graphs we can reduce this problem to understanding the inertia sets for three-connected graphs that are not joins. We term such graphs atoms and give the inertia sets for all atoms on at most seven vertices. This can be used to compute the inertia sets for all graphs on at most seven vertices.     

无向路图和块图上的混合控制

图G=(V,E)的一个混合控制集是一个满足如下条件的集合DV∪E:不在D中的每个点或每条边都相邻或关联于D中的至少一个点或一条边.确定图的最小基数的混合控制集的问题称为混合控制问题.本文研究混合控制问题的算法复杂性,证明了混合控制问题在无向路图上是NP-完全的,但在块图上有线性时间算法.无向路图和块图都是弦图的子类,又是树的母类.     

Proper interval graphs and the guard problem

This paper is a study of the hamiltonicity of proper interval graphs with applications to the guard problem in spiral polygons. We prove that proper interval graphs with 2 vertices have hamiltonian paths, those with 3 vertices have hamiltonian cycles, and those with 4 vertices are hamiltonian-connected if and only if they are, respectively, 1-, 2-, or 3-connected. We also study the guard problem in spiral polygons by connecting the class of nontrivial connected proper interval graphs with the class of stick-intersection graphs of spiral polygons.     

Approximating the minimum clique cover and other hard problems in subtree filament graphs

Subtree filament graphs are the intersection graphs of subtree filaments in a tree. This class of graphs contains subtree overlap graphs, interval filament graphs, chordal graphs, circle graphs, circular-arc graphs, cocomparability graphs, and polygon-circle graphs. In this paper we show that, for circle graphs, the clique cover problem is NP-complete and the h-clique cover problem for fixed h is solvable in polynomial time. We then present a general scheme for developing approximation algorithms for subtree filament graphs, and give approximation algorithms developed from the scheme for the following problems which are NP-complete on circle graphs and therefore on subtree filament graphs: clique cover, vertex colouring, maximum k-colourable subgraph, and maximum h-coverable subgraph.