7
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Two inequalities related to Vizing's conjecture

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          A well-known conjecture of Vizing is that \(\gamma(G \square H) \ge \gamma(G)\gamma(H)\) for any pair of graphs \(G, H\), where \(\gamma\) is the domination number and \(G \square H\) is the Cartesian product of \(G\) and \(H\). Suen and Tarr, improving a result of Clark and Suen, showed \(\gamma(G \square H) \ge \frac{1}{2}\gamma(G)\gamma(H) + \frac{1}{2}\min(\gamma(G),\gamma(H))\). We further improve their result by showing \(\gamma(G \square H) \ge \frac{1}{2}\gamma(G)\gamma(H) + \frac{1}{2}\max(\gamma(G),\gamma(H)).\) We also prove a fractional version of Vizing's conjecture: \(\gamma(G \square H) \ge \gamma(G)\gamma^*(H)\).

          Related collections

          Most cited references2

          • Record: found
          • Abstract: not found
          • Article: not found

          Vizing's conjecture: a survey and recent results

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            On the domination of the products of graphs II: Trees

              Bookmark

              Author and article information

              Journal
              2017-06-12
              Article
              1706.03682
              2039234d-2887-4d4d-8731-2fe84f67772c

              http://arxiv.org/licenses/nonexclusive-distrib/1.0/

              History
              Custom metadata
              math.CO

              Combinatorics
              Combinatorics

              Comments

              Comment on this article