Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userIndependent Dominating Sets in Directed Graphs
142
0
0.0
(
0
)
Added by
Adam Blumenthal
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Authors
Adam Blumenthal
Ask ChatGPT about the research
No Arabic abstract
In this paper, we study independent domination in directed graphs, which was recently introduced by Cary, Cary, and Prabhu. We provide a short, algorithmic proof that all directed acyclic graphs contain an independent dominating set. Using linear algebraic tools, we prove that any strongly connected graph with even period has at least two independent dominating sets, generalizing several of the results of Cary, Cary, and Prabhu. We prove that determining the period of the graph is not sufficient to determine the existence of an independent dominating set by constructing a few examples of infinite families of graphs. We show that the direct analogue of Vizings Conjecture does not hold for independent domination number in directed graphs by providing two infinite families of graphs. We initialize the study of time complexity for independent domination in directed graphs, proving that the existence of an independent dominating set in directed acyclic graphs and strongly connected graphs with even period are in the time complexity class $P$. We also provide an algorithm for determining existence of an independent dominating set for digraphs with period greater than $1$.
rate research
Read More
We show that any connected Cayley graph $Gamma$ on an Abelian group of order $2n$ and degree $tilde{Omega}(log n)$ has at most $2^{n+1}(1 + o(1))$ independent sets. This bound is tight up to to the $o(1)$ term when $Gamma$ is bipartite. Our proof is based on Sapozhenkos graph container method and uses the Pl{u}nnecke-Rusza-Petridis inequality from additive combinatorics.
The notion of a Riordan graph was introduced recently, and it is a far-reaching generalization of the well-known Pascal graphs and Toeplitz graphs. However, apart from a certain subclass of Toeplitz graphs, nothing was known on independent sets in Riordan graphs. In this paper, we give exact enumeration and lower and upper bounds for the number of independent sets for various classes of Riordan graphs. Remarkably, we offer a variety of methods to solve the problems that range from the structural decomposition theorem to methods in combinatorics on words. Some of our results are valid for any graph.
We study two n
Nielsen proved that the maximum number of maximal independent sets (MISs) of size $k$ in an $n$-vertex graph is asymptotic to $(n/k)^k$, with the extremal construction a disjoint union of $k$ cliques with sizes as close to $n/k$ as possible. In this paper we study how many MISs of size $k$ an $n$-vertex graph $G$ can have if $G$ does not contain a clique $K_t$. We prove for all fixed $k$ and $t$ that there exist such graphs with $n^{lfloorfrac{(t-2)k}{t-1}rfloor-o(1)}$ MISs of size $k$ by utilizing recent work of Gowers and B. Janzer on a generalization of the Ruzsa-Szemeredi problem. We prove that this bound is essentially best possible for triangle-free graphs when $kle 4$.
Let $D$ be a strongly connected digraph. The average distance $bar{sigma}(v)$ of a vertex $v$ of $D$ is the arithmetic mean of the distances from $v$ to all other vertices of $D$. The remoteness $rho(D)$ and proximity $pi(D)$ of $D$ are the maximum and the minimum of the average distances of the vertices of $D$, respectively. We obtain sharp upper and lower bounds on $pi(D)$ and $rho(D)$ as a function of the order $n$ of $D$ and describe the extreme digraphs for all the bounds. We also obtain such bounds for strong tournaments. We show that for a strong tournament $T$, we have $pi(T)=rho(T)$ if and only if $T$ is regular. Due to this result, one may conjecture that every strong digraph $D$ with $pi(D)=rho(D)$ is regular. We present an infinite family of non-regular strong digraphs $D$ such that $pi(D)=rho(D).$ We describe such a family for undirected graphs as well.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
