Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFair splittings by independent sets in sparse graphs
148
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Given a partition $V_1 sqcup V_2 sqcup dots sqcup V_m$ of the vertex set of a graph, we are interested in finding multiple disjoint independent sets that contain the correct fraction of vertices of each $V_j$. We give conditions for the existence of $q$ such independent sets in terms of the topology of the independence complex. We relate this question to the existence of $q$-fold points of coincidence for any continuous map from the independence complex to Euclidean space of a certain dimension, and to the existence of equivariant maps from the $q$-fold deleted join of the independence complex to a certain representation sphere of the symmetric group. As a corollary we derive the existence of $q$ pairwise disjoint independent sets accurately representing the $V_j$ in certain sparse graphs for $q$ a power of a prime.
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$.
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$.
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.
We consider numbers and sizes of independent sets in graphs with minimum degree at least $d$, when the number $n$ of vertices is large. In particular we investigate which of these graphs yield the maximum numbers of independent sets of different sizes, and which yield the largest random independent sets. We establish a strengthened form of a conjecture of Galvin concerning the first of these topics.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
