اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدDomination number of cubic graphs with large girth
153
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We show that every n-vertex cubic graph with girth at least g have domination number at most 0.299871n+O(n/g)<3n/10+O(n/g).
قيم البحث
اقرأ أيضاً
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.
An induced forest of a graph G is an acyclic induced subgraph of G. The present paper is devoted to the analysis of a simple randomised algorithm that grows an induced forest in a regular graph. The expected size of the forest it outputs provides a l
ower bound on the maximum number of vertices in an induced forest of G. When the girth is large and the degree is at least 4, our bound coincides with the best bound known to hold asymptotically almost surely for random regular graphs. This results in an alternative proof for the random case.
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)$.
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 o
f $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)}).$
The $k$-power domination problem is a problem in graph theory, which has applications in many areas. However, it is hard to calculate the exact $k$-power domination number since determining k-power domination number of a generic graph is a NP-complet
e problem. We determine the exact $k$-power domination number in two graphs which have the same number of vertices and edges: pseudofractal scale-free web and Sierpinski gasket. The $k$-power domination number becomes 1 for $kge2$ in the Sierpinski gasket, while the $k$-power domination number increases at an exponential rate with regard to the number of vertices in the pseudofractal scale-free web. The scale-free property may account for the difference in the behavior of two graphs.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
