Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEnumerating independent sets in Abelian Cayley graphs
131
0
0.0
(
0
)
Added by
Aditya Potukuchi
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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$.
We construct a polynomial-time algorithm that given a graph $X$ with $4p$ vertices ($p$ is prime), finds (if any) a Cayley representation of $X$ over the group $C_2times C_2times C_p$. This result, together with the known similar result for circulant graphs, shows that recognising and testing isomorphism of Cayley graphs over an abelian group of order $4p$ can be done in polynomial time.
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.
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 $G$ be a finite, undirected $d$-regular graph and $A(G)$ its normalized adjacency matrix, with eigenvalues $1 = lambda_1(A)geq dots ge lambda_n ge -1$. It is a classical fact that $lambda_n = -1$ if and only if $G$ is bipartite. Our main result provides a quantitative separation of $lambda_n$ from $-1$ in the case of Cayley graphs, in terms of their expansion. Denoting $h_{out}$ by the (outer boundary) vertex expansion of $G$, we show that if $G$ is a non-bipartite Cayley graph (constructed using a group and a symmetric generating set of size $d$) then $lambda_n ge -1 + ch_{out}^2/d^2,,$ for $c$ an absolute constant. We exhibit graphs for which this result is tight up to a factor depending on $d$. This improves upon a recent result by Biswas and Saha who showed $lambda_n ge -1 + h_{out}^4/(2^9d^8),.$ We also note that such a result could not be true for general non-bipartite graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
