共查询到20条相似文献,搜索用时 0 毫秒
1.
《国际计算机数学杂志》2012,89(3):468-475
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. 相似文献
2.
3.
Qiaoping Guo Shengjia Li Gaokui Xu Yubao Guo 《Information Processing Letters》2013,113(19-21):710-713
4.
5.
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. 相似文献
6.
图[G]的点可区别V-全染色就是相邻的边、顶点与其关联边必须染不同的颜色,同时要求所有顶点的色集合也不相同,所用的最少颜色数称为图[G]的点可区别V-全色数。根据点可区别V-全染色的约束规则,设计了一种启发式的点可区别V-全染色算法,该算法借助染色矩阵及色补集合逐步迭代交换,每次迭代交换后判断目标函数值,当目标函数值满足要求时染色成功。给出了算法的详细描述、算法分析和算法测试结果,对给定点数的图进行了点可区别V-全染色猜想的验证。实验结果表明,该算法有很好的执行效率并可以得到给定图的点可区别V-全色数,并且算法的时间复杂度不超过[O(n3)]。 相似文献
7.
图的均匀树[k]-染色是图的一个点[k]-染色,其任何两个色类的大小相差至多为1,并且每个色类的导出子图是一个森林。使得图[G]具有均匀树[k]-染色的最小整数[k]称为图[G]的均匀点荫度。证明了每个外1-平面图的均匀点荫度至多为3,继而对于外1-平面图证明了均匀点荫度猜想。 相似文献
8.
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. 相似文献
9.
M. Becker W. Degenhardt J. Doenhardt S. Hertel G. Kaninke W. Keber K. Mehlhorn S. Näher H. Rohnert T. Winter 《Information Processing Letters》1982,15(3):135-136
A probabilistic algorithm is presented which computes the vertex connectivity of an undirected graph G = (V,E) in expected time with error probability at most e provided that |E|<frcase|1/2d|V|2 for some universal constant d<1. 相似文献
10.
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. 相似文献
11.
12.
Let G be a graph. Then T ⊆ V(G) is called an Rk-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 Rk-vertex-cut is the Rk-vertex-connectivity of G and is denoted by κk(G). In this paper, we determine the numbers κ1 and κ2 for Cayley graphs generated by 2-trees, including the popular alternating group graphs. 相似文献
13.
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 G1∗G2 of two graphs G1 and G2 and proves that Dk1+k2(G1∗G2)?Dk1(G1)+Dk2(G2)+1 if G1 is k1-connected and G2 is k2-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]. 相似文献
14.
15.
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. 相似文献
16.
This paper gives the first polynomial time approximation scheme for the connected vertex cover problem in unit disk graphs. 相似文献
17.
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. 相似文献
18.
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. 相似文献
19.
Fanica Gavril 《Information Processing Letters》2008,107(1):1-6
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. 相似文献
20.
M. L. MUGNIER 《人工智能实验与理论杂志》2013,25(3):325-344
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. 相似文献