Let G be a simple graph with no isolated vertices. A set S of vertices of G is a total dominating set if every vertex of G is adjacent to some vertex in S . The total domination number of G , den...Let G be a simple graph with no isolated vertices. A set S of vertices of G is a total dominating set if every vertex of G is adjacent to some vertex in S . The total domination number of G , denoted by γ t (G) , is the minimum cardinality of a total dominating set of G . It is shown that if G is a graph of order n with minimum degree at least 3, then γ t (G)≤n/2 . Thus a conjecture of Favaron, Henning, Mynhart and Puech is settled in the affirmative.展开更多
We have introduced the total domination polynomial for any simple non isolated graph G in [7] and is defined by Dt(G, x) = ∑in=yt(G) dr(G, i) x', where dr(G, i) is the cardinality of total dominating sets of...We have introduced the total domination polynomial for any simple non isolated graph G in [7] and is defined by Dt(G, x) = ∑in=yt(G) dr(G, i) x', where dr(G, i) is the cardinality of total dominating sets of G of size i, and yt(G) is the total domination number of G. In [7] We have obtained some properties of Dt(G, x) and its coefficients. Also, we have calculated the total domination polynomials of complete graph, complete bipartite graph, join of two graphs and a graph consisting of disjoint components. In this paper, we presented for any two isomorphic graphs the total domination polynomials are same, but the converse is not true. Also, we proved that for any n vertex transitive graph of order n and for any v ∈ V(G), dt(G, i) = 7 dt(V)(G, i), 1 〈 i 〈 n. And, for any k-regular graph of order n, dr(G, i) = (7), i 〉 n-k and d,(G, n-k) = (kn) - n. We have calculated the total domination polynomial of Petersen graph D,(P, x) = 10X4 + 72x5 + 140x6 + 110x7 + 45x8 + [ 0x9 + x10. Also, for any two vertices u and v of a k-regular graph Hwith N(u) ≠ N(v) and if Dr(G, x) = Dt( H, x ), then G is also a k-regular graph.展开更多
文摘Let G be a simple graph with no isolated vertices. A set S of vertices of G is a total dominating set if every vertex of G is adjacent to some vertex in S . The total domination number of G , denoted by γ t (G) , is the minimum cardinality of a total dominating set of G . It is shown that if G is a graph of order n with minimum degree at least 3, then γ t (G)≤n/2 . Thus a conjecture of Favaron, Henning, Mynhart and Puech is settled in the affirmative.
文摘We have introduced the total domination polynomial for any simple non isolated graph G in [7] and is defined by Dt(G, x) = ∑in=yt(G) dr(G, i) x', where dr(G, i) is the cardinality of total dominating sets of G of size i, and yt(G) is the total domination number of G. In [7] We have obtained some properties of Dt(G, x) and its coefficients. Also, we have calculated the total domination polynomials of complete graph, complete bipartite graph, join of two graphs and a graph consisting of disjoint components. In this paper, we presented for any two isomorphic graphs the total domination polynomials are same, but the converse is not true. Also, we proved that for any n vertex transitive graph of order n and for any v ∈ V(G), dt(G, i) = 7 dt(V)(G, i), 1 〈 i 〈 n. And, for any k-regular graph of order n, dr(G, i) = (7), i 〉 n-k and d,(G, n-k) = (kn) - n. We have calculated the total domination polynomial of Petersen graph D,(P, x) = 10X4 + 72x5 + 140x6 + 110x7 + 45x8 + [ 0x9 + x10. Also, for any two vertices u and v of a k-regular graph Hwith N(u) ≠ N(v) and if Dr(G, x) = Dt( H, x ), then G is also a k-regular graph.