اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدRainbow independent sets in certain classes of graphs
211
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
For a given class $mathcal{C}$ of graphs and given integers $m leq n$, let $f_mathcal{C}(n,m)$ be the minimal number $k$ such that every $k$ independent $n$-sets in any graph belonging to $mathcal{C}$ have a (possibly partial) rainbow independent $m$-set. Motivated by known results on the finiteness and actual value of $f_mathcal{C}(n,m)$ when $mathcal{C}$ is the class of line graphs of graphs, we study this function for various other classes.
قيم البحث
اقرأ أيضاً
Given a family $mathcal{I}$ of independent sets in a graph, a rainbow independent set is an independent set $I$ such that there is an injection $phicolon Ito mathcal{I}$ where for each $vin I$, $v$ is contained in $phi(v)$. Aharoni, Briggs, J. Kim, a
nd M. Kim [Rainbow independent sets in certain classes of graphs. arXiv:1909.13143] determined for various graph classes $mathcal{C}$ whether $mathcal{C}$ satisfies a property that for every $n$, there exists $N=N(mathcal{C},n)$ such that every family of $N$ independent sets of size $n$ in a graph in $mathcal{C}$ contains a rainbow independent set of size $n$. In this paper, we add two dense graph classes satisfying this property, namely, the class of graphs of bounded neighborhood diversity and the class of $r$-powers of graphs in a bounded expansion class.
Given a graph $G$, let $f_{G}(n,m)$ be the minimal number $k$ such that every $k$ independent $n$-sets in $G$ have a rainbow $m$-set. Let $mathcal{D}(2)$ be the family of all graphs with maximum degree at most two. Aharoni et al. (2019) conjectured t
hat (i) $f_G(n,n-1)=n-1$ for all graphs $Ginmathcal{D}(2)$ and (ii) $f_{C_t}(n,n)=n$ for $tge 2n+1$. Lv and Lu (2020) showed that the conjecture (ii) holds when $t=2n+1$. In this article, we show that the conjecture (ii) holds for $tgefrac{1}{3}n^2+frac{44}{9}n$. Let $C_t$ be a cycle of length $t$ with vertices being arranged in a clockwise order. An ordered set $I=(a_1,a_2,ldots,a_n)$ on $C_t$ is called a $2$-jump independent $n$-set of $C_t$ if $a_{i+1}-a_i=2pmod{t}$ for any $1le ile n-1$. We also show that a collection of 2-jump independent $n$-sets $mathcal{F}$ of $C_t$ with $|mathcal{F}|=n$ admits a rainbow independent $n$-set, i.e. (ii) holds if we restrict $mathcal{F}$ on the family of 2-jump independent $n$-sets. Moreover, we prove that if the conjecture (ii) holds, then (i) holds for all graphs $Ginmathcal{D}(2)$ with $c_e(G)le 4$, where $c_e(G)$ is the number of components of $G$ isomorphic to cycles of even lengths.
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 alg
ebraic 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 Ri
ordan 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$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
