Search

Let Γ ${\rm{\Gamma }}$ be the graph whose vertices are the chambers of the finite projective 3‐space PG(3,q) $\text{PG}(3,q)$, with two vertices being adjacent if and only if the corresponding chambers are in general position. We show that a maximal independent set of vertices of Γ ${\rm{\Gamma }}$ contains q4+3q3+4q2+3q+1 ${q}^{4}+3{q}^{3}+4{q}^{2}+3q+1$, or 3q3+5q2+3q+1 $3{q}^{3}+5{q}^{2}+3q+1$, or at most 3q3+4q2+3q+2 $3{q}^{3}+4{q}^{2}+3q+2$ elements. For q≥4 $q\ge 4$ the structure of the largest maximal independent sets is described. For q≥7 $q\ge 7$ the structure of the maximal independent sets of the three largest cardinalities is described. Using the cardinality of the second largest maximal independent sets, we show that the chromatic number of Γ ${\rm{\Gamma }}$ is q2+q ${q}^{2}+q$. [ABSTRACT FROM AUTHOR]

A graph G is well-covered if all its maximal independent sets are of the same cardinality. Assume that a weight function w is defined on its vertices, while the weight of a set of vertices is the sum of their weights. Then G is w-well-covered if all maximal independent sets are of the same weight. For every graph G, the set of weight functions w such that G is w-well-covered is a vector space, denoted WCW(G). In what follows, all weights are real. Let B be a complete bipartite induced subgraph of G on vertex sets of bipartition B X and B Y . Then B is generating if there exists an independent set S such that S ∪ B X and S ∪ B Y are both maximal independent sets of G. Generating subgraphs play an important role in finding WCW(G). In the restricted case that a generating subgraph B is isomorphic to K 1 , 1 , its unique edge is called a relating edge. Deciding whether an input graph G is well-covered is co-NP-complete. Therefore finding WCW(G) is co-NP-hard. Deciding whether an edge is relating is NP-complete. Therefore, deciding whether a subgraph is generating is NP-complete as well. This article deals with graphs G such that Δ (G) = | V (G) | - k for some k ∈ N . We prove that for this family recognizing well-covered graphs is a polynomial problem, while finding WCW(G) is co-NP-hard. To the best of our knowledge, this is the first family of graphs in the literature known to have these properties. For this set of graphs, recognizing relating edges and generating subgraphs is NP-complete. The article also deals with connected graphs for which δ (G) = k or δ (G) ≥ k - 1 k | V (G) | . For these families of graphs recognizing well-covered graphs is co-NP-complete, while recognizing relating edges is NP-complete. [ABSTRACT FROM AUTHOR]

