Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA New Upper Bound on Total Domination Number of Bipartite Graphs
143
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $ G $ be a graph. A subset $S subseteq V(G) $ is called a total dominating set if every vertex of $G$ is adjacent to at least one vertex of $S$. The total domination number, $gamma_{t}$($G$), is the minimum cardinality of a total dominating set of $G$. In this paper using a greedy algorithm we provide an upper bound for $gamma_{t}$($G$), whenever $G$ is a bipartite graph and $delta(G)$ $geq$ $k$. More precisely, we show that if $k$ > 1 is a natural number, then for every bipartite graph $G$ of order $n$ and $delta(G) ge k$, $ $$gamma_{t}$($G$) $leq$ $n(1- frac{k!}{prod_{i=0}^{k-1}(frac{k}{k-1}+i)}).$
rate research
Read More
A $k$-tuple total dominating set ($k$TDS) of a graph $G$ is a set $S$ of vertices in which every vertex in $G$ is adjacent to at least $k$ vertices in $S$. The minimum size of a $k$TDS is called the $k$-tuple total dominating number and it is denoted by $gamma_{times k,t}(G)$. We give a constructive proof of a general formula for $gamma_{times 3, t}(K_n Box K_m)$.
For a graph $G=(V,E)$, we call a subset $ Ssubseteq V cup E$ a total mixed dominating set of $G$ if each element of $V cup E$ is either adjacent or incident to an element of $S$, and the total mixed domination number $gamma_{tm}(G)$ of $G$ is the minimum cardinality of a total mixed dominating set of $G$. In this paper, we initiate to study the total mixed domination number of a connected graph by giving some tight bounds in terms of some parameters such as order and total domination numbers of the graph and its line graph. Then we discuss on the relation between total mixed domination number of a graph and its diameter. Studing of this number in trees is our next work. Also we show that the total mixed domination number of a graph is equale to the total domination number of a graph which is obtained by the graph. Giving the total mixed domination numbers of some special graphs is our last work.
In this paper, we study the domination number of middle graphs. Indeed, we obtain tight bounds for this number in terms of the order of the graph. We also compute the domination number of some families of graphs such as star graphs, double start graphs, path graphs, cycle graphs, wheel graphs, complete graphs, complete bipartite graphs and friendship graphs, explicitly. Moreover, some Nordhaus-Gaddum-like relations are presented for the domination number of middle graphs.
A fan $F_n$ is a graph consisting of $n$ triangles, all having precisely one common vertex. Currently, the best known bounds for the Ramsey number $R(F_n)$ are $9n/2-5 leq R(F_n) leq 11n/2+6$, obtained by Chen, Yu and Zhao. We improve the upper bound to $31n/6+O(1)$.
Total dominator total coloring of a graph is a total coloring of the graph such that each object of the graph is adjacent or incident to every object of some color class. The minimum namber of the color classes of a total dominator total coloring of a graph is called the total dominator total chromatic number of the graph. Here, we will find the total dominator chromatic numbers of wheels, complete bipartite graphs and complete graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
