Results 11 to 20 of about 2,421,288 (269)
Eternal Independent Sets in Graphs
Theory and Applications of Graphs, 2016 The use of mobile guards to protect a graph has received much attention in the literature of late in the form of eternal dominating sets, eternal vertex covers and other models of graph protection.
Yair Caro, William Klostermeyer
doaj +1 more source
On the Independence Number of Cayley Digraphs of Clifford Semigroups
Mathematics, 2023 Let S be a Clifford semigroup and A a subset of S. We write Cay(S,A) for the Cayley digraph of a Clifford semigroup S relative to A. The (weak, path, weak path) independence number of a graph is the maximum cardinality of an (weakly, path, weakly path ...
Krittawit Limkul, Sayan Panma
doaj +1 more source
Combinatorics, Probability and Computing, 2012 The study of extremal problems related to independent sets in hypergraphs is a problem that has generated much interest. There are a variety of types of independent sets in hypergraphs depending on the number of vertices from an independent set allowed in an edge.
Cutler, Jonathan, Radcliffe, A. J.
openaire +3 more sources
Counting Independent Sets in Hypergraphs [PDF]
Combinatorics, Probability and Computing, 2014 Let G be a triangle-free graph with n vertices and average degree t. We show that G contains at least ${\exp\biggl({1-n^{-1/12})\frac{1}{2}\frac{n}{t}\ln t} \biggl(\frac{1}{2}\ln t-1\biggr)\biggr)}$ independent sets. This improves a recent result of the first and third authors [8]. In particular, it implies that as n → ∞, every triangle-free graph on n
Cooper, J., Dutta, K., Mubayi, D.
openaire +4 more sources
Large Independent Sets on Random d-Regular Graphs with Fixed Degree d
Computation, 2023 The maximum independent set problem is a classic and fundamental combinatorial challenge, where the objective is to find the largest subset of vertices in a graph such that no two vertices are adjacent.
Raffaele Marino, Scott Kirkpatrick
doaj +1 more source
Beeping a maximal independent set [PDF]
Distributed Computing, 2011 arXiv admin note: substantial text overlap with arXiv:1108 ...
Afek, Yehuda +5 more
openaire +4 more sources
European Journal of Combinatorics, 2014 Yannakakis' Clique versus Independent Set problem (CL-IS) in communication complexity asks for the minimum number of cuts separating cliques from stable sets in a graph, called CS-separator. Yannakakis provides a quasi-polynomial CS-separator, i.e. of size $O(n^{\log n})$, and addresses the problem of finding a polynomial CS-separator. This question is
Bousquet, Nicolas +2 more
openaire +3 more sources
Critical sets, crowns and local maximum independent sets [PDF]
Journal of Global Optimization, 2021 19 pages, 11 ...
Vadim E. Levit, Eugen Mandrescu
openaire +3 more sources
Ultrafilters and Independent Sets [PDF]
Transactions of the American Mathematical Society, 1972 Independent families of sets and of functions are used to prove some theorems about ultrafilters. All of our results are well known to be provable from some form of the generalized continuum hypothesis, but had remained open without such an assumption.
openaire +1 more source
Independent Sets in Polarity Graphs [PDF]
SIAM Journal on Discrete Mathematics, 2016 Given a projective plane $ $ and a polarity $ $ of $ $, the corresponding polarity graph is the graph whose vertices are the points of $ $, and two distinct points $p_1$ and $p_2$ are adjacent if $p_1$ is incident to $p_2^{ }$ in $ $. A well-known example of a polarity graph is the Erd s-R nyi orthogonal polarity graph $ER_q$, which appears ...
Tait, Michael, Timmons, Craig
openaire +3 more sources