We continue the recently started line of work on the distributed node-averaged complexity of distributed graph algorithms. The node-averaged complexity of a distributed algorithm running on a graph G = (V , E) is the average over the times at which the nodes V of G finish their computation and commit to their outputs. We study the node-averaged complexity for some of the central distributed symmetry breaking problems and provide the following results (among others). As our main result, we show that the randomized node-averaged complexity of computing a maximal independent set (MIS) in n-node graphs of maximum degree Δ is at least Ω (min { log Δ log log Δ , log n log log n }) . This bound is obtained by a novel adaptation of the well-known lower bound by Kuhn, Moscibroda, and Wattenhofer [JACM'16]. As a side result, we obtain that the worst-case randomized round complexity for computing an MIS in trees is also Ω (min { log Δ log log Δ , log n log log n }) —this essentially answers open problem 11.15 in the book by Barenboim and Elkin and resolves the complexity of MIS on trees up to an O (log log n) factor. We also show that, perhaps surprisingly, a minimal relaxation of MIS, which is the same as (2, 1)-ruling set, to the (2, 2)-ruling set problem drops the randomized node-averaged complexity to O(1). For maximal matching, we show that while the randomized node-averaged complexity is Ω (min { log Δ log log Δ , log n log log n }) , the randomized edge-averaged complexity is O(1). Further, we show that the deterministic edge-averaged complexity of maximal matching is O (log 2 Δ + log ∗ n) and the deterministic node-averaged complexity of maximal matching is O (log 3 Δ + log ∗ n) . Finally, we consider the problem of computing a sinkless orientation of a graph. The deterministic worst-case complexity of the problem is known to be Θ (log n) , even on bounded-degree graphs. We show that the problem can be solved deterministically with node-averaged complexity O (log ∗ n) , while keeping the worst-case complexity in O (log n) . [ABSTRACT FROM AUTHOR]

For a given finite commutative ring R with 1 ≠ 0 , one may associate a graph which is called the total graph of R. This graph has R as the vertex set and its two distinct vertices x and y are adjacent exactly whenever x + y is a zero-divisor of R. In this paper, we give necessary and sufficient conditions for two classes of total graphs to be Cohen–Macaulay. [ABSTRACT FROM AUTHOR]

An independent dominating set of a graph, also known as a maximal independent set, is a set S of pairwise non-adjacent vertices such that every vertex not in S is adjacent to some vertex in S. We prove that for Δ = 4 or Δ ≥ 6 , every connected n -vertex graph of maximum degree at most Δ has an independent dominating set of size at most (1 − Δ ⌊ Δ 2 / 4 ⌋ + Δ) (n − 1) + 1. In addition, we characterize all connected graphs having the equality and we show that other connected graphs have an independent dominating set of size at most (1 − Δ ⌊ Δ 2 / 4 ⌋ + Δ) n. [ABSTRACT FROM AUTHOR]

A Maximal Independent Set (MIS) is an inclusion maximal set of pairwise non-adjacent vertices. The computation of an MIS is one of the core problems in distributed computing. In this article, we introduce and analyze a finite-state distributed randomized algorithm for computing a Maximal Independent Set (MIS) on arbitrary undirected graphs. Our algorithm is self-stabilizing (reaches a correct output on any initial configuration) and can be implemented on systems with very scarce conditions. We analyze the convergence time of the proposed algorithm, showing that in many cases the algorithm converges in logarithmic time with high probability. [ABSTRACT FROM AUTHOR]

Self-stabilizing protocols enable distributed systems to recover correct behavior starting from any arbitrary configuration. In particular, when processors communicate by message passing and the communication links are unbounded, fake messages may be placed in communication links by an adversary. When the number of such fake messages is unknown, self-stabilization may require huge resources: • generic solutions (a.k.a. data link protocols) require unbounded resources, which makes them unrealistic to deploy, • specific solutions (e.g. , census or tree construction) require O (n log ⁡ n) or O (Δ log ⁡ n) bits of memory per node, where n denotes the network size and Δ its maximum degree, which may prevent scalability. We investigate the possibility of resource-efficient self-stabilizing protocols in this context. Specifically, we present self-stabilizing protocols for (Δ + 1) -coloring and maximal independent set construction in any n -node graph, under the asynchronous message-passing model. The problems of (Δ + 1) -coloring and maximal independent set construction are widely regarded as benchmark problems for evaluating local algorithms. Our protocols offer many desirable features. They are deterministic, converge in O (k Δ n 2 log ⁡ n) message exchanges, where k is the (unknown) initial number of (possibly corrupted) messages in a communication link. They use messages of O (log ⁡ log ⁡ n + log ⁡ Δ) bits with a memory of O (Δ log ⁡ Δ + log ⁡ log ⁡ n) bits at each node. The resource consumption of our protocols is thus almost oblivious to the number of nodes, enabling scalability. Moreover, a striking property of our protocols is that the nodes do not need to know the number, or any bound on the number of messages initially present in each communication link of the initial (potentially corrupted) network configuration. This permits our protocols to handle any future network with unknown message capacity communication links. A key building block of our coloring and maximal independent set schemes is an algorithm to obtain an acyclic orientation of graph edges, that is of independent interest, and can serve as a useful tool for solving other tasks in this challenging setting. [ABSTRACT FROM AUTHOR]

Self-stabilization is a promising paradigm for designing highly adaptive distributed systems. However, it cannot be realized when the communication between processes is unreliable with some constant probability. To circumvent such impossibility, this paper adopts the concept of loose-stabilization for the first time, which is a practical alternative of self-stabilization, and proposes three systematic approaches to realize loose-stabilization in the atomic-state model with probabilistically erroneous communications , namely, the redundant-state approach, the step-up approach, and the repetition approach. Further, we apply these approaches to design three corresponding loosely-stabilizing algorithms for the maximal independent set problem. • Self-stabilization solutions are precluded for most of non-trivial problems in probabilistic error models. • Loose-stabilization is a relaxed variant of self-stabilization and practically equivalent to it. • Loose-stabilization can circumvent the impossibilities of self-stabilization in probabilistic error models. • Adopt the concept of loose-stabilization in the atomic-state model for the first time. • Three loose-stabilizing algorithms for maximal independent set problem. [ABSTRACT FROM AUTHOR]

An independent dominating set of a graph is a vertex subset that is both dominating and independent set in the graph, i.e., a maximal independent set. Also, the independent domination polynomial is an ordinary generating function for the number of independent dominating sets in the graph. In this paper, we examine independent domination polynomials of zero-divisor graphs of the ring Z n where n ∈ { 2 p , p 2 , p α , p q , p 2 q , p q r } and their roots. Finally, we prove the log-concavity and unimodality of their independent domination polynomials. [ABSTRACT FROM AUTHOR]

For any n and l , we completely describe trees with the maximum and minimum numbers of maximal independent sets among all n -vertex trees with l leaves. [ABSTRACT FROM AUTHOR]

Given a graph G = (V,E), an (α, β)-ruling set is a subset S ⊆ V such that the distance between any two vertices in S is at least α, and the distance between any vertex in V and the closest vertex in S is at most \beta. We present lower bounds for distributedly computing ruling sets. More precisely, for the problem of computing a (2, β)-ruling set (and hence also any (α, β)-ruling set with α > 2) in the LOCAL model of distributed computing, we show the following, where n denotes the number of vertices, γ the maximum degree, and c is some universal constant independent of n and γ: (a) Any deterministic algorithm requires \Omega (min\{ logγ β log logγ, logγ n\}) rounds for all β \leq c \c. min\{ √{} logγ log logγ, logγ n\}. By optimizing γ, this implies a deterministic lower bound of \Omega (√{} log n β log log n) for all β \leq c 3 √{} log n log log n. (b) Any randomized algorithm requires \Omega (min\{ logγ β log logγ, logγ log n\}) rounds for all β \leq c \c. min\{ √{} logγ log logγ, logγ log n\}. By optimizing γ, this implies a randomized lower bound of \Omega (√{} log log n β log log log n) for all β \leq c 3 √{} log log n log log log n. For β > 1, this improves on the previously best lower bound of \Omega (log\ast n) rounds that follows from the 30-yearold bounds of Linial [SIAM J. Comput., 21(1992), pp. 193--201] and Naor [SIAM J. Discrete Math., 4(1991), pp. 409--412] (resp., \Omega (1) rounds if β \in \omega (log\ast n)). For β = 1, i.e., for the problem of computing a maximal independent set (which is nothing else than a (2, 1)-ruling set), our results improve on the previously best lower bound of \Omega (log\ast n) on trees, as our bounds already hold on trees. For the maximal independent set on general graphs, a deterministic lower bound of \Omega (min\{ γ, logγ n\}) and a randomized lower bound of \Omega (min\{ γ, logγ log n\}) were already known due to Balliu et al. [Proceedings of FOCS, 2019, pp. 481--497]. [ABSTRACT FROM AUTHOR]

A complete description of trees with maximal possible number of maximum independent sets among all n-vertex trees with exactly l leaves is obtained. For all values of the parameters n and l the extremal tree is unique and is the result of merging the endpoints of l simple paths. [ABSTRACT FROM AUTHOR]

A graph G is well-covered if all its maximal independent sets are of the same cardinality. Assume that a weight function w is defined on its vertices. Then G is w well-covered if all maximal independent sets are of the same weight. For every graph G , the set of weight functions w such that G is w -well-covered is a vector space, denoted as WCW(G). Deciding whether an input graph G is well-covered is co-NP-complete. Therefore, finding WCW(G) is co-NP-hard. A generating subgraph of a graph G is an induced complete bipartite subgraph B of G on vertex sets of bipartition B X and B Y , such that each of S ∪ B X and S ∪ B Y is a maximal independent set of G , for some independent set S. If B is generating, then w (B X) = w (B Y) for every weight function w ∈ W C W (G). Therefore, generating subgraphs play an important role in finding WCW(G). The decision problem whether a subgraph of an input graph is generating is known to be NP-complete. In this article we prove NP- completeness of the problem for graphs without cycles of length 3 and 5, and for bipartite graphs with girth at least 6. On the other hand, we supply polynomial algorithms for recognizing generating subgraphs and finding WCW(G), when the input graph is bipartite without cycles of length 6. We also present a polynomial algorithm which finds WCW(G) when G does not contain cycles of lengths 3, 4, 5, and 7. [ABSTRACT FROM AUTHOR]

Interference in femtocells due to neighboring femtocells and macrocells is a major issue of two-tier networks. Handover should be made to reduce interference, if and only if, when resources are available. Otherwise, it will further degrade network performance. Resource management should be made in an efficient manner that will not cause interference between macrocells and neighboring femtocells. Since distance between macro base station (MBS) and femto access point (FAP) is short, therefore, it is very hard to sustain low handover probability when macro user moves from MBS to FAP. We proposed handover algorithm for uplink co-channel interference mitigation that will make handover decision on the basis of time-to-stay and signal to interference plus noise ratio thresholds along with efficient resource management mechanism to reduce number of handovers and also resolve interference problem. [ABSTRACT FROM AUTHOR]

For any n, in the set of n-vertex trees such that any two leaves have no common adjacent vertex, we describe the trees with the smallest number of maximal independent sets. [ABSTRACT FROM AUTHOR]

Many randomized algorithms can be derandomized efficiently using either the method of conditional expectations or probability spaces with low independence. A series of papers, beginning with work by Luby (1988), showed that in many cases these techniques can be combined to give deterministic parallel (NC) algorithms for a variety of combinatorial optimization problems, with low time- and processor-complexity. We extend and generalize a technique of Luby for efficiently handling bilinear objective functions. One noteworthy application is an NC algorithm for maximal independent set. On a graph G with m edges and n vertices, this takes O~(log2n) time and (m+n)no(1) processors, nearly matching the best randomized parallel algorithms. Other applications include reduced processor counts for algorithms of Berger (SIAM J Comput 26:1188-1207, 1997) for maximum acyclic subgraph and Gale-Berlekamp switching games. This bilinear factorization also gives better algorithms for problems involving discrepancy. An important application of this is to automata-fooling probability spaces, which are the basis of a notable derandomization technique of Sivakumar (In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), pp 619-626, 2002). Our method leads to large reduction in processor complexity for a number of derandomization algorithms based on automata-fooling, including set discrepancy and the Johnson-Lindenstrauss Lemma. [ABSTRACT FROM AUTHOR]

