On the L(2, 1)-labelling of block graphs

The distance-two labelling problem of graphs was proposed by Griggs and Roberts in 1988, and it is a variation of the frequency assignment problem introduced by Hale in 1980. An L(2, 1)-labelling of a graph G is an assignment of non-negative integers to the vertices of G such that vertices at distance two receive different numbers and adjacent vertices receive different and non-consecutive integers. The L(2, 1)-labelling number of G, denoted by λ(G), is the smallest integer k such that G has a L(2, 1)-labelling in which no label is greater than k.

In this work, we study the L(2, 1)-labelling problem on block graphs. We find upper bounds for λ(G) in the general case and reduce those bounds for some particular cases of block graphs with maximum clique size equal to 3.     

Flow in planar graphs with vertex capacities

Max-flow in planar graphs has always been studied with the assumption that there are capacities only on the edges. Here we consider a more general version of the problem when the vertices as well as edges have capacity constraints. In the context of general graphs considering only edge capacities is not restrictive, since the vertex-capacity problem can be reduced to the edge-capacity problem. However, in the case of planar graphs this reduction does not maintainplanarity and cannot be used. We study different versions of the planar flow problem (all of which have been extensively investigated in the context of edge capacities).A preliminary version of this paper appeared in theProceedings of the First Integer Programming and Combinatorial Optimization Conference, Waterloo, Canada, May 1990, pp. 367–383. Samir Khuller is currently supported by NSF Grant CCR-8906949. Part of this research was done while he was visiting the IBM Thomas J. Watson Research Center and was supported by an IBM Graduate Fellowship at Cornell University. Joseph Naor's work was supported by Contract ONR N00014-88-K-0166 while he was a post-doctoral fellow in the Department of Computer Science at Stanford University.     

随机图的点可区别V-全染色算法

图[G]的点可区别V-全染色就是相邻的边、顶点与其关联边必须染不同的颜色,同时要求所有顶点的色集合也不相同,所用的最少颜色数称为图[G]的点可区别V-全色数。根据点可区别V-全染色的约束规则,设计了一种启发式的点可区别V-全染色算法,该算法借助染色矩阵及色补集合逐步迭代交换,每次迭代交换后判断目标函数值,当目标函数值满足要求时染色成功。给出了算法的详细描述、算法分析和算法测试结果,对给定点数的图进行了点可区别V-全染色猜想的验证。实验结果表明,该算法有很好的执行效率并可以得到给定图的点可区别V-全色数,并且算法的时间复杂度不超过[O(n3)]。     

外1-平面图的均匀点荫度

图的均匀树[k]-染色是图的一个点[k]-染色,其任何两个色类的大小相差至多为1,并且每个色类的导出子图是一个森林。使得图[G]具有均匀树[k]-染色的最小整数[k]称为图[G]的均匀点荫度。证明了每个外1-平面图的均匀点荫度至多为3,继而对于外1-平面图证明了均匀点荫度猜想。     

Feedback vertex sets in star graphs

In a graph G=(V,E), a subset F⊂V(G) is a feedback vertex set of G if the subgraph induced by V(G)?F is acyclic. In this paper, we propose an algorithm for finding a small feedback vertex set of a star graph. Indeed, our algorithm can derive an upper bound to the size of the feedback vertex set for star graphs. Also by applying the properties of regular graphs, a lower bound can easily be achieved for star graphs.     

A probabilistic algorithm for vertex connectivity of graphs

