Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe domination number of the graph defined by two levels of the $n$-cube, II
98
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Consider all $k$-element subsets and $ell$-element subsets $(k>ell )$ of an $n$-element set as vertices of a bipartite graph. Two vertices are adjacent if the corresponding $ell$-element set is a subset of the corresponding $k$-element set. Let $G_{k,ell}$ denote this graph. The domination number of $G_{k,1}$ was exactly determined by Badakhshian, Katona and Tuza. A conjecture was also stated there on the asymptotic value ($n$ tending to infinity) of the domination number of $G_{k,2}$. Here we prove the conjecture, determining the asymptotic value of the domination number $gamma (G_{k,2})={k+3over 2(k-1)(k+1)}n^2+o(n^2)$.
rate research
Read More
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$.
The Ramsey number r(K_3,Q_n) is the smallest integer N such that every red-blue colouring of the edges of the complete graph K_N contains either a red n-dimensional hypercube, or a blue triangle. Almost thirty years ago, Burr and ErdH{o}s conjectured that r(K_3,Q_n) = 2^{n+1} - 1 for every n in N, but the first non-trivial upper bound was obtained only recently, by Conlon, Fox, Lee and Sudakov, who proved that r(K_3,Q_n) le 7000 cdot 2^n. Here we show that r(K_3,Q_n) = (1 + o(1)) 2^{n+1} as n to infty.
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.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