Highlights • We propose a maximal independent set algorithm for wireless sensor networks. • The proposed algorithm is fully distributed and self-stabilizing. • The upper bound of the move count is max {3 n − 6 , 2 n − 1 } (n is the node count) and 1.3 moves per node in the average case for random graphs. • We provide theoretical analysis for proof of correctness and average move count. • The proposed algorithm is compared with the previous work through extensive testbed experiments and simulations. Abstract Maximal independent set (MIS) is a very important structure that provides data aggregation, topology control and routing for wireless sensor networks (WSNs). Energy-efficient and fault-tolerant construction of MIS on WSNs is one of the vital tasks. A distributed sensor network is self-stabilizing if it can initially start at any state and regain a legal state in a finite time without any external intervention. Self-stabilization is a considerable method to provide fault tolerance in WSNs. This paper presents a distributed self-stabilizing MIS algorithm which is an improved version of Turau's algorithm under a fully distributed scheduler for WSNs. The proposed algorithm is theoretically analyzed and evaluated with its counterparts. The proposed algorithm is compared with the other studies through testbed experiments on IRIS nodes and simulations on TOSSIM environment. It is shown that the proposed algorithm outperforms other algorithms in terms of move count and energy consumption. [ABSTRACT FROM AUTHOR]

We present a short inductive proof of Brooks' Theorem. [ABSTRACT FROM AUTHOR]

