Optimal numberings and isoperimetric problems on graphs
From MaRDI portal
Publication:5541108
DOI10.1016/S0021-9800(66)80059-5zbMath0158.20802WikidataQ30053684 ScholiaQ30053684MaRDI QIDQ5541108
Publication date: 1966
Published in: Journal of Combinatorial Theory (Search for Journal in Brave)
Related Items
On Sums of Generating Sets in ℤ2n, A Result on the Strength of Graphs by Factorizations of Complete Graphs, Bi-Lipschitz bijection between the Boolean cube and the Hamming ball, An Isoperimetric Theorem on the Cube and the Kintchine-Kahane Inequalities, On semidefinite programming bounds for graph bandwidth, Crux and Long Cycles in Graphs, On Type of Metric Spaces, Congestion optimale du plongement de l’hypercube $H (n)$ dans la chaîne $P(2^n)$, Local Expansion of Symmetrical Graphs, A new approach to finding the extra connectivity of graphs, Treewidth of Cartesian Products of Highly Connected Graphs, Minimum Linear Arrangement of the Cartesian Product of Optimal Order Graph and Path, Discrepancies of spanning trees and Hamilton cycles, Walker-Breaker Games, Lower bounds for the bandwidth problem, Graph layout problems, Unnamed Item, Tighter spectral bounds for the cut size, based on Laplacian eigenvectors, The maximum linear arrangement problem for trees under projectivity and planarity, Shotgun reconstruction in the hypercube, Efficient parallel algorithms for some tree layout problems, The boundary of a graph and its isoperimetric inequality, Expansion of random 0/1 polytopes, When Are Fuzzy Extractors Possible?, An extremal graph problem on a grid and an isoperimetric problem for polyominoes, Some remarks on the Erdős Distinct subset sums problem, Homomorphisms from the torus, A lower bound for the vertex boundary-width of complete \(k\)-ary trees, Isoperimetric Problem and Meta-fibonacci Sequences, Minimising the total number of subsets and supersets, Shadows of ordered graphs, An isoperimetric inequality for the Hamming cube and some consequences, An Inequality for Functions on the Hamming Cube, The Proofs of Two Directed Paths Conjectures of Bollobás and Leader, Polynomial-time targeted attacks on coin tossing for any number of corruptions, RATE OF PARITY VIOLATION FROM MEASURE CONCENTRATION, Bandwidth of the product of paths of the same length, Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile, On bandwidth, cutwidth, and quotient graphs, Improved Bound for Dilation of an Embedding onto Circulant Networks, Lipschitz subtype, Efficient Connectivity Testing of Hypercubic Networks with Faults, Comparison of Metric Spectral Gaps, Isoperimetry in integer lattices, The sub-Gaussian constant and concentration inequalities, On diagnosability of large multiprocessor networks, On diagnosability of large multiprocessor networks, Efficient embeddings of grids into grids, The vertex isoperimetric problem for the powers of the diamond graph, On dominated \(\ell_1\) metrics, On Kruskal's cascades and counting containments in a set of subsets, Forbidden Intersections, On the edge-bandwidth of graph products, The carvingwidth of hypercubes, Storage representations for tree-like data structures, On Harpers' Result Concerning the Bandwidths of Graphs, Linear layout of directed grid graph, An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube, Minimum linear arrangement of chord graphs, On Eulerian orientations of even-degree hypercubes, Uniqueness in Harper's vertex-isoperimetric theorem, Vertex-isoperimetric stability in the hypercube, A Kruskal-Katona type result and applications, Bounds on the costs of data encodings, Interactive Communication, Diagnosis and Error Control in Networks, On theorems of Wirsing and Sanders, Phase transitions in phylogeny, Optimal Numberings of an $N \times N$ Array, A Variable Neighbourhood Search approach to the Cutwidth Minimization Problem, New bounds on the edge-bandwidth of triangular grids, Crossing patterns of semi-algebraic sets, A Note on the Erdös Distinct Subset Sums Problem, On attractive and friendly sets in sequence spaces, On the bandwidth of the Kneser graph, The treewidth and pathwidth of hypercubes, Planar lattice subsets with minimal vertex boundary, Lower bounds on the competitive ratio for mobile user tracking and distributed job scheduling, A survey of the modified Moran process and evolutionary graph theory, A problem of Shapozenko on Johnson graphs, Hunting rabbits on the hypercube, Vertex ordering and partitioning problems for random spatial graphs., Union of shadows, New results on edge-bandwidth, The bandwidth minimization problem for cyclic caterpillars with hair length 1 is NP-complete, A strong lower bound for approximate nearest neighbor searching, On the problem of bandsize, On the extremal combinatorics of the Hamming space, On bandwidth and edgesum for the composition of two graphs, A diagnosis algorithm by using graph-coloring under the PMC model, Generic properties of combinatory maps: Neutral networks of RNA secondary structures, Improved exact approaches for row layout problems with departments of equal length, Branch and bound for the cutwidth minimization problem, Matchings and paths in the cube, Edge-bandwidth of grids and tori, Measure concentration in optimization, Concentration of measure and isoperimetric inequalities in product spaces, On the bandwidth of convex triangulation meshes, The isoperimetric number of the incidence graph of \(\operatorname{PG}(n,q)\), Catching an infinitely fast robber on a grid, A generalization of the Katona theorem for cross t-intersecting families, A lower bound on the size of a complex generated by an antichain, Harper-type lower bounds and the bandwidths of the compositions of graphs, Shadows and isoperimetry under the sequence-subsequence relation, The structure of popular difference sets, Simple polytopes without small separators, Isoperimetry, stability, and irredundance in direct products, Dimension 1 sequences are close to randoms, Isoperimetric problem for exponential measure on the plane with \(\ell_1\)-metric, Parallel algorithms for the minimum cut and the minimum length tree layout problems, An approximate vertex-isoperimetric inequality for \(r\)-sets, Cutwidth of triangular grids, Bisection width of transposition graphs, Data encodings and their costs, Decorous combinatorial lower bounds for row layout problems, The edge-isoperimetric problem on the 600-vertex regular solid, On the bandwidth of a Hamming graph, Bandwidth of the composition of two graphs., Stability for vertex isoperimetry in the cube, Some extremal problems arising from discrete control processes, A short proof for a theorem of Harper about Hamming-spheres, Isoperimetric inequalities for faces of the cube and the grid, Exact face-isoperimetric inequalities, Largest random component of a k-cube, The global theory of paths in networks. I: Definitions, examples and limits, Foreword to the special issue ``Advances in graph labelling, On a problem of Kleitman and West, Bandwidth of graphs resulting from the edge clique covering problem, An optimal time algorithm for minimum linear arrangement of chord graphs, Optimal embedding of 2-D torus into ring, On bandwidth for the tensor product of paths and cycles, Eigenvalues of subgraphs of the cube, Subset sums in binary spaces, A general method to determine limiting optimal shapes for edge-isoperimetric inequalities, Metastability of hard-core dynamics on bipartite graphs, On the bandwidth of 3-dimensional Hamming graphs, On cross-intersecting families, Improving Beckner's bound via Hermite functions, On edge numberings of the \(n\)-cube graph, Bandwidth and pathwidth of three-dimensional grids, Optimal labelling of a product of two paths, Extremal set theory for the binomial norm, A note on Hamming spheres, The carving-width of generalized hypercubes, On embedding of a hypercube in a completely overlapping network, Multistart search for the cyclic cutwidth minimization problem, Simulation theorems via pseudo-random properties, The profile of the Cartesian product of graphs, Invitation to intersection problems for finite sets, Monotone Gray codes and the middle levels problem, Bounds on isoperimetric values of trees, Isoperimetric theorems in the binary sequences of finite lengths, On the domination search number, Antibandwidth and cyclic antibandwidth of meshes and hypercubes, On explicit formulas for bandwidth and antibandwidth of hypercubes, On minimum cuts and the linear arrangement problem, An isoperimetric inequality for Hamming balls and local expansion in hypercubes, Exponential integrability and transportation cost related to logarithmic Sobolev inequalities, The bandwidth of the complement of a \(k\)-tree, Recursive circulants and their embeddings among hypercubes, Lower bounds on treespan, Note on an extremal problem arising for unreliable networks in parallel computing, On the bandwidth of triangulated triangles, Bounding the bandwidths for graphs, Morphisms for the maximum weight ideal problem, On the area of hypercube layouts., Odd and even Hamming spheres also have minimum boundary, \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators, The bandwidth problem for distributive lattices of breadth 3, Variations on the Erdős distinct-sums problem, Maximal sets of given diameter in the grid and the torus, Compressions and isoperimetric inequalities, Isoperimetric inequalities and fractional set systems, Weight functions on the Kneser graph and the solution of an intersection problem of Sali, A general variable neighborhood search for the cyclic antibandwidth problem
