scientific article; zbMATH DE number 3598234
From MaRDI portal
Publication:4165164
zbMath0384.90091MaRDI QIDQ4165164
Václav Chvátal, Peter L. Hammer
Publication date: 1977
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
Characterizations for co-graphs defined by restricted NLC-width or clique-width operations, Some complexity results about threshold graphs, Total matchings and total coverings of threshold graphs, A duality property for the set of all feasible solutions to an integer program, Hamiltonian threshold graphs, Graphs with induced-saturation number zero, Knapsack polytopes: a survey, Dualization of regular Boolean functions, About recognizing (\(\alpha\) ,\(\beta\) ) classes of polar graphs, No threshold graphs are cospectral, Structure and recognition of domishold graphs, Geometric comparison of combinatorial polytopes, An \(O(n^3)\) time algorithm for recognizing threshold dimension 2 graphs, Alternating orientation and alternating colouration of perfect graphs, Polynomial-time algorithms for regular set-covering and threshold synthesis, Split graphs and Nordhaus-Gaddum graphs, Longest cycles in threshold graphs, Structural characterization and decomposition for cographs-(2, 1) and (1, 2): a natural generalization of threshold graphs, Matroids arisen from matrogenic graphs, Generalized neighbourhoods and a class of perfectly orderable graphs, Adamant digraphs, Locally perfect graphs, On the use of Boolean methods for the computation of the stability number, Minimum edge ranking spanning trees of split graphs, \(\lambda\)-coloring matrogenic graphs, On equistable, split, CIS, and related classes of graphs, On recognition of threshold tolerance graphs and their complements, Strict 2-threshold graphs, The skiving stock problem and its relation to hypergraph matchings, Laplacian integral graphs in \(S(a, b)\), The hardness of approximating the boxicity, cubicity and threshold dimension of a graph, Dot product representations of graphs, Error-free and best-fit extensions of partially defined Boolean functions, \(H\)-product of graphs, \(H\)-threshold graphs and threshold-width of graphs, Random threshold digraphs, An aggregate and iterative disaggregate algorithm with proven optimality in machine learning, On the spectrum of threshold graphs, A characterization of threshold matroids, Sublinear approximation algorithms for boxicity and related problems, Astral graphs (threshold graphs), scale-free graphs and related algorithmic questions, A note on chromatic properties of threshold graphs, Unit and single point interval graphs, Completely separable graphs, On dynamic threshold graphs and related classes, Ferrers digraphs and threshold graphs, On the Ferrers dimension of a digraph, On 2-switches and isomorphism classes, Pseudodomishold graphs, The splittance of a graph, On shift stable hypergraphs, Eigenvalues and energy in threshold graphs, Induced saturation of graphs, Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs, Split dimension of graphs, Unoriented Laplacian maximizing graphs are degree maximal, The zero forcing polynomial of a graph, The Laplacian energy of threshold graphs and majorization, Non-minimal degree-sequence-forcing triples, The Dilworth number of auto-chordal bipartite graphs, Recognizing strict 2-threshold graphs in O(m) time, Efficient computation of the characteristic polynomial of a threshold graph, Monotone clutters, Bipartite bithreshold graphs, The chromatic symmetric functions of trivially perfect graphs and cographs, Adjacency relationships forced by a degree sequence, Towards a comprehensive theory of conflict-tolerance graphs, The strong perfect graph conjecture holds for diamonded odd cycle-free graphs, On bounds for the index of double nested graphs, Some notes on the threshold graphs, The polytope of degree sequences, The induced separation dimension of a graph, Vertex deletion problems on chordal graphs, NP-completeness results for some problems on subclasses of bipartite and chordal graphs, Matroidal graphs, Spectral characterizations of anti-regular graphs, Trivially perfect graphs, Paired threshold graphs, On random trees obtained from permutation graphs, A note on Hamiltonian split graphs, Cubicity of threshold graphs, Note on upper bound graphs and forbidden subposets, Probe threshold and probe trivially perfect graphs, Stability in \(P_5\)- and banner-free graphs, Counting and enumerating independent sets with applications to combinatorial optimization problems, The realization graph of a degree sequence with majorization gap 1 is Hamiltonian, Hamiltonian powers in threshold and arborescent comparability graphs, A class of threshold and domishold graphs: Equistable and equidominating graphs, Permutations représentatives d'un graphe à seuil, Threshold hypergraphs, Degree sequences of matrogenic graphs, Once more on matrogenic graphs, Interval graphs and interval orders, Split graphs of Dilworth number 2, Boolean techniques for matroidal decomposition of independence systems and applications to graphs, The threshold order of a Boolean function, Maximal graphs and graphs with maximal spectral radius, Vicinal orders of trees, Degree sequences and majorization, Strong cliques and equistability of EPT graphs, The polytope of degree sequences of hypergraphs, Split graphs, Threshold Sequences, Bithreshold Graphs, Minkowski complexes and convex threshold dimension, Letter Graphs and Geometric Grid Classes of Permutations, A lower bound on the saturation number, and graphs for which it is sharp, Seidel spectrum of threshold graphs, Efficient Computation of the Characteristic Polynomial of a Threshold Graph, Simple games and magic squares, Boolean minors, Maximum Laplacian energy among threshold graphs, On pairwise compatibility graphs having Dilworth number two, Hardness results of connected power domination for bipartite graphs and chordal graphs, Pairwise Compatibility Graphs: A Survey, Word-Representable Graphs: a Survey, Representing split graphs by words, Double-threshold permutation graphs, Spanning tree enumeration and nearly triangular graph Laplacians, Threshold Dimension of Graphs, Laplacian spectra and spanning trees of threshold graphs, On the geometric separability of Boolean functions, Homomorphically full graphs, Betti numbers and anti-lecture Hall compositions of random threshold graphs, Polynomial size IP formulations of knapsack may require exponentially large coefficients, The role of the anti-regular graph in the spectral analysis of threshold graphs, Some results on multithreshold graphs, Peer effects in endogenous networks, Neighborhood degree lists of graphs, A simple model of network formation with competition effects, Recognizing Threshold Tolerance Graphs in $$O(n^2)$$ Time, Hyper-Hamiltonicity in graphs: some sufficient conditions, Forbidden induced subgraphs, Characterizations, probe and sandwich problems on \(( k , \ell )\)-cographs, On hyper-Hamiltonicity in graphs, Optimal constraints aggregation method for ILP, Characterizing threshold graphs with \(k\) main signless Laplacian eigenvalues, The Second Neighborhood Conjecture for Oriented Graphs Missing $\{C_{4}, \overline{C_{4}}, S_{3},$ chair and co-chair$\}$-Free Graph, The signless Laplacian spectral radius of graphs with a prescribed number of edges, Connected graphs of fixed order and size with maximal \(A_\alpha \)-index: the one-dominating-vertex case, Hardness and approximation results of Roman \{3\}-domination in graphs, Eigenvalue location in threshold graphs, Separable and equatable hypergraphs, Inner-core and outer-core functions of partially defined Boolean functions, Computing square roots of trivially perfect and threshold graphs, Equistable simplicial, very well-covered, and line graphs, Graphs and degree sequences. I, Threshold graphs, shifted complexes, and graphical complexes, A conjecture on the eigenvalues of threshold graphs, Independent transversals of hypergraph edges and bipartite bigraphs, Difference graphs, New Classes of Degree Sequences with Fast Mixing Swap Markov Chain Sampling, Enumerating threshold graphs and some related graph classes, On pairwise compatibility graphs having Dilworth number \(k\), Bounds on Threshold Dimension and Disjoint Threshold Coverings, On the Burkard-Hammer condition for Hamiltonian split graphs, Laplacian controllability classes for threshold graphs, On the normalized spectrum of threshold graphs, Split permutation graphs, Any 2-asummable bipartite function is weighted threshold, Equistable graphs, general partition graphs, triangle graphs, and graph products, On characterizations for subclasses of directed co-graphs, Cut-threshold graphs, A Graph Theoretic Approach to Solve Special Knapsack Problems in Polynomial Time, Recognition of Unigraphs through Superposition of Graphs (Extended Abstract), Algorithmic aspects of upper paired-domination in graphs, Deciding the Bell Number for Hereditary Graph Properties, Forbidden subgraphs of power graphs, Representing graphs as the intersection of cographs and threshold graphs, Solving network design problems via iterative aggregation, Majorization and the number of bipartite graphs for given vertex degrees, Graphs with no induced \(C_ 4\) and \(2K_ 2\), Embeddings of graphs in Euclidean spaces, The size of chordal, interval and threshold subgraphs, Linear separation of connected dominating sets in graphs, On forcibly hereditary P-graphical sequences, On the Lovász-Schrijver PSD-operator on graph classes defined by clique cutsets, Decomposing 1-Sperner hypergraphs, Unnamed Item, Geometrical embeddings of graphs, Cographs: eigenvalues and Dilworth number, Group-annihilator graphs realised by finite abelian groups and its properties, Permutation graphs and the abelian sandpile model, tiered trees and non-ambiguous binary trees, The principal Erdős-Gallai differences of a degree sequence, Comparing linear width parameters for directed graphs, Optimization for L1-Norm Error Fitting via Data Aggregation, The Complexity of the Partial Order Dimension Problem, Fast algorithms for computing the characteristic polynomial of threshold and chain graphs, Graph Classes and Forbidden Patterns on Three Vertices, Note on chromatic polynomials of the threshold graphs, The structure of graphs with forbidden induced $C_4$, $\overline{C}_4$, $C_5$, $S_3$, chair and co-chair, Describing hereditary properties by forbidden circular orderings, A survey on pairwise compatibility graphs, On the enumeration of Boolean functions with distinguished variables, Hereditary classes of graphs: a parametric approach, On upper bound graphs with forbidden subposets, Vertex Deletion Problems on Chordal Graphs, Upward-closed hereditary families in the dominance order, Counting Labeled Threshold Graphs with Eulerian Numbers, Relating centralities in graphs and the principal eigenvector of its distance matrix, Arbitrarily partitionable \(\{2K_2, C_4\}\)-free graphs, Bounding threshold dimension: realizing graphic Boolean functions as the AND of majority gates, Multithreshold multipartite graphs, Complete signed graphs with largest maximum or smallest minimum eigenvalue, Groups, Graphs, and Hypergraphs: Average Sizes of Kernels of Generic Matrices with Support Constraints, An explicit formula for the distance characteristic polynomial of threshold graphs, Generating \(I\)-eigenvalue free threshold graphs, Induced subgraphs of zero-divisor graphs, Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs, Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs, Algorithms and complexity of sandwich problems in graphs (extended abstract), Split graphs and block representations, Hardness results of global Roman domination in graphs, On double bound graphs and forbidden subposets, On double bound graphs and forbidden subposets, The lexicographic method for the threshold cover problem, Letter graphs and geometric grid classes of permutations: characterization and recognition
