The Experts below are selected from a list of 4161 Experts worldwide ranked by ideXlab platform
Michael A. Henning - One of the best experts on this subject based on the ideXlab platform.
-
trees with equal total domination and game total domination numbers
Discrete Applied Mathematics, 2017Co-Authors: Michael A. Henning, Douglas F RallAbstract:Abstract In this paper, we continue the study of the total domination game in graphs introduced in Henning et al. (2015), where the players Dominator and Staller alternately select vertices of G . Each Vertex chosen must strictly increase the number of vertices totally dominated, where a Vertex totally dominates another Vertex if they are neighbors. This process eventually produces a total dominating set S of G in which every Vertex is totally dominated by a Vertex in S . Dominator wishes to minimize the number of vertices chosen, while Staller wishes to maximize it. The game total domination number, γ tg ( G ) , (respectively, Staller-start game total domination number, γ tg ′ ( G ) ) of G is the number of vertices chosen when Dominator (respectively, Staller) starts the game and both players play optimally. For general graphs G , sometimes γ tg ( G ) > γ tg ′ ( G ) . We show that if G is a forest with no Isolated Vertex, then γ tg ( G ) ≤ γ tg ′ ( G ) . Using this result, we characterize the trees with equal total domination and game total domination number.
-
trees with equal total domination and game total domination numbers
arXiv: Combinatorics, 2016Co-Authors: Michael A. Henning, Douglas F RallAbstract:In this paper, we continue the study of the total domination game in graphs introduced in [Graphs Combin. 31(5) (2015), 1453--1462], where the players Dominator and Staller alternately select vertices of $G$. Each Vertex chosen must strictly increase the number of vertices totally dominated, where a Vertex totally dominates another Vertex if they are neighbors. This process eventually produces a total dominating set $S$ of $G$ in which every Vertex is totally dominated by a Vertex in $S$. Dominator wishes to minimize the number of vertices chosen, while Staller wishes to maximize it. The game total domination number, $\gamma_{\rm tg}(G)$, (respectively, Staller-start game total domination number, $\gamma_{\rm tg}'(G)$) of $G$ is the number of vertices chosen when Dominator (respectively, Staller) starts the game and both players play optimally. For general graphs $G$, sometimes $\gamma_{\rm tg}(G) > \gamma_{\rm tg}'(G)$. We show that if $G$ is a forest with no Isolated Vertex, then $\gamma_{\rm tg}(G) \le \gamma_{\rm tg}'(G)$. Using this result, we characterize the trees with equal total domination and game total domination number.
-
total roman domination in graphs
Applicable Analysis and Discrete Mathematics, 2016Co-Authors: Hossein Ahangar Abdollahzadeh, Michael A. Henning, Vladimir Samodivkin, Ismael G YeroAbstract:A Roman dominating function on a graph G is a function f:V(G) → {0,1,2} satisfying the condition that every Vertex u for which f(u) = 0 is adjacent to at least one Vertex v for which f(v) = 2. The weight of a Roman dominating function f is the sum, ΣuV(G) f(u), of the weights of the vertices. The Roman domination number is the minimum weight of a Roman dominating function in G. A total Roman domination function is a Roman dominating function with the additional property that the subgraph of G induced by the set of all vertices of positive weight has no Isolated Vertex. The total Roman domination number is the minimum weight of a total Roman domination function on G. We establish lower and upper bounds on the total Roman domination number. We relate the total Roman domination to domination parameters, including the domination number, the total domination number and Roman domination number.
-
total dominator colorings and total domination in graphs
Graphs and Combinatorics, 2015Co-Authors: Michael A. HenningAbstract:A total dominator coloring of a graph $$G$$G is a proper coloring of the vertices of $$G$$G in which each Vertex of the graph is adjacent to every Vertex of some color class. The total dominator chromatic number $$\chi _d^t(G)$$?dt(G) of $$G$$G is the minimum number of colors among all total dominator coloring of $$G$$G. A total dominating set of $$G$$G is a set $$S$$S of vertices such that every Vertex in $$G$$G is adjacent to at least one Vertex in $$S$$S. The total domination number $$\gamma _t(G)$$?t(G) of $$G$$G is the minimum cardinality of a total dominating set of $$G$$G. We establish lower and upper bounds on the total dominator chromatic number of a graph in terms of its total domination number. In particular, we show that every graph $$G$$G with no Isolated Vertex satisfies $$\gamma _t(G) \le \chi _d^t(G) \le \gamma _t(G) + \chi (G)$$?t(G)≤?dt(G)≤?t(G)+?(G), where $$\chi (G)$$?(G) denotes the chromatic number of $$G$$G. We establish properties of total dominator colorings in trees. We characterize the trees $$T$$T for which $$\gamma _t(T) = \chi _d^t(T)$$?t(T)=?dt(T). We prove that if $$T$$T is a tree of $$n \ge 2$$n?2 vertices, then $$\chi _d^t(T) \le 2(n+1)/3$$?dt(T)≤2(n+1)/3 and we characterize the trees achieving equality in this bound.
-
graphs with large disjunctive total domination number
arXiv: Combinatorics, 2014Co-Authors: Michael A. Henning, Viroshan NaickerAbstract:Let $G$ be a graph with no Isolated Vertex. In this paper, we study a parameter that is a relaxation of arguably the most important domination parameter, namely the total domination number, $\gamma_t(G)$. A set $S$ of vertices in $G$ is a disjunctive total dominating set of $G$ if every Vertex is adjacent to a Vertex of $S$ or has at least two vertices in $S$ at distance $2$ from it. The disjunctive total domination number, $\gamma^d_t(G)$, is the minimum cardinality of such a set. We observe that $\gamma^d_t(G) \le \gamma_t(G)$. Let $G$ be a connected graph on $n$ vertices with minimum degree $\delta$. It is known [J. Graph Theory 35 (2000), 21--45] that if $\delta \ge 2$ and $n \ge 11$, then $\gamma_t(G) \le 4n/7$. Further [J. Graph Theory 46 (2004), 207--210] if $\delta \ge 3$, then $\gamma_t(G) \le n/2$. We prove that if $\delta \ge 2$ and $n \ge 8$, then $\gamma^d_t(G) \le n/2$ and we characterize the extremal graphs.
Reddy, Venkata P. Subba - One of the best experts on this subject based on the ideXlab platform.
-
Algorithmic complexity of isolate secure domination in graphs
Işık University Press, 2021Co-Authors: Kumar, Jakkepalli Pavan, Reddy, Venkata P. SubbaAbstract:A dominating set S is an Isolate Dominating Set (IDS) if the induced subgraph G[S] has at least one Isolated Vertex. In this paper, we initiate the study of new domination parameter called, isolate secure domination. An isolate dominating set S subset of V is an isolate secure dominating set (ISDS), if for each Vertex u is an element of V \ S, there exists a neighboring Vertex v of u in S such that (S \ {v}) boolean OR {u} is an IDS of G. The minimum cardinality of an ISDS of G is called as an isolate secure domination number, and is denoted by gamma(0s) (G). We give isolate secure domination number of path and cycle graphs. Given a graph G = (V, E) and a positive integer k, the ISDM problem is to check whether G has an isolate secure dominating set of size at most k. We prove that ISDM is NP-complete even when restricted to bipartite graphs and split graphs. We also show that ISDM can be solved in linear time for graphs of bounded tree-width.Publisher's Versio
-
Algorithmic Complexity of Isolate Secure Domination in Graphs
2020Co-Authors: Kumar, Jakkepalli Pavan, Reddy, Venkata P. SubbaAbstract:A dominating set $S$ is an Isolate Dominating Set (IDS) if the induced subgraph $G[S]$ has at least one Isolated Vertex. In this paper, we initiate the study of new domination parameter called, isolate secure domination. An isolate dominating set $S\subseteq V$ is an isolate secure dominating set (ISDS), if for each Vertex $u \in V \setminus S$, there exists a neighboring Vertex $v$ of $u$ in $S$ such that $(S \setminus \{v\}) \cup \{u\}$ is an IDS of $G$. The minimum cardinality of an ISDS of $G$ is called as an isolate secure domination number, and is denoted by $\gamma_{0s}(G)$. Given a graph $ G=(V,E)$ and a positive integer $ k,$ the ISDM problem is to check whether $ G $ has an isolate secure dominating set of size at most $ k.$ We prove that ISDM is NP-complete even when restricted to bipartite graphs and split graphs. We also show that ISDM can be solved in linear time for graphs of bounded tree-width.Comment: arXiv admin note: substantial text overlap with arXiv:2002.00002; text overlap with arXiv:2001.1125
-
Algorithmic Aspects of Some Variants of Domination in Graphs
2020Co-Authors: Kumar, Jakkepalli Pavan, Reddy, Venkata P. SubbaAbstract:A set $S \subseteq V$ is a dominating set in G if for every u \in V \ S, there exists $v \in S$ such that $(u,v) \in E$, i.e., $N[S] = V$. A dominating set $S$ is an Isolate Dominating Set} (IDS) if the induced subgraph $G[S]$ has at least one Isolated Vertex. It is known that Isolate Domination Decision problem (IDOM) is NP-complete for bipartite graphs. In this paper, we extend this by showing that the IDOM is NP-complete for split graphs and perfect elimination bipartite graphs, a subclass of bipartite graphs. A set $S \subseteq V$ is an independent set if G[S] has no edge. A set S \subseteq V is a secure dominating set of $G$ if, for each Vertex $u \in V \setminus S$, there exists a Vertex $v \in S$ such that $ (u,v) \in E $ and $(S \ \{v\}) \cup \{u\}$ is a dominating set of $G$. In addition, we initiate the study of a new domination parameter called, independent secure domination. A set $S\subseteq V$ is an Independent Secure Dominating Set (InSDS) if $S$ is an independent set and a secure dominating set of $G$. The minimum size of an InSDS in $G$ is called the independent secure domination number of $G$ and is denoted by $\gamma_{is}(G)$. Given a graph $ G$ and a positive integer $ k,$ the InSDM problem is to check whether $ G $ has an independent secure dominating set of size at most $ k.$ We prove that InSDM is NP-complete for bipartite graphs and linear time solvable for bounded tree-width graphs and threshold graphs, a subclass of split graphs. The MInSDS problem is to find an independent secure dominating set of minimum size, in the input graph. Finally, we prove that the MInSDS problem is APX-hard for graphs with maximum degree $5.$Comment: arXiv admin note: text overlap with arXiv:2001.1125
Lu Mei - One of the best experts on this subject based on the ideXlab platform.
-
Bounds on the Locating-Total Domination Number in Trees
'Faculty of Mathematics Computer Science and Econometrics University of Zielona Gora', 2020Co-Authors: Wang Kun, Ning Wenjie, Lu MeiAbstract:Given a graph G = (V, E) with no Isolated Vertex, a subset S of V is called a total dominating set of G if every Vertex in V has a neighbor in S. A total dominating set S is called a locating-total dominating set if for each pair of distinct vertices u and v in V \ S, N(u) ∩ S ≠ N(v) ∩ S. The minimum cardinality of a locating-total dominating set of G is the locating-total domination number, denoted by γtL(G)\gamma _t^L ( G ) . We show that, for a tree T of order n ≥ 3 and diameter d+12≤γtL(T)≤n−d−12{{d + 1} \over 2} \le \gamma _t^L ( T ) \le n - {{d - 1} \over 2} , and if T has l leaves, s support vertices and s1 strong support vertices, then γtL(T)≥max{n+l−s+12−s+s14,2(n+1)+3(l−s)−s15}\gamma _t^L ( T ) \ge \max \left\{ {{{n + l - s + 1} \over 2} - {{s + {s_1}} \over 4},{{2 ( {n + 1} ) + 3 ( {l - s} ) - {s_1}} \over 5}} \right\} . We also characterize the extremal trees achieving these bounds
-
Vertex degree sums for matchings in 3-uniform hypergraphs
2019Co-Authors: Yi Zhang, Yi Zhao, Lu MeiAbstract:Let $n, s$ be positive integers such that $n$ is sufficiently large and $s\le n/3$. Suppose $H$ is a 3-uniform hypergraph of order $n$. If $H$ contains no Isolated Vertex and $deg(u)+ deg(v) > 2(s-1)(n-1)$ for any two vertices $u$ and $v$ that are contained in some edge of $H$, then $H$ contains a matching of size $s$. This degree sum condition is best possible and confirms a conjecture of the authors [Electron. J. Combin. 25 (3), 2018], who proved the case when $s= n/3$.Comment: arXiv admin note: text overlap with arXiv:1710.0475
-
Bounding the Locating-Total Domination Number of a Tree in Terms of Its Annihilation Number
'Faculty of Mathematics Computer Science and Econometrics University of Zielona Gora', 2019Co-Authors: Ning Wenjie, Lu Mei, Wang KunAbstract:Suppose G = (V,E) is a graph with no Isolated Vertex. A subset S of V is called a locating-total dominating set of G if every Vertex in V is adjacent to a Vertex in S, and for every pair of distinct vertices u and v in V −S, we have N(u) ∩ S ≠ N(v) ∩ S. The locating-total domination number of G, denoted by γLt(G), is the minimum cardinality of a locating-total dominating set of G. The annihilation number of G, denoted by a(G), is the largest integer k such that the sum of the first k terms of the nondecreasing degree sequence of G is at most the number of edges in G. In this paper, we show that for any tree of order n ≥ 2, γLt(T) ≤ a(T) + 1 and we characterize the trees achieving this bound
Martin Furer - One of the best experts on this subject based on the ideXlab platform.
-
efficient computation of the characteristic polynomial of a threshold graph
Theoretical Computer Science, 2017Co-Authors: Martin FurerAbstract:An efficient algorithm is presented to compute the characteristic polynomial of a threshold graph. Threshold graphs were introduced by Chvatal and Hammer, as well as by Henderson and Zalcstein in 1977. A threshold graph is obtained from a one Vertex graph by repeatedly adding either an Isolated Vertex or a dominating Vertex, which is a Vertex adjacent to all the other vertices. Threshold graphs are special kinds of cographs, which themselves are special kinds of graphs of clique-width 2. We obtain a running time of O ( n log 2 ź n ) for computing the characteristic polynomial, while the previously fastest algorithm ran in quadratic time. We improve the running time drastically in the case where there is a small number of alternations between 0's and 1's in the sequence defining a threshold graph. A simple recurrence equation for the determinant of a weighted threshold graph matrix is presented.The characteristic polynomial is computed in O ( n log 2 ź n ) arithmetic operations.The algorithm is more efficient if the alternations in the defining sequence are o ( n ) .As the numbers may be of length n log ź n , the bit complexity is investigated too.
-
efficient computation of the characteristic polynomial of a threshold graph
International Workshop on Frontiers in Algorithmics, 2015Co-Authors: Martin FurerAbstract:An efficient algorithm is presented to compute the characteristic polynomial of a threshold graph. Threshold graphs were introduced by Chvatal and Hammer, as well as by Henderson and Zalcstein in 1977. A threshold graph is obtained from a one Vertex graph by repeatedly adding either an Isolated Vertex or a dominating Vertex, which is a Vertex adjacent to all the other vertices. Threshold graphs are special kinds of cographs, which themselves are special kinds of graphs of clique-width 2. We obtain a running time of \(O(n \log ^2 n)\) for computing the characteristic polynomial, while the previously fastest algorithm ran in quadratic time.
-
efficient computation of the characteristic polynomial of a threshold graph
arXiv: Data Structures and Algorithms, 2015Co-Authors: Martin FurerAbstract:An efficient algorithm is presented to compute the characteristic polynomial of a threshold graph. Threshold graphs were introduced by Chv\'atal and Hammer, as well as by Henderson and Zalcstein in 1977. A threshold graph is obtained from a one Vertex graph by repeatedly adding either an Isolated Vertex or a dominating Vertex, which is a Vertex adjacent to all the other vertices. Threshold graphs are special kinds of cographs, which themselves are special kinds of graphs of clique-width 2. We obtain a running time of $O(n \log^2 n)$ for computing the characteristic polynomial, while the previously fastest algorithm ran in quadratic time. Keywords: Efficient Algorithms, Threshold Graphs, Characteristic Polynomial.
Yero, Ismael G. - One of the best experts on this subject based on the ideXlab platform.
-
Quasi-total Roman domination in graphs
2019Co-Authors: Cabrera-garcia Suitberto, Cabrera-martinez Abel, Yero, Ismael G.Abstract:A quasi-total Roman dominating function on a graph $G=(V, E)$ is a function $f : V \rightarrow \{0,1,2\}$ satisfying the following: - every Vertex $u$ for which $f(u) = 0$ is adjacent to at least one Vertex $v$ for which $f(v) =2$, and - if $x$ is an Isolated Vertex in the subgraph induced by the set of vertices labeled with 1 and 2, then $f(x)=1$. The weight of a quasi-total Roman dominating function is the value $\omega(f)=f(V)=\sum_{u\in V} f(u)$. The minimum weight of a quasi-total Roman dominating function on a graph $G$ is called the quasi-total Roman domination number of $G$. We introduce the quasi-total Roman domination number of graphs in this article, and begin the study of its combinatorial and computational properties.Comment: 15 page
-
Quasi-total Roman Domination in Graphs
'Springer Science and Business Media LLC', 2019Co-Authors: Cabrera-garcia Suitberto, Cabrera-martinez Abel, Yero, Ismael G.Abstract:[EN] A quasi-total Roman dominating function on a graph G=(V,E) is a function f:V ->{0,1,2}satisfying the following: Every Vertex for which u for which f(u) = 0 is adjacent to at least one Vertex v for which f(v) = 2, and If x is an Isolated Vertex in the subgraph induced by the set of vertices labeled with 1 and 2, then f(x) = 1. The weight of a quasi-total Roman dominating function is the value omega(f) = f(V) = Sigma(u is an element of V) f(u). The minimum weight of a quasi-total Roman dominating function on a graph G is called the quasi-total Roman domination number of G. We introduce the quasi-total Roman domination number of graphs in this article, and begin the study of its combinatorial and computational properties.Cabrera García, S.; Cabrera Martínez, A.; Yero, IG. (2019). Quasi-total Roman Domination in Graphs. Results in Mathematics. 74(4):1-18. https://doi.org/10.1007/s00025-019-1097-5S11874
