• Fulltext

       

        Click here to view fulltext PDF


      Permanent link:
      https://www.ias.ac.in/article/fulltext/pmsc/126/01/0011-0020

    • Keywords

       

      Outer-2-independent domination; domination; outer-connected domination; Vizing’s conjecture; cartesian product of graphs.

    • Abstract

       

      We initiate the study of outer-2-independent domination in graphs. An outer-2-independent dominating set of a graph 𝐺 is a set 𝐷 of vertices of 𝐺 such that every vertex of 𝑉 (𝐺)\𝐷 has a neighbor in 𝐷 and the maximum vertex degree of the subgraph induced by 𝑉 (𝐺)\𝐷 is at most one. The outer-2-independent domination number of a graph 𝐺 is the minimum cardinality of an outer-2-independent dominating set of 𝐺. We show that if a graph has minimum degree at least two, then its outer-2-independent domination number equals the number of vertices minus the 2-independence number. Then we investigate the outer-2-independent domination in graphs with minimum degree one. We also prove the Vizing-type conjecture for outer-2-independent domination and disprove the Vizing-type conjecture for outer-connected domination.

    • Author Affiliations

       

      Marcin Krzywkowski1 2 Doost Ali Mojdeh3 Maryem Raoofi4

      1. Department of Pure and Applied Mathematics, University of Johannesburg, Johannesburg, South Africa
      2. Faculty of Electronics, Telecommunications and Informatics, Gdansk University of Technology, Gdansk, Poland
      3. Department of Mathematics, University of Mazandaran, Babolsar, Iran
      4. Department of Mathematics, Fereydun Kenar Education, Mazandaran, Iran
    • Dates

       
  • Proceedings – Mathematical Sciences | News

© 2017 Indian Academy of Sciences, Bengaluru.