Small -dominating sets.
Small Ramsey numbers.
Smallest cubic and quartic graphs with a given number of cutpoints and bridges.
Smallest Regular Graphs of Given Degree and Diameter
In this note we present a sharp lower bound on the number of vertices in a regular graph of given degree and diameter.
Smooth and sharp thresholds for random -XOR-CNF satisfiability
The aim of this paper is to study the threshold behavior for the satisfiability property of a random -XOR-CNF formula or equivalently for the consistency of a random Boolean linear system with variables per equation. For we show the existence of a sharp threshold for the satisfiability of a random -XOR-CNF formula, whereas there are smooth thresholds for and .
Smooth and sharp thresholds for random {k}-XOR-CNF satisfiability
The aim of this paper is to study the threshold behavior for the satisfiability property of a random k-XOR-CNF formula or equivalently for the consistency of a random Boolean linear system with k variables per equation. For k ≥ 3 we show the existence of a sharp threshold for the satisfiability of a random k-XOR-CNF formula, whereas there are smooth thresholds for k=1 and k=2.
Smooth spheres in IR4 with four critical points are standard.
Sobre la representación de un conjunto mediante árboles aditivos.
En este trabajo se estudia el problema de la representación de un conjunto mediante árboles aditivos, en el sentido de hallar una formalización que permita abordar el mismo desde la perspectiva general de los métodos geométricos de representación del análisis multivariante.
Sobre un cono convexo asociado a un grafo.
En este artículo se construye un cono convexo sobre un grafo y se estudian las propiedades básicas de este cono convexo: dimensión, linealidad y sistemas minimales de generadores. El interés de esta situación tiene su origen en problemas de decisión, donde la información disponible está dada por órdenes parciales entre las componentes de la información. Sin embargo, el estudio realizado es independiente de los problemas de decisión que lo motivan.
Sofic groups are not locally embeddable into finite Moufang loops
We shall show that there exist sofic groups which are not locally embeddable into finite Moufang loops. These groups serve as counterexamples to a problem and two conjectures formulated in the paper by M. Vodička, P. Zlatoš (2019).
Sofic Systems and Graphs.
Solution of Heawood's empire problem in the plane.
Solution to a combinatorial puzzle arising from Mayer's theory of cluster integrals.
Solution to the problem of Kubesa
An infinite family of T-factorizations of complete graphs , where 2n = 56k and k is a positive integer, in which the set of vertices of T can be split into two subsets of the same cardinality such that degree sums of vertices in both subsets are not equal, is presented. The existence of such T-factorizations provides a negative answer to the problem posed by Kubesa.
Solutions and kernels of a directed graph
Solutions de tournois : un spicilège
L'article passe en revue quelques Solutions de Tournois (correspondances de choix définies sur les tournois). On compare ces solutions entre elles, et on mentionne certaines de leurs propriétés.
Solutions of Some L(2, 1)-Coloring Related Open Problems
An L(2, 1)-coloring (or labeling) of a graph G is a vertex coloring f : V (G) → Z+ ∪ {0} such that |f(u) − f(v)| ≥ 2 for all edges uv of G, and |f(u)−f(v)| ≥ 1 if d(u, v) = 2, where d(u, v) is the distance between vertices u and v in G. The span of an L(2, 1)-coloring is the maximum color (or label) assigned by it. The span of a graph G is the smallest integer λ such that there exists an L(2, 1)-coloring of G with span λ. An L(2, 1)-coloring of a graph with span equal to the span of the graph is...
Solving maximum independent set by asynchronous distributed hopfield-type neural networks
We propose a heuristic for solving the maximum independent set problem for a set of processors in a network with arbitrary topology. We assume an asynchronous model of computation and we use modified Hopfield neural networks to find high quality solutions. We analyze the algorithm in terms of the number of rounds necessary to find admissible solutions both in the worst case (theoretical analysis) and in the average case (experimental Analysis). We show that our heuristic is better than the...
Solving the Minimum Independent Domination Set Problem in Graphs by Exact Algorithm and Greedy Heuristic
In this paper we present a new approach to solve the Minimum Independent Dominating Set problem in general graphs which is one of the hardest optimization problem. We propose a method using a clique partition of the graph, partition that can be obtained greedily. We provide conditions under which our method has a better complexity than the complexity of the previously known algorithms. Based on our theoretical method, we design in the second part of this paper an efficient algorithm by including...
Some additions to the theory of star partitions of graphs
This paper contains a number of results in the theory of star partitions of graphs. We illustrate a variety of situations which can arise when the Reconstruction Theorem for graphs is used, considering in particular galaxy graphs - these are graphs in which every star set is independent. We discuss a recursive ordering of graphs based on the Reconstruction Theorem, and point out the significance of galaxy graphs in this connection.