A probabilistic algorithm is presented which computes the vertex connectivity of an undirected graph G = (V,E) in expected time $\text{O((-log ε|V|}{}^{\mathrm{<mtext>3</mtext><mtext>2</mtext>}}\text{|E|)}$ with error probability at most e provided that |E|<frcase|1/2d|V|² for some universal constant d<1.     

Honeycomb toroidal graphs are Cayley graphs

There is a particular family of trivalent vertex-transitive graphs that have been called generalized honeycomb tori by some and brick products by others. They have been studied as hexagonal embeddings on the torus as well. We show that all these graphs are Cayley graphs on generalized dihedral groups.     

随机图的点可区别全染色算法

点可区别全染色(VDTC)是指在满足正常全染色的基础上,还要使得图中由顶点颜色和其关联边颜色构成的顶点色集合也不同,所使用的最少颜色数称为点可区别全色数.提出了一种针对随机图的点可区别全染色算法,算法的基本思想是对图G中的边随机地进行预染色,查找存在边染色不正常的冲突集,然后根据规则逐步迭代,直至使目标函数的值满足要求,此时说明染色成功.实验结果表明,算法能够有效地求得给定点数随机图的点可区别全色数,算法时间复杂度不超过O(n3).     

A kind of conditional vertex connectivity of Cayley graphs generated by 2-trees

Let G be a graph. Then T ⊆ V(G) is called an R^k-vertex-cut if G − T is disconnected and each vertex in V(G) − T has at least k neighbors in G − T. The size of a smallest R^k-vertex-cut is the R^k-vertex-connectivity of G and is denoted by κ^k(G). In this paper, we determine the numbers κ¹ and κ² for Cayley graphs generated by 2-trees, including the popular alternating group graphs.     

Fault diameter of product graphs

The (k−1)-fault diameter Dk(G) of a k-connected graph G is the maximum diameter of an induced subgraph by deleting at most k−1 vertices from G. This paper considers the fault diameter of the product graph G₁∗G₂ of two graphs G₁ and G₂ and proves that Dk₁+k₂(G₁∗G₂)?Dk₁(G₁)+Dk₂(G₂)+1 if G₁ is k₁-connected and G₂ is k₂-connected. This generalizes some known results such as Bani? and ?erovnik [I. Bani?, J. ?erovnik, Fault-diameter of Cartesian graph bundles, Inform. Process. Lett. 100 (2) (2006) 47-51].     

Function-described graphs for modelling objects represented by sets of attributed graphs

We present in this article the model function-described graph (FDG), which is a type of compact representation of a set of attributed graphs (AGs) that borrow from random graphs the capability of probabilistic modelling of structural and attribute information. We define the FDGs, their features and two distance measures between AGs (unclassified patterns) and FDGs (models or classes) and we also explain an efficient matching algorithm. Two applications of FDGs are presented: in the former, FDGs are used for modelling and matching 3D-objects described by multiple views, whereas in the latter, they are used for representing and recognising human faces, described also by several views.     

PTAS for connected vertex cover in unit disk graphs

This paper gives the first polynomial time approximation scheme for the connected vertex cover problem in unit disk graphs.     

Oriented vertex and arc colorings of outerplanar graphs

A homomorphism from an oriented graph G to an oriented graph H is an arc-preserving mapping φ from V(G) to V(H), that is φ(x)φ(y) is an arc in H whenever xy is an arc in G. The oriented chromatic number of G is the minimum order of an oriented graph H such that G has a homomorphism to H. The oriented chromatic index of G is the minimum order of an oriented graph H such that the line-digraph of G has a homomorphism to H.In this paper, we determine for every k?3 the oriented chromatic number and the oriented chromatic index of the class of oriented outerplanar graphs with girth at least k.     

Reconstruction of interval graphs

The graph reconstruction conjecture is a long-standing open problem in graph theory. There are many algorithmic studies related to it, such as DECK CHECKING, LEGITIMATE DECK, PREIMAGE CONSTRUCTION, and PREIMAGE COUNTING. We study these algorithmic problems by limiting the graph class to interval graphs. Since we can solve GRAPH ISOMORPHISM for interval graphs in polynomial time, DECK CHECKING for interval graphs is easily done in polynomial time. Since the number of interval graphs that can be obtained from an interval graph by adding a vertex and edges incident to it can be exponentially large, developing polynomial time algorithms for LEGITIMATE DECK, PREIMAGE CONSTRUCTION, and PREIMAGE COUNTING on interval graphs is not trivial. We present that these three problems are solvable in polynomial time on interval graphs.     

Minimum weight feedback vertex sets in circle graphs

We describe a polynomial time algorithm to find a minimum weight feedback vertex set, or equivalently, a maximum weight induced forest, in a circle graph. The circle graphs are the overlap graphs of intervals on a line.     

On generalization/specialization for conceptual graphs

Abstract

This paper centres on the generalization/specialization relation in the framework of conceptual graphs (this relation corresponds to logical subsumption when considering logical formulas associated with conceptual graphs). Results given here apply more generally to any model where knowledge is described by labelled graphs and reasoning is based on graph subsumption, as in semantic networks or in structural machine learning. The generalization/specialization relation, as defined by Sowa, is first precisely analysed, in particular its links with a graph morphism, called projection. Besides Sowa's specialization relation (which is a preorder), another one is actually used in some practical applications (which is an order). These are comparatively studied. The second topic of this paper is the design of efficient algorithms for computing these specialization relations. Since the associated problems are NP-hard, the form of the graphs is restricted in order to arrive at polynomial algorithms. In particular, polynomial algorithms are presented for computing a projection from a conceptual ‘tree’ to any conceptual graph, and for counting the number of such projections. The algorithms are also described in a generic way, replacing the projection by a parametrized graph morphism, and conceptual graphs by directed labelled graphs.