Explicit construction of linear sized tolerant networks

DOI10.1016/0012-365X(88)90189-6zbMath0657.05068OpenAlexW1998400388WikidataQ105583521 ScholiaQ105583521MaRDI QIDQ1110541

Publication date: 1988

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(88)90189-6

zbMATH Keywords

minimum number construction of graphs fault tolerant linear arrays path of length m

Mathematics Subject Classification ID

Paths and cycles (05C38) Generalized Ramsey theory (05C55) Graph theory (05C99)

Related Items

Expansion in matrix-weighted graphs, Percolation on finite graphs and isoperimetric inequalities., Inverse expander mixing for hypergraphs, Sharp spectral bounds of several graph parameters using eigenvector norms, Embedding graphs with bounded degree in sparse pseudorandom graphs, Expanding graphs contain all small trees, Eigenvalues of Cayley graphs, Expander Construction in VNC1, Efficient parallel computing with memory faults, Expanders and time-restricted branching programs, Tough Ramsey graphs without short cycles, On the number of matroids, Pioneering the Establishment of the Foundations of the Internet of Things, Hitting Time of Edge Disjoint Hamilton Cycles in Random Subgraph Processes on Dense Base Graphs, Symmetric unique neighbor expanders and good LDPC codes, T-SNE, forceful colorings, and mean field limits, Finite Field Kakeya and Nikodym Sets in Three Dimensions, The complexity and approximability of finding maximum feasible subsystems of linear relations, Isoperimetric inequalities in simplicial complexes, Largest component and node fault tolerance for grids, Rolling backwards can move you forward: On embedding problems in sparse expanders, Unnamed Item, On the spectrum of dense random geometric graphs, Constructive bounds for a Ramsey-type problem, The Erdős matching conjecture and concentration inequalities, $k$-planar crossing number of random graphs and random regular graphs, Explicit expanding expanders, Constructing cospectral graphs via a new form of graph product, On sensitivity in bipartite Cayley graphs, On the Size-Ramsey Number of Tight Paths, On an anti‐Ramsey property of Ramanujan graphs, Spectrum and combinatorics of two-dimensional Ramanujan complexes, Pseudorandom generators for combinatorial checkerboards, Expander construction in $\mathrm{VNC}^1$, Fractional and circular separation dimension of graphs, A note on eigenvalue bounds for independence numbers of non-regular graphs, Tighter spectral bounds for the cut size, based on Laplacian eigenvectors, Discrepancy inequalities for directed graphs, Structure and supersaturation for intersecting families, On distinct perpendicular bisectors and pinned distances in finite fields, The size Ramsey number of a directed path, On rigid matrices and $U$-polynomials, The number of additive triples in subsets of abelian groups, On the derandomization of the graph test for homomorphism over groups, Expander graphs and their applications, The multicolour size-Ramsey number of powers of paths, Fighting constrained fires in graphs, Randomized Rumour Spreading: The Effect of the Network Topology, An Alternative Proof of the Linearity of the Size-Ramsey Number of Paths, Mixing in High-Dimensional Expanders, Local spectral expansion approach to high dimensional expanders. II: Mixing and geometrical overlapping, A lower bound on the area of permutation layouts, Sparse networks tolerating random faults., On the automorphism groups of strongly regular graphs. II., Generalized transversals, generalized vertex covers and node-fault-tolerance in graphs, Cleaning random $d$-regular graphs with brooms, Toughness in pseudo-random graphs, Lovász, Vectors, Graphs and Codes, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, FORCING QUASIRANDOMNESS WITH TRIANGLES, Modular Orientations of Random and Quasi-Random Regular Graphs, On the number of alternating paths in random graphs, Quasi-random graphs, Lower bounds for tropical circuits and dynamic programs, Explicit expanders of every degree and size, Spectral bounds for the $k$-independence number of a graph, Lower bounds of size Ramsey number for graphs with small independence number, The Grothendieck constant of random and pseudo-random graphs, Unimodular graphs and Eisenstein sums, The size-Ramsey number of 3-uniform tight paths, Eigenvalues and expansion of bipartite graphs, Doing-it-all with bounded work and communication, Intersecting families of discrete structures are typically trivial, Counting sum-free sets in abelian groups, A note on the Size-Ramsey number of long subdivisions of graphs, Unnamed Item, Regular pairs in sparse random graphs I, Quasirandomness in hypergraphs, The size-Ramsey number of trees, Additive patterns in multiplicative subgroups, Recent progress on graphs with fixed smallest adjacency eigenvalue: a survey, Minimum $k$-critical bipartite graphs, Graphs with average degree smaller than $\frac{30}{11}$ burn slowly, Distributed Corruption Detection in Networks, Discrepancy and eigenvalues of Cayley graphs, Incidence Bounds for Block Designs, A Proof of Brouwer's Toughness Conjecture, Expander graphs in pure and applied mathematics, Clique-factors in sparse pseudorandom graphs, Trace of Products in Finite Fields from a Combinatorial Point of View, Rainbow matchings in k‐partite hypergraphs, Products of Differences over Arbitrary Finite Fields, Derandomized graph products, The size‐Ramsey number of powers of bounded degree trees, The Size Ramsey Number of Graphs with Bounded Treewidth, Efficient gossip and robust distributed computation, Counting independent sets in graphs, On monoid graphs, On the number of union-free families, Finding any given 2‐factor in sparse pseudorandom graphs efficiently, Algebraic and combinatorial expansion in random simplicial complexes, Reliable Spanners for Metric Spaces, The spectral gap of random regular graphs, Extremal Problem for Matchings and Rainbow Matchings on Direct Products, Making an H $H$‐free graph k $k$‐colorable, Graph rigidity properties of Ramanujan graphs, The Spectrum of Triangle-Free Graphs, Turán‐type problems for long cycles in random and pseudo‐random graphs, The asymptotics of $r(4,t)$

Cites Work