Finding the maximum number of maximal independent sets in an n -vertex graph G , i ( G ) , from a restricted class is an extensively studied problem. Let k K 2 denote the matching of size k , that is a graph with 2 k vertices and k disjoint edges. A graph with an induced copy of k K 2 contains at least 2 k maximal independent sets. The other direction was established in a series of papers (Farber, 1989; Balas and Yu, 1989; Farber, 1993) finally yielding i ( G ) ≤ ( n ∕ k ) 2 k for a graph G without an induced ( k + 1 ) K 2 . Alekseev proved in Alekseev (2007) that i ( G ) is at most the number of induced matchings of G . This work generalises the aforementioned results to clutters. The right substructures in this setting are minors rather than induced subgraphs. Maximal independent sets of a clutter H are in one-to-one correspondence to the sets of its blocker, b ( H ) , hence i ( H ) = | b ( H ) | . We show that | b ( H ) | ≤ ∑ m = 0 k ⋅ f ( r ) | H | m r 2 m for a ( k + 1 ) K 2 -minor-free clutter H where f ( r ) = ( 2 r − 3 ) 2 r − 2 and r is the maximum size of a set in H . A key step in the proofs is, similarly to Alekseev’s result, showing that i ( H ) is bounded by the number of a substructure called semi-matching, and then proving a dependence between the number of semi-matchings and the number of minor matchings. Note that similarly to graphs, a clutter containing a k K 2 minor has at least 2 k maximal independent sets. From a computational perspective, a polynomial number of independent sets is particularly interesting. Our results lead to polynomial algorithms for restricted instances of many problems including Set Cover and k -SAT. [ABSTRACT FROM AUTHOR]

A graph G is well-covered if all its maximal independent sets are of the same cardinality. Assume that a weight function w is defined on its vertices. Then G is w-well-covered if all maximal independent sets are of the same weight. For every graph G, the set of weight functions w such that G is w-well-covered is a vector space, denoted WCW(G). Let B be a complete bipartite induced subgraph of G on vertex sets of bipartition BX and BY. Then B is generating if there exists an independent set S such that S∪BX and S∪BY are both maximal independent sets of G. In the restricted case that a generating subgraph B is isomorphic to K1,1, the unique edge in B is called a relating edge. Deciding whether an input graph G is well-covered is co-NP-complete. Therefore finding WCW(G) is co-NP-hard. Deciding whether an edge is relating is NP-complete. Therefore, deciding whether a subgraph is generating is NP-complete as well. In this article we discuss the connections among these problems, provide proofs for NP-completeness for several restricted cases, and present polynomial characterizations for some other cases. [ABSTRACT FROM AUTHOR]

We describe and count the maximal subsemigroups of many well-known transformation monoids, and diagram monoids, using a new unified framework that allows the treatment of several classes of monoids simultaneously. The problem of determining the maximal subsemigroups of a finite monoid of transformations has been extensively studied in the literature. To our knowledge, every existing result in the literature is a special case of the approach we present. In particular, our technique can be used to determine the maximal subsemigroups of the full spectrum of monoids of order- or orientation-preserving transformations and partial permutations considered by I. Dimitrova, V. H. Fernandes, and co-authors. We only present details for the transformation monoids whose maximal subsemigroups were not previously known; and for certain diagram monoids, such as the partition, Brauer, Jones, and Motzkin monoids. The technique we present is based on a specialised version of an algorithm for determining the maximal subsemigroups of any finite semigroup, developed by the third and fourth authors, and available in the Semigroups package for GAP, an open source computer algebra system. This allows us to concisely present the descriptions of the maximal subsemigroups, and to clearly see their common features. [ABSTRACT FROM AUTHOR]

