几类特殊有向循环图的核
|
摘要
有向图D=(V,A)的核K是顶点集V的一个子集,其中K中任意两点在D中均不相邻,并且对V\K中任意一个点v,都存在K中的一个点u,使得(v,u)是D中的一条弧.一般有向图核的存在问题是NP-完全的.Bang-Jensen和Gutin在他们的著作[Digraphs:Theory, Algorithms and Applications, London:Springer-Verlag, 2000]中提出公开问题(Problem 12.3.5):刻画有向循环图核存在性.本文研究了几类特殊有向循环图核的存在问题,并给出了Duchet核猜想(对任意一个不是有向奇圈的无核有向图,都存在一条弧,使得删除这条弧所得到的图仍然是无核的)的一类反例.
A kernel in a directed graph D =(V, A) is a set K of vertices of D such that no two vertices in K are adjacent and for every vertex v in V\K there is a vertex u in K, such that(v, u) is an arc of D. It is well known that the problem of existence of a kernel is NP-complete for a general digraph. Bang-Jensen and Gutin posed an interesting problem(Problem 12.3.5) in their book [Digraphs: Theory, Algorithms and Applications, London: Springer-Verlag, 2000]: to characterize all circular digraphs with kernels. In this paper, we study the problem of existence of the kernel for several special classes of circular digraphs. Moreover, a class of counterexamples is given for the Duchet kernel conjecture(for every connected kernel-less digraph which is not an odd directed cycle, there exists an arc which can be removed and the obtained digraph is still kernel-less).
A kernel in a directed graph D =(V, A) is a set K of vertices of D such that no two vertices in K are adjacent and for every vertex v in V\K there is a vertex u in K, such that(v, u) is an arc of D. It is well known that the problem of existence of a kernel is NP-complete for a general digraph. Bang-Jensen and Gutin posed an interesting problem(Problem 12.3.5) in their book [Digraphs: Theory, Algorithms and Applications, London: Springer-Verlag, 2000]: to characterize all circular digraphs with kernels. In this paper, we study the problem of existence of the kernel for several special classes of circular digraphs. Moreover, a class of counterexamples is given for the Duchet kernel conjecture(for every connected kernel-less digraph which is not an odd directed cycle, there exists an arc which can be removed and the obtained digraph is still kernel-less).
引文
[1]Apartsin, A., Ferapontova, E. and Gurvich, V., A circular graph-counterexample to the Duchet kernel conjecture, Discrete Math., 1998, 178(1/2/3):229-231.
[2]Bang-Jensen, J. and Gutin, G., Digraphs:Theory, Algorithms and Applications, London:Springer-Verlag,2000.
[3]Berge, C., Graphs, Volume 6, Amsterdam:North Holland Publishing Co., 1985.
[4]Berge, C. and Duchet, P., Recent problems and results about kernels in directed graphs, Discrete Math.,1990, 86(1/2/3):27-31.
[5]Boros, E. and Gurvich, V., A corrected version of the Duchet kernel conjecture, Discrete Math., 1998,179(1/2/3):231-233.
[6]Chvatal, V., On the computational complexity of finding a kernel, Report NO. CRM-300, Centre de Recherches Mathematiques, Montreal:Universite de Montreal, 1973.
[7]Duchet, P., Graphes noyau-parfaits, Ann. Discrete Math., 1980, 9:93-101(in French).
[8]Fraenkel, A., Planar kernel and Grundy with d≤3, d_(out)≤2, d_(in)≤2 are NP-complete, Discrete Appl.Math., 1981, 3(4):257-262.
[9]Kwasnik, M., The generalization of Richardson theorem, Discuss. Math., 1981,4:11-14.
[10]Manuel, P., Rajasingh, I., Rajan, B. and Punitha, J., Kernel in oriented circulant graphs, In:Combinatorial Algorithms, Lecture Notes in Comput. Sci., Vol. 5874, Berlin:Springer-Verlag, 2009, 396-407.
[11]Richardson, M., Solutions of irreflexive relations, Ann. of Math.(2), 1953, 58:573-590.
[12]Szwarcfiter, J. and Chaty, G., Enumerating the kernels of a directed graph with no odd circuits, Inform.Process. Lett., 1994, 51(3):149-153.
[13]Van Leeuwen, J., Having a Grundy-numbering is NP-complete, Report No. 207, Computer Science Dept.,University Park, PA:Pennsylvania State University, 1976.
[14]Von Neumann, J. and Morgenstern, O., Theory of Games and Economic Behaviour, Princeton:Princeton Univ. Press, 1994.
[2]Bang-Jensen, J. and Gutin, G., Digraphs:Theory, Algorithms and Applications, London:Springer-Verlag,2000.
[3]Berge, C., Graphs, Volume 6, Amsterdam:North Holland Publishing Co., 1985.
[4]Berge, C. and Duchet, P., Recent problems and results about kernels in directed graphs, Discrete Math.,1990, 86(1/2/3):27-31.
[5]Boros, E. and Gurvich, V., A corrected version of the Duchet kernel conjecture, Discrete Math., 1998,179(1/2/3):231-233.
[6]Chvatal, V., On the computational complexity of finding a kernel, Report NO. CRM-300, Centre de Recherches Mathematiques, Montreal:Universite de Montreal, 1973.
[7]Duchet, P., Graphes noyau-parfaits, Ann. Discrete Math., 1980, 9:93-101(in French).
[8]Fraenkel, A., Planar kernel and Grundy with d≤3, d_(out)≤2, d_(in)≤2 are NP-complete, Discrete Appl.Math., 1981, 3(4):257-262.
[9]Kwasnik, M., The generalization of Richardson theorem, Discuss. Math., 1981,4:11-14.
[10]Manuel, P., Rajasingh, I., Rajan, B. and Punitha, J., Kernel in oriented circulant graphs, In:Combinatorial Algorithms, Lecture Notes in Comput. Sci., Vol. 5874, Berlin:Springer-Verlag, 2009, 396-407.
[11]Richardson, M., Solutions of irreflexive relations, Ann. of Math.(2), 1953, 58:573-590.
[12]Szwarcfiter, J. and Chaty, G., Enumerating the kernels of a directed graph with no odd circuits, Inform.Process. Lett., 1994, 51(3):149-153.
[13]Van Leeuwen, J., Having a Grundy-numbering is NP-complete, Report No. 207, Computer Science Dept.,University Park, PA:Pennsylvania State University, 1976.
[14]Von Neumann, J. and Morgenstern, O., Theory of Games and Economic Behaviour, Princeton:Princeton Univ. Press, 1994.