اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA New Upper Bound on Total Domination Number of Bipartite Graphs
127
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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)}).$
قيم البحث
اقرأ أيضاً
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 min
imum 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 grap
hs, 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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