An independent vertex set of a graph is a set of vertices of the graph in which no two vertices are adjacent, and a maximal independent set is one that is not a proper subset of any other independent set. In this paper we count the number of maximal independent sets of vertices on a complete rectangular grid graph. More precisely, we provide a recursive matrix-relation producing the partition function with respect to the number of vertices. The asymptotic behavior of the maximal hard square entropy constant is also provided. We adapt the state matrix recursion algorithm, recently invented by the author to answer various two-dimensional regular lattice model problems in enumerative combinatorics and statistical mechanics. [ABSTRACT FROM AUTHOR]

In future scenarios of heterogeneous and dense networks, randomly-deployed small star networks (SSNs) become a key paradigm, whose system performance is restricted to inter-SSN interference and requires an efficient resource allocation scheme for interference coordination. Traditional resource allocation schemes do not specifically focus on this paradigm and are usually too time consuming in dense networks. In this article, a very efficient graph-based scheme is proposed, which applies the maximal independent set (MIS) concept in graph theory to help divide SSNs into almost interference-free groups. We first construct an interference graph for the system based on a derived distance threshold indicating for any pair of SSNs whether there is intolerable inter-SSN interference or not. Then, SSNs are divided into MISs, and the same resource can be repetitively used by all the SSNs in each MIS. Empirical parameters and equations are set in the scheme to guarantee high performance. Finally, extensive scenarios both dense and nondense are randomly generated and simulated to demonstrate the performance of our scheme, indicating that it outperforms the classical max K-cut-based scheme in terms of system capacity, utility and especially time cost. Its achieved system capacity, utility and fairness can be close to the near-optimal strategy obtained by a time-consuming simulated annealing search. [ABSTRACT FROM AUTHOR]

The paper is concerned with the asymptotic behaviour of the number mi(Tq,n) of maximal independent sets in a complete q-ary tree of height n. For some constants α2 and β2 The asymptotic formula mi(T2,n) ~ α2⋅(β2)2n is shown to hold as n → ∞. It is also proved that mi(Tq,3k) ..., mi(Tq,3k+1) ... ask →∞ for any sufficiently Large q, some three pairwise distinct constants α(1)q, α(3)q and a constant bq. [ABSTRACT FROM AUTHOR]

Given a graph G , viewed as a loop-less symmetric digraph, we study the maximum number of fixed points in a conjunctive boolean network with G as interaction graph. We prove that if G has no induced C 4 , then this quantity equals both the number of maximal independent sets in G and the maximum number of maximal independent sets among all the graphs obtained from G by contracting some edges. We also prove that, in the general case, it is coNP-hard to decide if one of these equalities holds, even if G has a unique induced C 4 . [ABSTRACT FROM AUTHOR]

Let G be a graph. A set S of vertices in G dominates the graph if every vertex of G is either in S or a neighbor of a vertex in S . Finding a minimum cardinality set which dominates the graph is an NP -complete problem. The graph G is well-dominated if all its minimal dominating sets are of the same cardinality. The complexity status of recognizing well-dominated graphs is not known. We show that recognizing well-dominated graphs can be done polynomially for graphs without cycles of lengths 4 and 5 , by proving that a graph belonging to this family is well-dominated if and only if it is well-covered. Assume that a weight function w is defined on the vertices of G . Then G is w -well-dominated if all its minimal dominating sets are of the same weight. We prove that the set of weight functions w such that G is w -well-dominated is a vector space, and denote that vector space by W W D ( G ) . We show that W W D ( G ) is a subspace of W C W ( G ) , the vector space of weight functions w such that G is w -well-covered. We provide a polynomial characterization of W W D ( G ) for the case that G does not contain cycles of lengths 4 , 5 , and 6 . [ABSTRACT FROM AUTHOR]

Integrity constraint based data repairing is an iterative process consisting of two parts: detect and group errors that violate given integrity constraints (ICs); and modify values inside each group such that the modified database satisfies those ICs. However, most existing automatic solutions treat the process of detecting and grouping errors straightforwardly (e.g., violations of functional dependencies using string equality), while putting more attention on heuristics of modifying values within each group. In this paper, we propose a revised semantics of violations and data consistency w.r.t. a set of ICs. The revised semantics relies on string similarities, in contrast to traditional methods that use syntactic error detection using string equality. Along with the revised semantics, we also propose a new cost model to quantify the cost of data repair by considering distances between strings. We show that the revised semantics provides a significant change for better detecting and grouping errors, which in turn improves both precision and recall of the following data repairing step. We prove that finding minimum-cost repairs in the new model is NP-hard, even for a single FD. We devise efficient algorithms to find approximate repairs. In addition, we develop indices and optimization techniques to improve the efficiency. Experiments show that our approach significantly outperforms existing automatic repair algorithms in both precision and recall. [ABSTRACT FROM AUTHOR]

A graph G is said to be well-covered if every maximal independent set of vertices has the same cardinality. A plane (simple) graph in which each face is a triangle is called a (plane) triangulation . In the first of a sequence of three papers the authors proved that there are no 5-connected plane well-covered triangulations. Clearly, the only plane triangulation which is exactly 2-connected is the triangle K 3 . Two subsequent papers culminated in the proof that there are exactly four well-covered plane triangulations which are exactly 4-connected. It is the aim of the present paper to complete the characterization of well-covered plane triangulations by characterizing the infinite family of those well-covered triangulations of the plane which are exactly 3-connected. [ABSTRACT FROM AUTHOR]

