اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn exponential domination of the consecutive circulant graph
131
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
For a graph $G,$ we consider $D subset V(G)$ to be a porous exponential dominating set if $1le sum_{d in D}$ $left( frac{1}{2} right)^{text{dist}(d,v) -1}$ for every $v in V(G),$ where dist$(d,v)$ denotes the length of the smallest $dv$ path. Similarly, $D subset V(G)$ is a non-porous exponential dominating set is $1le sum_{d in D} left( frac{1}{2} right)^{overline{text{dist}}(d,v) -1}$ for every $v in V(G),$ where $overline{text{dist}}(d,v)$ represents the length of the shortest $dv$ path with no internal vertices in $D.$ The porous and non-porous exponential dominating number of $G,$ denoted $gamma_e^*(G)$ and $gamma_e(G),$ are the minimum cardinality of a porous and non-porous exponential dominating set, respectively. The consecutive circulant graph, $C_{n, [ell]},$ is the set of $n$ vertices such that vertex $v$ is adjacent to $v pm i mod n$ for each $i in [ell].$ In this paper we show $gamma_e(C_{n, [ell]}) = gamma_e^*(C_{n, [ell]}) = leftlceil tfrac{n}{3ell +1} rightrceil.$
قيم البحث
اقرأ أيضاً
A graph $X$ is said to be unstable if the direct product $X times K_2$ (also called the canonical double cover of $X$) has automorphisms that do not come from automorphisms of its factors $X$ and $K_2$. It is nontrivially unstable if it is unstable,
connected, and nonbipartite, and no two distinct vertices of X have exactly the same neighbors. We find three new conditions that each imply a circulant graph is unstable. (These yield infinite families of nontrivially unstable circulant graphs that were not previously known.) We also find all of the nontrivially unstable circulant graphs of order $2p$, where $p$ is any prime number. Our results imply that there does not exist a nontrivially unstable circulant graph of order $n$ if and only if either $n$ is odd, or $n < 8$, or $n = 2p$, for some prime number $p$ that is congruent to $3$ modulo $4$.
The domination polynomials of binary graph operations, aside from union, join and corona, have not been widely studied. We compute and prove recurrence formulae and properties of the domination polynomials of families of graphs obtained by various pr
oducts, ranging from explicit formulae and recurrences for specific families to more general results. As an application, we show the domination polynomial is computationally hard to evaluate.
For a graph $G,$ the set $D subseteq V(G)$ is a porous exponential dominating set if $1 le sum_{d in D} left( 2 right)^{1-dist(d,v)}$ for every $v in V(G),$ where $dist(d,v)$ denotes the length of the shortest $dv$ path. The porous exponential domina
ting number of $G,$ denoted $gamma_e^*(G),$ is the minimum cardinality of a porous exponential dominating set. For any graph $G,$ a technique is derived to determine a lower bound for $gamma_e^*(G).$ Specifically for a grid graph $H,$ linear programing is used to sharpen bound found through the lower bound technique. Lower and upper bounds are determined for the porous exponential domination number of the King Grid $mathcal{K_n},$ the Slant Grid $mathcal{S_n},$ and the $n$-dimensional hypercube $Q_n.$
A vertex $v$ in a porous exponential dominating set assigns weight $left(tfrac{1}{2}right)^{dist(v,u)}$ to vertex $u$. A porous exponential dominating set of a graph $G$ is a subset of $V(G)$ such that every vertex in $V(G)$ has been assigned a sum w
eight of at least 1. In this paper the porous exponential dominating number, denoted by $gamma_e^*(G)$, for the graph $G = C_m times C_n$ is discussed. Anderson et. al. proved that $frac{mn}{15.875}le gamma_e^*(C_m times C_n) le frac{mn}{13}$ and conjectured that $frac{mn}{13}$ is also the asymptotic lower bound. We use a linear programing approach to sharpen the lower bound to $frac{mn}{13.7619 + epsilon(m,n)}$.
Let ${[n] choose k}$ and ${[n] choose l}$ $( k > l ) $ where $[n] = {1,2,3,...,n}$ denote the family of all $k$-element subsets and $l$-element subsets of $[n]$ respectively. Define a bipartite graph $G_{k,l} = ({[n] choose k},{[n] choose l},E)$ such
that two vertices $S, epsilon ,{[n] choose k} $ and $T, epsilon ,{[n] choose l} $ are adjacent if and only if $T subset S$. In this paper, we give an upper bound for the domination number of graph $G_{k,2}$ for $k > lceil frac{n}{2} rceil$ and exact value for $k=n-1$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
