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 (only showing first 100 items - show all)

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)$ ⋮ 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

Cites Work

This page was built for publication: Explicit construction of linear sized tolerant networks