A maximal independent set is an independent set that is not a proper subset of any other independent set. In this paper, we determine the third largest number of maximal independent sets among all graphs of order $$n\geqslant 3$$ and identify the corresponding extremal graphs. [ABSTRACT FROM AUTHOR]

In this paper, we give a silent self-stabilizing algorithm for constructing a k -clustering of any asynchronous connected network with unique IDs. Our algorithm stabilizes in O ( n ) rounds, using O ( log ⁡ k + log ⁡ n ) space per process, where n is the number of processes. In the general case, our algorithm constructs O ( n k ) k -clusters. If the network is a Unit Disk Graph (UDG), then our algorithm is 7.2552 k + O ( 1 ) - competitive , that is, the number of k -clusters constructed by the algorithm is at most 7.2552 k + O ( 1 ) times the minimum possible number of k -clusters in any k -clustering of the same network. More generally, if the network is an Quasi-Unit Disk Graph (QUDG) with approximation ratio λ , then our algorithm is 7.2552 λ 2 k + O ( λ ) - competitive . In case of tree networks, our algorithm computes a k -clustering with the minimum number of clusters. Our solution is based on the self-stabilizing construction of a data structure called an MIS tree , a spanning tree of the network whose processes at even levels form a maximal independent set of the network. The MIS tree construction we use (called LFMIS) is the time bottleneck of our k -clustering algorithm, as it takes Θ ( n ) rounds in the worst case, while the rest of the algorithm takes O ( D ) rounds, where D is the diameter of the network. We would like to improve that time to be O ( D ) , but we show that our distributed MIS tree construction is a P -complete problem. [ABSTRACT FROM AUTHOR]

A clutter (or antichain or Sperner family) L is a pair (V,E), where V is a finite set and E is a family of subsets of V none of which is a subset of another. Usually, the elements of V are called vertices of L, and the elements of E are called edges of L. A subset se of an edge e of a clutter is called recognizing for e, if se is not a subset of another edge. The hardness of an edge e of a clutter is the ratio of the size of e's smallest recognizing subset to the size of e. The hardness of a clutter is the maximum hardness of its edges. We study the hardness of clutters arising from independent sets and matchings of graphs. [ABSTRACT FROM AUTHOR]

A theorem of Ore [20] states that if D is a minimal dominating set in a graph G = ( V , E ) having no isolated nodes, then V − D is a dominating set. It follows that such graphs must have two disjoint minimal dominating sets R and B . We describe a self-stabilizing algorithm for finding such a pair of sets. It also follows from Ore's theorem that in a graph with no isolates, one can find disjoint sets R and B where R is maximal independent and B is minimal dominating. We describe a self-stabilizing algorithm for finding such a pair. Both algorithms are described using the Distance-2 model, but can be converted to the usual Distance-1 model [7] , yielding running times of O ( n 2 m ) . [ABSTRACT FROM AUTHOR]

We prove that given a bipartite graph G with vertex set V and an integer k, deciding whether there exists a subset of V of size at most k hitting all maximal independent sets of G is complete for the class $\varSigma_{2}^{\mathrm{P}}$. [ABSTRACT FROM AUTHOR]

A graph G is well-covered if all its maximal independent sets are of the same cardinality. Assume that a weight function w is defined on its vertices. Then G is w -well-covered if all maximal independent sets are of the same weight. For every graph G , the set of weight functions w such that G is w -well-covered is a vector space . Given an input claw-free graph G , we present an O ( m 3 2 n 3 ) algorithm, whose input is a claw-free graph G , and output is the vector space of weight functions w , for which G is w -well-covered. A graph G is equimatchable if all its maximal matchings are of the same cardinality. Assume that a weight function w is defined on the edges of G . Then G is w -equimatchable if all its maximal matchings are of the same weight. For every graph G , the set of weight functions w such that G is w -equimatchable is a vector space. We present an O ( m ⋅ n 4 + n 5 log n ) algorithm, which receives an input graph G , and outputs the vector space of weight functions w such that G is w -equimatchable. [ABSTRACT FROM AUTHOR]

We show that the maximum number of different sizes of maximal complete k -partite induced subgraphs of a graph G of sufficiently large order n is at least ( n − k + 1 ) − log 2 ( n − k + 1 ) − 4 and at most n − ⌊ log 2 ( n k ! ) ⌋ . We analyze some features of the structure of graphs with the maximum possible number of different sizes of maximal independent sets, and give best-possible estimates for K 1 , k -free graphs and regular graphs. [ABSTRACT FROM AUTHOR]

Abstract: We are interested in the number of fixed points in AND–OR–NOT networks, i.e. Boolean networks in which the update function of each component is either a conjunction or a disjunction of positive or negative literals. As the main result, we prove that the maximum number of fixed points in a loop-less connected AND–OR–NOT network with n components is at most the maximum number of maximal independent sets in a loop-less connected graph with n vertices, a quantity already known. [Copyright &y& Elsevier]

