On Total Domination and Hop Domination in Diamond-Free Graphs

• Published in: Bulletin of the Malaysian Mathematical Sciences Society 2020-03, Vol.43 (2), p.1885-1891
• Main Authors: Chen, Xue-gang, Wang, Yu-feng
• Format: Article
• Language: English
• Subjects: Apexes; Applications of Mathematics; Diamonds; Graph theory; Graphs; Mathematics; Mathematics and Statistics
• ISSN: 0126-6705; 2180-4206
• DOI: 10.1007/s40840-019-00778-w

Two vertices in a graph are said to 2-step dominate each other if they are at distance 2 apart. A set S of vertices in a graph G is a hop dominating set of G if every vertex outside S is 2-step dominated by some vertex of S . The hop domination number, γ h ( G ) , of G is the minimum cardinality of a hop dominating set of G . A set S of vertices in a graph G is a total dominating set of G if every vertex in G is adjacent to at least one vertex of S . The total domination number, γ t ( G ) , of G is the minimum cardinality of a total dominating set of G . It is known that if G is a triangle-free graph, then γ h ( G ) ≤ γ t ( G ) . But there are connected graphs G for which the difference γ h ( G ) - γ t ( G ) can be made arbitrarily large. It would be interesting to find other classes of graphs G that satisfy γ h ( G ) ≤ γ t ( G ) . In this paper, we study the relationship between total domination number and hop domination number in diamond-free graph. We prove that if G is diamond-free graph of order n with the exception of two special graphs, then γ h ( G ) - γ t ( G ) ≤ n 6 . Furthermore, we find two subclasses of diamond-free graphs G that satisfy γ h ( G ) ≤ γ t ( G ) and generalize the known result.