Immediate versus Eventual Conversion: Comparing Geodetic and Hull Numbers in P3-Convexity

详细信息    查看全文

• 作者：Carmen Cecilia Centeno (1) carmen@cos.ufrj.br
  Lucia Draque Penso (2) lucia.penso@uni-ulm.de
  Dieter Rautenbach (2) dieter.rautenbach@uni-ulm.de
  Vinícius Gusmc?o Pereira de Sá (1) vigusmao@dcc.ufrj.br
• 关键词：Hull number – geodetic number – P 3 ; convexity – irreversible 2 ; threshold processes – triangle ; free graphs
• 刊名：Lecture Notes in Computer Science
• 出版年：2012
• 出版时间：2012
• 年：2012
• 卷：7551
• 期：1
• 页码：262-273
• 全文大小：202.4 KB
• 参考文献：1. Balister, P., Bollobás, B., Johnson, J.R., Walters, M.: Random majority percolation. Random Struct. Algorithms 36, 315–340 (2010)
  2. Balogh, J., Bollobás, B.: Sharp thresholds in Bootstrap percolation. Physica A 326, 305–312 (2003)
  3. Bermond, J.-C., Bond, J., Peleg, D., Perennes, S.: The power of small coalitions in graphs. Discrete Appl. Math. 127, 399–414 (2003)
  4. Centeno, C.C., Dourado, M.C., Penso, L.D., Rautenbach, D., Szwarcfiter, J.L.: Irreversible Conversion of Graphs. Theor. Comput. Sci. 412, 3693–3700 (2011)
  5. 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–1627 (2009)
  6. Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of domination in graphs. Marcel Dekker (1998)
  7. Kempe, D., Kleinberg, J., Tardos, é.: Maximizing the spread of influence through a social network. In: Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137–146 (2003)
  8. Mustafa, N.H., Peke?, A.: Listen to your neighbors: How (not) to reach a consensus. SIAM J. Discrete. Math. 17, 634–660 (2004)
  9. Nayak, A., Ren, J., Santoro, N.: An improved testing scheme for catastrophic fault patterns. Inf. Process. Lett. 73, 199–206 (2000)
  10. Peleg, D.: Local majorities, coalitions and monopolies in graphs: A review. Theor. Comput. Sci. 282, 231–257 (2002)
  11. Rautenbach, D., dos Santos, V., Sch?fer, P.M.: Irreversible conversion processes with deadlines (2010) (manuscript)
• 作者单位：1. Instituto de Matemática, NCE, and COPPE, Universidade Federal do Rio de Janeiro, Rio de Janeiro, RJ, Brazil2. Institut für Optimierung und Operations Research, Universit?t Ulm, Ulm, Germany
• ISSN：1611-3349

文摘

We study the graphs G for which the hull number h(G) and the geodetic number g(G) with respect to P ₃-convexity coincide. These two parameters correspond to the minimum cardinality of a set U of vertices of G such that the simple expansion process that iteratively adds to U, all vertices outside of U that have two neighbors in U, produces the whole vertex set of G either eventually or after one iteration, respectively. We establish numerous structural properties of the graphs G with h(G)?=?g(G), which allow the constructive characterization as well as the efficient recognition of all triangle-free such graphs. Furthermore, we characterize the graphs G that satisfy h(H)?=?g(H) for every induced subgraph H of G in terms of forbidden induced subgraphs.