Data Gathering is a fundamental task in Wireless Sensor Networks (WSNs). Data gathering trees capable of performing aggregation operations are also referred to as Data Aggregation Trees (DATs). Currently, most of the existing works focus on constructing DATs according to different user requirements under the Deterministic Network Model (DNM). However, due to the existence of many probabilistic lossy links in WSNs, it is more practical to obtain a DAT under the realistic Probabilistic Network Model (PNM). Moreover, the load-balance factor is neglected when constructing DATs in current literatures. Therefore, in this paper, we focus on constructing a Load-Balanced Data Aggregation Tree (LBDAT) under the PNM. More specifically, three problems are investigated, namely, the Load-Balanced Maximal Independent Set (LBMIS) problem, the Connected Maximal Independent Set (CMIS) problem, and the LBDAT construction problem. LBMIS and CMIS are well-known NP-hard problems and LBDAT is an NP-complete problem. Consequently, approximation algorithms and comprehensive theoretical analysis of the approximation factors are presented in the paper. Finally, our simulation results show that the proposed algorithms outperform the existing state-of-the-art approaches significantly. [ABSTRACT FROM AUTHOR]

In this paper we study the problem of building a constant-degree connected dominating set (CCDS), a network structure that can be used as a communication backbone, in the dual graph radio network model (Clementi et al. in J Parallel Distrib Comput 64:89-96, ; Kuhn et al. in Proceedings of the international symposium on principles of distributed computing , Distrib Comput 24(3-4):187-206 , Proceedings of the international symposium on principles of distributed computing ). This model includes two types of links: reliable, which always deliver messages, and unreliable, which sometimes fail to deliver messages. Real networks compensate for this differing quality by deploying low-layer detection protocols to filter unreliable from reliable links. With this in mind, we begin by presenting an algorithm that solves the CCDS problem in the dual graph model under the assumption that every process $$u$$ is provided with a local link detector set consisting of every neighbor connected to $$u$$ by a reliable link. The algorithm solves the CCDS problem in $$O\left( \frac{\varDelta \log ^2{n}}{b} + \log ^3{n}\right) $$ rounds, with high probability, where $$\varDelta $$ is the maximum degree in the reliable link graph, $$n$$ is the network size, and $$b$$ is an upper bound in bits on the message size. The algorithm works by first building a Maximal Independent Set (MIS) in $$\log ^3{n}$$ time, and then leveraging the local topology knowledge to efficiently connect nearby MIS processes. A natural follow-up question is whether the link detector must be perfectly reliable to solve the CCDS problem. With this in mind, we first describe an algorithm that builds a CCDS in $$O(\varDelta $$ polylog $$(n))$$ time under the assumption of $$O(1)$$ unreliable links included in each link detector set. We then prove this algorithm to be (almost) tight by showing that the possible inclusion of only a single unreliable link in each process's local link detector set is sufficient to require $$\varOmega (\varDelta )$$ rounds to solve the CCDS problem, regardless of message size. We conclude by discussing how to apply our algorithm in the setting where the topology of reliable and unreliable links can change over time. [ABSTRACT FROM AUTHOR]

Abstract: A graph is well-covered if all its maximal independent sets have the same order. For a well-covered graph of order without an isolated vertex, Claude Berge (C. Berge, Some common properties for regularizable graphs, edge-critical graphs and -graphs, Ann. Discrete Math. 12 (1982) 31–44) proved that the independence number of is at most . The extremal graphs for this result are known as the very well-covered graphs and were characterized by Odile Favaron (O. Favaron, Very well-covered graphs, Discrete Math. 42 (1982) 177–187). We extend these two results in two different ways. First, we study the structure and recognition of the well-covered graphs without an isolated vertex that have independence number for some non-negative integer . For , we give a complete structural description of these graphs, and for a general but fixed , we describe a polynomial time recognition algorithm. Second, we relax the condition of well-coveredness and consider graphs without an isolated vertex for which the independence number and the independent domination number satisfy for some non-negative integer . We prove a suitable version of Berge’s result for these graphs, derive an upper bound on the independence number as a corollary, and discuss its relation to Favaron’s characterization. [Copyright &y& Elsevier]

We describe several classes of finite, planar Toeplitz graphs and present results on their chromatic number. We then turn to counting maximal independent sets in these graphs and determine recurrence equations and generating functions for some special cases. [ABSTRACT FROM AUTHOR]

Abstract: We prove that for integers and with and , there are only finitely many connected graphs of minimum degree at least 2, maximum degree at most , and girth at least 7 that have maximal independent sets of at most different sizes. Furthermore, we prove several results restricting the degrees of such graphs. Our contributions generalize known results on well-covered graphs. [Copyright &y& Elsevier]

