Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLower Bounds for the Exponential Domination Number of $C_m times C_n$
65
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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)}$.
rate research
Read More
Consider the graph $mathbb{H}(d)$ whose vertex set is the hyperbolic plane, where two points are connected with an edge when their distance is equal to some $d>0$. Asking for the chromatic number of this graph is the hyperbolic analogue to the famous Hadwiger-Nelson problem about colouring the points of the Euclidean plane so that points at distance $1$ receive different colours. As in the Euclidean case, one can lower bound the chromatic number of $mathbb{H}(d)$ by $4$ for all $d$. Using spectral methods, we prove that if the colour classes are measurable, then at least $6$ colours are are needed to properly colour $mathbb{H}(d)$ when $d$ is sufficiently large.
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.$
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.$
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.
While there have been many results on lower bounds for Max Cut in unweighted graphs, the only lower bound for non-integer weights is that by Poljak and Turzik (1986). In this paper, we launch an extensive study of lower bounds for Max Cut in weighted graphs. We introduce a new approach for obtaining lower bounds for Weighted Max Cut. Using it, Probabilistic Method, Vizings chromatic index theorem, and other tools, we obtain several lower bounds for arbitrary weighted graphs, weighted graphs of bounded girth and triangle-free weighted graphs. We pose conjectures and open questions.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
