Minimum Self-Repairing Graphs

A graph is self-repairing if it is 2-connected and such that the removal of any single vertex results in no increase in distance between any pair of remaining vertices of the graph. We completely characterize the class of minimum self-repairing graphs, which have the fewest edges for a given number of vertices.     

Constraint-Based Representations of Statistical Graphs

Abstract

Pictor is an environment for statistical graphics that promotes simple commands for common uses and offers the ability to experiment with whole new paradigms. Pictor describes graphs as graphical objects whose component pieces are related by several sorts of constraints. This article describes in detail the constraint system that Pictor uses.     

图的最小完整度

主要研究了图的完整度,并给出若干关于完整度的结果. 对于所有的顶点数和边数都给定的连通图类,如何确定该图类中完整度最小的图. 同时研究了对于顶点数和完整度都给定的连通图类,如何确定该图类中边数最多的图的问题. 这些结果为图的最小完整度的优化设计提供了理论和方法.     

Minimum Size of n-Factor-Critical Graphs and k-Extendable Graphs

We determine the minimum size of n-factor-critical graphs and that of k-extendable bipartite graphs, by considering Harary graphs and related graphs. Moreover, we determine the minimum size of k-extendable non-bipartite graphs for k = 1, 2, and pose a related conjecture for general k.     

Planar Graphs Have 1-string Representations

We prove that every planar graph is an intersection graph of strings in the plane such that any two strings intersect at most once.     

Minimum Paths in Directed Graphs

This paper considers the problem of finding paths from a fixed node to all other nodes of a directed graph which minimise a function defined on the paths. Under certain assumptions a characterisation of optimal paths is derived. Two algorithms which are generalisations of standard shortest path methods are then given.     

Sphere and Dot Product Representations of Graphs

A graph G is a k-sphere graph if there are k-dimensional real vectors v ₁,…,v _n such that ij∈E(G) if and only if the distance between v _i and v _j is at most 1. A graph G is a k-dot product graph if there are k-dimensional real vectors v ₁,…,v _n such that ij∈E(G) if and only if the dot product of v _i and v _j is at least 1.     

Minimum Clique-Free Subgraphs of Kneser Graphs

Doklady Mathematics - The saturation and weak saturation numbers of Kneser graphs with clique patterns are estimated.     

Minimum Color Sum of Bipartite Graphs

The problem ofminimum color sumof a graph is to color the vertices of the graph such that the sum (average) of all assigned colors is minimum. Recently it was shown that in general graphs this problem cannot be approximated withinn^{1 − ε}, for any ε > 0, unlessNP = ZPP(Bar-Noyet al., Information and Computation140(1998), 183–202). In the same paper, a 9/8-approximation algorithm was presented for bipartite graphs. The hardness question for this problem on bipartite graphs was left open. In this paper we show that the minimum color sum problem for bipartite graphs admits no polynomial approximation scheme, unlessP = NP. The proof is byL-reducing the problem of finding the maximum independent set in a graph whose maximum degree is four to this problem. This result indicates clearly that the minimum color sum problem is much harder than the traditional coloring problem, which is trivially solvable in bipartite graphs. As for the approximation ratio, we make a further step toward finding the precise threshold. We present a polynomial 10/9-approximation algorithm. Our algorithm uses a flow procedure in addition to the maximum independent set procedure used in previous solutions.     

序列平行图的最小填充

起源于稀疏矩阵计算和其它应用领域的一个图G的最小填充问题就是在G中寻找一个边数| F |最小的添加边集F,使得G+F是弦图.这里最小值| F |称为图G的填充数,表示为f(G).对一般图来说,这个问题是NP-困难问题.一些特殊图类的最小填充问题已被研究.本文给出了序列平行图G的最小填充数的具体值.     

局部大边宽嵌入图的最小圈基

利用Thomassen等人在大边宽嵌入方面的工作,给出局部大边宽嵌入的定义,并运用线性代数和相异代表系的知识,证明了局部大边宽嵌入图的最小圈基.     

Domination in Graphs of Minimum Degree Five

Let G=(V,E) be a simple graph. A subset D⊆V is a dominating set of G, if for any vertex x ∈ V−D, there exists a vertex y ∈ D such that xy ∈ E. By using the so-called vertex disjoint paths cover introduced by Reed, in this paper we prove that every graph G on n vertices with minimum degree at least five has a dominating set of order at most 5n/14.     

Uniquely Hamiltonian Graphs of Minimum Degree 4

We construct an infinite family of uniquely hamiltonian graphs of minimum degree 4, maximum degree 14, and of arbitrarily high maximum degree.     

Damping in Un-Damped Finite Difference Representations

It is shown that interpreting the von Neumann-Fourier stabilityanalysis in terms of a dispersion relation yeilds insight intothe propogation of information input at the boundary in linearfinite difference schemes. As an example it is shown that themethod explains the damping of a high frequency input in theLeap-frog representation of the shallow-water wave equations.     

Corrigendum: Minimum Paths in Directed Graphs

Journal of the Operational Research Society -     

Minimum Clique Partition in Unit Disk Graphs

The minimum clique partition (MCP) problem is that of partitioning the vertex set of a given graph into a minimum number of cliques. Given n points in the plane, the corresponding unit disk graph (UDG) has these points as vertices, and edges connecting points at distance at most 1. MCP in UDGs is known to be NP-hard and several constant factor approximations are known, including a recent PTAS. We present two improved approximation algorithms for MCP in UDGs with a realization: (I) A polynomial time approximation scheme (PTAS) running in time n^O(1/e2){n^{O(1/\varepsilon^2)}}. This improves on a previous PTAS with n^O(1/e4){n^{O(1/\varepsilon^4)}} running time by Pirwani and Salavatipour (arXiv:0904.2203v1, 2009). (II) A randomized quadratic-time algorithm with approximation ratio 2.16. This improves on a ratio 3 algorithm with O(n ²) running time by Cerioli et al. (Electron. Notes Discret. Math. 18:73–79, 2004).     

Minimum Fill-in on Circle and Circular-Arc Graphs

We present two algorithms solving the minimum fill-in problem on circle graphs and on circular-arc graphs in timeO(n³).     

弦图的补图的最小填充

从图论观点讲,最小填充问题就是在一个图G中添加边集F,使得图G的母图G F是一个弦图而且所添边的边数| F|是最小的,其中最小值| F|称为图G的填充数,表示为f( G) .对一般图来说,最小填充问题是NP-困难的,但是对一些特殊图类来说,这个问题是在多项式时间内可解的.本文给出了弦图的补图-G的填充数f(-G) .     

Minimum Power Dominating Sets of Random Cubic Graphs

We present two heuristics for finding a small power dominating set of cubic graphs. We analyze the performance of these heuristics on random cubic graphs using differential equations. In this way, we prove that the proportion of vertices in a minimum power dominating set of a random cubic graph is asymptotically almost surely at most 0.067801. We also provide a corresponding lower bound of using known results on bisection width.