We consider the problem of computing a maximal independent set (MIS) in an extremely harsh broadcast model that relies only on carrier sensing. The model consists of an anonymous broadcast network in which nodes have no knowledge about the topology of the network or even an upper bound on its size. Furthermore, it is assumed that an adversary chooses at which time slot each node wakes up. At each time slot a node can either beep, that is, emit a signal, or be silent. At a particular time slot, beeping nodes receive no feedback, while silent nodes can only differentiate between none of its neighbors beeping, or at least one of its neighbors beeping. We start by proving a lower bound that shows that in this model, it is not possible to locally converge to an MIS in sub-polynomial time. We then study four different relaxations of the model which allow us to circumvent the lower bound and find an MIS in polylogarithmic time. First, we show that if a polynomial upper bound on the network size is known, it is possible to find an MIS in $$\mathcal O (\log ^3 n)$$ time. Second, if we assume sleeping nodes are awoken by neighboring beeps, then we can also find an MIS in $$\mathcal O (\log ^3 n)$$ time. Third, if in addition to this wakeup assumption we allow sender-side collision detection, that is, beeping nodes can distinguish whether at least one neighboring node is beeping concurrently or not, we can find an MIS in $$\mathcal O (\log ^2 n)$$ time. Finally, if instead we endow nodes with synchronous clocks, it is also possible to find an MIS in $$\mathcal O (\log ^2 n)$$ time. [ABSTRACT FROM AUTHOR]

Abstract: Several familiar problems in extremal set theory can be cast as questions about the maximum possible size of an independent set defined on a suitable graph, about the total number of independent sets in such graphs, or about enumeration of the maximal independent sets. Here we find bounds on the number of maximal independent sets in the covering graph of a hypercube. [Copyright &y& Elsevier]

For a given positive integer t we consider graphs having maximal independent sets of precisely t distinct cardinalities and restrict our attention to those that have no vertices of degree one. In the situation when t is four or larger and the length of the shortest cycle is at least 6 t − 6, we completely characterize such graphs. [ABSTRACT FROM AUTHOR]

Abstract: Every graph contains a minimum vertex-coloring with the property that at least one color class of the coloring is a maximal independent set (equivalently, a dominating set) in . Among all such minimum vertex-colorings of the vertices of , a coloring with the maximum number of color classes that are dominating sets in is called a dominating--coloring of . The number of color classes that are dominating sets in a dominating--coloring of is defined to be the dominating--color number of . In this paper, we continue to investigate the dominating--color number of a graph first defined and studied in . [Copyright &y& Elsevier]

We present a novel distributed algorithm for the maximal independent set problem (This is an extended journal version of Schneider and Wattenhofer in Twenty-seventh annual ACM SIGACT-SIGOPS symposium on principles of distributed computing, 2008). On bounded-independence graphs our deterministic algorithm finishes in O(log* n) time, n being the number of nodes. In light of Linial’s Ω(log* n) lower bound our algorithm is asymptotically optimal. Furthermore, it solves the connected dominating set problem for unit disk graphs in O(log* n) time, exponentially faster than the state-of-the-art algorithm. With a new extension our algorithm also computes a δ + 1 coloring and a maximal matching in O(log* n) time, where δ is the maximum degree of the graph. [ABSTRACT FROM AUTHOR]

Abstract: A graph is said to be well-covered if every maximal independent set of vertices has the same cardinality. A planar (simple) graph in which each face is a triangle is called a triangulation. It was proved in an earlier paper Finbow et al. (2004) that there are no 5-connected planar well-covered triangulations, and in Finbow et al. (submitted for publication) that there are exactly four 4-connected well-covered triangulations containing two adjacent vertices of degree 4. It is the aim of the present paper to complete the characterization of 4-connected well-covered triangulations by showing that each such graph contains two adjacent vertices of degree 4. [Copyright &y& Elsevier]

Abstract: People arrive one at a time to a theater consisting of rows of length . Being unfriendly they choose seats at random so that no one is in front of them, behind them or to either side. What is the expected number of people in the theater when it becomes full, i.e., it cannot accommodate any more unfriendly people? This is equivalent to the random process of generating a maximal independent set of an grid by randomly choosing a node, removing it and its neighbors, and repeating until there are no nodes remaining. The case of was posed by Freedman and Shepp [D. Freedman, L. Shepp, An unfriendly seating arrangement (problem 62-3), SIAM Rev. 4 (2) (1962) 150] and solved independently by Friedman, Rothman and MacKenzie [H.D. Friedman, D. Rothman, Solution to: An unfriendly seating arrangement (problem 62-3), SIAM Rev. 6 (2) (1964) 180–182; J.K. MacKenzie, Sequential filling of a line by intervals placed at random and its application to linear adsorption, J. Chem. Phys. 37 (4) (1962) 723–728] by proving the asymptotic limit . In this paper we solve the case and prove the asymptotic limit . In addition, we consider the more general case of grids, , and prove the existence of asymptotic limits in this general setting. We also make several conjectures based upon Monte Carlo simulations. [Copyright &y& Elsevier]

Abstract: A maximal independent set is an independent set that is not a proper subset of any other independent set. In this paper, we determine the second largest number of maximal independent sets among all trees and forests of order n≥4. We also characterize those extremal graphs achieving these values. [Copyright &y& Elsevier]