Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn exponential domination of the consecutive circulant graph
131
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.$
rate research
Read More
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 products, 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 dominating 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 weight 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$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
