On P 3-Convexity of Graphs with Bounded?Degree
详细信息 查看全文
- 作者：Lucia Draque Penso (17)
Fábio Protti (18)
Dieter Rautenbach (17)
Uéverton S. Souza (18) - 关键词：P 3 ; convexity ; P 3 ; hull set ; P 3 ; geodetic set ; planar graphs ; bounded degree ; NP ; hardness
- 刊名：Lecture Notes in Computer Science
- 出版年：2014
- 出版时间：2014
- 年：2014
- 卷：8546
- 期：1
- 页码：263-274
- 参考文献：1. Balister, P., Bollobás, B., Johnson, J.R., Walters, M.: Random majority percolation. Random Struct. Algorithms?36, 315-40 (2010) CrossRef
2. Balogh, J., Bollobás, B.: Sharp thresholds in Bootstrap percolation. Physica A?326, 305-12 (2003) CrossRef
3. Bermond, J.-C., Bond, J., Peleg, D., Perennes, S.: The power of small coalitions in graphs. Discrete Appl. Math.?127, 399-14 (2003) CrossRef
4. Centeno, C.C., Dourado, M.C., Penso, L.D., Rautenbach, D., Szwarcfiter, J.L.: Irreversible conversion of graphs. Theor. Comput. Sci.?412, 3693-700 (2011) CrossRef
5. Centeno, C.C., Penso, L.D., Rautenbach, D., de Sá, V.G.P.: Immediate versus eventual conversion: comparing geodetic and hull numbers in P3-convexity. In: Golumbic, M.C., Stern, M., Levy, A., Morgenstern, G. (eds.) WG 2012. LNCS, vol.?7551, pp. 262-73. Springer, Heidelberg (2012) CrossRef
6. Dreyer Jr., P.A., Roberts, F.S.: Irreversible k-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion. Discrete Appl. Math.?157, 1615-627 (2009) CrossRef
7. Cook, S.A.: The complexity of theorem-proving procedures. In: Proc. 3rd Ann. ACM Symp. on Theory of Computing Machinery, New York, pp. 151-58 (1971)
8. Hansberg, A., Volkmann, L.: On graphs with equal domination and 2-domination numbers. Discrete Mathematics?308(11), 2277-281 (2008) CrossRef
9. Garey, M.R., Johnson, D.S.: Computers and intractability. Freeman, N.York (1979)
10. Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of domination in graphs. Marcel Dekker (1998)
11. DeLaVina, E., Goddard, W., Henning, M.A., Pepper, R., Vaughan, E.R.: Bounds on the k-domination number of a graph. Applied Mathematics Letters?24(6), 996-98 (2011) CrossRef
12. Hansberg, A., Volkmann, L.: On 2-domination and independence domination numbers of graphs. Ars Combinatoria?101, 405-15 (2011)
13. Centeno, C.C., Penso, L.D., Rautenbach, D., de Sà, V.G.P.: Geodetic Number versus Hull Number in / P 3-Convexity. SIAM Journal on Discrete Mathematics?27(2), 717-31 (2013) CrossRef
14. Lichtenstein, D.: Planar satisfiability and its uses. SIAM Journal on Computing?11, 329-43 (1982) CrossRef
15. Ueno, S., Kajitani, Y., Gotoh, S.: On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three. Discrete Mathematics?72(1-3), 355-60 (1988) CrossRef - 作者单位：Lucia Draque Penso (17)
Fábio Protti (18)
Dieter Rautenbach (17)
Uéverton S. Souza (18)
17. Universit?t Ulm, Ulm, Germany
18. IC - Universidade Federal Fluminense, Niterói, RJ, Brazil - ISSN：1611-3349
文摘
Motivated by the large applicability as well as the hardness of P 3-convexity, we study new complexity aspects of such convexity restricted to graphs with bounded maximum degree. More specifically, we are interested in identifying either a minimum P 3-geodetic set or a minimum P 3-hull set of such graphs, from which the whole vertex set of G is obtained either after one or sufficiently many iterations, respectively. Each iteration adds to a set S all vertices of V(G)??-em class="a-plus-plus">S with at least two neighbors in S. We prove that: (i) a minimum P 3-hull set of a graph G can be found in polynomial time when \(\delta(G)\geq \frac{n(G)}{c}\) (for some constant c); (ii) deciding if the size of a minimum P 3-hull set of a graph is at most k remains NP-complete even on planar graphs with maximum degree four; (iii) a minimum P 3-hull set of a cubic graph can be found in polynomial time; (iv) a minimum P 3-hull set can be found in polynomial time in graphs with minimum feedback vertex set of bounded size and no vertex of degree two; (v) deciding if the size of a minimum P 3-geodetic set of a planar graph with maximum degree three is at most k remains NP-complete.