Threshold graphs and related topics

zbMath0852.05001MaRDI QIDQ1899209

N. V. R. Mahadev, Uri N. Peled

Publication date: 9 October 1995

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

zbMATH Keywords

decompositionenumerationNP-completenessextremal problemssplit graphsthreshold graphsdegree sequencesdifference graphsDilworth numberFerrers digraphsthreshold weights

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Split graphs, Exponentially many graphs have a \(Q\)-cospectral mate, Notes on Hamiltonian threshold and chain graphs, Matching orderable and separable hypergraphs, A lower bound on the saturation number, and graphs for which it is sharp, Eigenvalue-free interval for Seidel matrices of threshold graphs, Complex Pythagorean fuzzy threshold graphs with application in petroleum replenishment, Maximum Laplacian energy among threshold graphs, On family of graphs with minimum number of spanning trees, Hardness results of connected power domination for bipartite graphs and chordal graphs, Representing split graphs by words, Combinatorics, graph theory, and computing, Double-threshold permutation graphs, Deciding atomicity of subword-closed languages, Spanning tree enumeration and nearly triangular graph Laplacians, Injective coloring of some subclasses of bipartite graphs and chordal graphs, Laplacian spectra and spanning trees of threshold graphs, Betti numbers and anti-lecture Hall compositions of random threshold graphs, Exact square coloring of certain classes of graphs: complexity and algorithms, The role of the anti-regular graph in the spectral analysis of threshold graphs, Maximality of the signless Laplacian energy, Neighborhood degree lists of graphs, Recognizing simple-triangle graphs by restricted 2-chain subgraph cover, Homomorphisms into loop-threshold graphs, Characterizing threshold graphs with \(k\) main signless Laplacian eigenvalues, The signless Laplacian spectral radius of graphs with a prescribed number of edges, Net Laplacian controllability for joins of signed graphs, Perfect Italian domination on planar and regular graphs, Erdős-Ko-Rado theorems for simplicial complexes, Interval graph limits, Eigenvalue location in threshold graphs, On the adjacency matrix of a threshold graph, \(G\)-parking functions and tree inversions, Face numbers of centrally symmetric polytopes produced from Split graphs, Efficient counting of degree sequences, On the complexity of the black-and-white coloring problem on some classes of perfect graphs, \(b\)-vectors of chordal graphs, Equistable simplicial, very well-covered, and line graphs, Graph vulnerability parameters, compression, and threshold graphs, Distance eigenvalues of a cograph and their multiplicities, Threshold graphs, shifted complexes, and graphical complexes, A conjecture on the eigenvalues of threshold graphs, Graph vulnerability parameters, compression, and quasi-threshold graphs, NP-hard graph problems and boundary classes of graphs, Each \((n,m)\)-graph having the \(i\)-th minimal Laplacian coefficient is a threshold graph, The Moore-Penrose inverse of symmetric matrices with nontrivial equitable partitions, Equistable distance-hereditary graphs, Adjacency relationships forced by a degree sequence, Extremal threshold graphs for matchings and independent sets, On pairwise compatibility graphs having Dilworth number \(k\), On the eigenvalues distribution in threshold graphs, Stable-\(\Pi\) partitions of graphs, The graph tessellation cover number: chromatic bounds, efficient algorithms and hardness, Laplacian controllability classes for threshold graphs, On the normalized spectrum of threshold graphs, Graphs with maximal signless Laplacian spectral radius, On the reduced signless Laplacian spectrum of a degree maximal graph, Equistable graphs, general partition graphs, triangle graphs, and graph products, The \(L(2,1)\)-labeling of unigraphs, On characterizations for subclasses of directed co-graphs, Pairwise stable networks in homogeneous societies with weak link externalities, Algorithmic aspects of upper paired-domination in graphs, Spectral characterizations of anti-regular graphs, Binomial edge ideals of regularity 3, Sandwiches missing two ingredients of order four, Forbidden subgraphs of power graphs, Representing graphs as the intersection of cographs and threshold graphs, Perfectness of clustered graphs, A vertex ordering characterization of simple-triangle graphs, Paired threshold graphs, Fractional revival of threshold graphs under Laplacian dynamics, On the threshold of intractability, On main eigenvalues of chain graphs, Algorithmic aspects of Roman domination in graphs, A note on the eigenvalue free intervals of some classes of signed threshold graphs, On maximal graphical partitions that are the nearest to a given graphical partition, Decomposing 1-Sperner hypergraphs, Cographs: eigenvalues and Dilworth number, Group-annihilator graphs realised by finite abelian groups and its properties, On the eccentricity spectra of threshold graphs, The principal Erdős-Gallai differences of a degree sequence, Idiosyncratic preferences in games on networks, Local public goods with weighted link formation, Vertex types in threshold and chain graphs, Supersolvable frame-matroid and graphic-lift lattices, Partitioning cographs into cliques and stable sets, Linear algebraic techniques for weighted spanning tree enumeration, Eigenvalue-free interval for threshold graphs, Fast algorithms for computing the characteristic polynomial of threshold and chain graphs, Cliques in realization graphs, Threshold graphs of maximal Laplacian energy, A remark concerning graphical sequences, Domination, coloring and stability in \(P_5\)-reducible graphs, Non-bipartite graphs of fixed order and size that minimize the least eigenvalue, Hereditary classes of graphs: a parametric approach, The Burge correspondence and crystal graphs, On monoid graphs, Extension of threshold graphs under complex fuzzy environment, On bipartite graphs having minimum fourth adjacency coefficient, Graphs and digraphs represented by intervals and circular arcs, Characterizations for co-graphs defined by restricted NLC-width or clique-width operations, On realization graphs of degree sequences, No threshold graphs are cospectral, Algorithmic aspects of total Roman and total double Roman domination in graphs, On structural parameterizations of load coloring, The micro-world of cographs, An \(O(n^3)\) time algorithm for recognizing threshold dimension 2 graphs, Distribution of Laplacian eigenvalues of graphs, Mock threshold graphs, On the OBDD representation of some graph classes, On the distance spectra of threshold graphs, Diagonalization of generalized lollipop graphs, Strategic complementarities, network games and endogenous network formation, Algorithmic and modeling insights via volumetric comparison of polyhedral relaxations, Minimum edge ranking spanning trees of split graphs, \(\lambda\)-coloring matrogenic graphs, Graphs with the strong Havel-Hakimi property, Threshold-coloring and unit-cube contact representation of planar graphs, On equistable, split, CIS, and related classes of graphs, On the emergence of scale-free production networks, The isomorphic version of Brualdi's and Sanderson's nestedness, Estimating parameters of a probabilistic heterogeneous block model via the EM algorithm, On the evaluation of the Tutte polynomial at the points \((1, -1)\) and \((2, -1)\), Maximum likelihood estimation in the \(\beta\)-model, Fast algorithms for indices of nested split graphs approximating real complex networks, Dot product representations of graphs, Cones of closed alternating walks and trails, Some approaches for solving the general (\(t,k\))-design existence problem and other related problems, Minimal dominating sets in graph classes: combinatorial bounds and enumeration, \(H\)-product of graphs, \(H\)-threshold graphs and threshold-width of graphs, Hereditary unigraphs and Erdős-Gallai equalities, Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization, Theorems on partitioned matrices revisited and their applications to graph spectra, Random threshold digraphs, Matchings, coverings, and Castelnuovo-Mumford regularity, On the spectrum of threshold graphs, Bichain graphs: geometric model and universal graphs, Sphere and dot product representations of graphs, Connected graphs of fixed order and size with maximal \(Q\)-index: some spectral bounds, Sublinear approximation algorithms for boxicity and related problems, Forbidden substructure for interval digraphs/bigraphs, Astral graphs (threshold graphs), scale-free graphs and related algorithmic questions, Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs, Efficient networks for a class of games with global spillovers, Forms of representation for simple games: sizes, conversions and equivalences, A note on chromatic properties of threshold graphs, The efficiency and stability of R\&D networks, Edge contractions in subclasses of chordal graphs, Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs, Unit and single point interval graphs, On dynamic threshold graphs and related classes, Equistable series-parallel graphs, Equistable chordal graphs, Random graphs with a given degree sequence, On 2-switches and isomorphism classes, The chain graph sandwich problem, A characterization of chain probe graphs, Complexity results for equistable graphs and related classes, A fully dynamic algorithm for modular decomposition and recognition of cographs., Eigenvalues and energy in threshold graphs, A characterization of claw-free \(b\)-perfect graphs, Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs, Bipartite graphs with the maximum sum of squares of degrees, Unoriented Laplacian maximizing graphs are degree maximal, Some new considerations about double nested graphs, Extremal Laplacian energy of threshold graphs, On a class of graphs between threshold and total domishold graphs, Efficient computation of the characteristic polynomial of a threshold graph, On maximal graphical partitions, Graphs with the fewest matchings, Operator decomposition of graphs and the reconstruction conjecture, Graphs with the maximum or minimum number of 1-factors, A short constructive proof of the Erdős-Gallai characterization of graphic lists, Connected graphs with maximal \(Q\)-index: The one-dominating-vertex case, On bounds for the index of double nested graphs, Some notes on the threshold graphs, Graphs of linear clique-width at most 3, Stable sets in \(k\)-colorable \(P_{5}\)-free graphs, On the complete width and edge clique cover problems, On split-coloring problems, The polytope of dual degree partitions, Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions, On random trees obtained from permutation graphs, Specializations of Ferrers ideals, Extreme values of the sum of squares of degrees of bipartite graphs, Cubicity of threshold graphs, Undirected simple connected graphs with minimum number of spanning trees, Split digraphs, The complexity of some problems related to GRAPH 3-COLORABILITY, Probe threshold and probe trivially perfect 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, Enumerative aspects of certain subclasses of perfect graphs, Random walks and hyperplane arrangements, Matrix sandwich problems, Maximal graphs and graphs with maximal spectral radius, Threshold arrangements and the knapsack problem, Strong cliques and equistability of EPT graphs, The polytope of degree sequences of hypergraphs, Chain graph sequences and Laplacian spectra of chain graphs, Laplacian eigenvalues of equivalent cographs, Graphs of fixed order and size with maximal \(A_\alpha\)-index, Generating \(I\)-eigenvalue free threshold graphs, Laplacian spectra of cographs: a twin reduction perspective, Nonvanishing Betti numbers of edge ideals of weakly chordal graphs, Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs, On inverse symmetric division deg index of graphs, Split graphs and block representations, On structural parameterizations of load coloring, Complexity issues of perfect secure domination in graphs, The Micro-world of Cographs, Letter Graphs and Geometric Grid Classes of Permutations, Minimizer graphs for a class of extremal problems, Efficient Computation of the Characteristic Polynomial of a Threshold Graph, Total vertex-edge domination in graphs: Complexity and algorithms, Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs, Pairwise Compatibility Graphs: A Survey, Unnamed Item, Unnamed Item, The Group Inverse of the Laplacian Matrix of a Graph, Extremal graphs for the Tutte polynomial, Complexity aspects of variants of independent Roman domination in graphs, Optimization over Degree Sequences, Nestedness in networks: A theoretical model and some applications, Results on the small quasi-kernel conjecture, Bounding threshold dimension: realizing graphic Boolean functions as the AND of majority gates, Graph universal cycles: compression and connections to universal cycles, Maximum spread of graphs and bipartite graphs, Algorithmic aspects of outer independent Roman domination in graphs, Unnamed Item, Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration, Multithreshold multipartite graphs, AROUND THE ERDÖS–GALLAI CRITERION, Signed graphs with integral net Laplacian spectrum, Dr. Charles L. Suffel: Scholar, teacher, mentor, friend, Efficient non-isomorphic graph enumeration algorithms for subclasses of perfect graphs, Certifying induced subgraphs in large graphs, Persuasion in Networks: Public Signals and Cores, Re-conceptualizing centrality in social networks, On 4-Sachs optimal graphs, Groups, Graphs, and Hypergraphs: Average Sizes of Kernels of Generic Matrices with Support Constraints, Complexity aspects of restrained Roman domination in graphs, Chain graphs with simple Laplacian eigenvalues and their Laplacian dynamics, An explicit formula for the distance characteristic polynomial of threshold graphs, Connected graphs of fixed order and size with maximal \(A_\alpha \)-index: the one-dominating-vertex case, Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs, Hardness and approximation results of Roman \{3\}-domination in graphs, Separable and equatable hypergraphs, Positional Dominance: Concepts and Algorithms, On Structural Parameterizations of Graph Motif and Chromatic Number, The asymptotics of the geometric polynomials, On König graphs with respect to P4, A survey of discrete methods in (algebraic) statistics for networks, Unnamed Item, Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs, Efficiently Realizing Interval Sequences, Hardness results of global Roman domination in graphs, Edge Contractions in Subclasses of Chordal Graphs, Sampling for Conditional Inference on Network Data, Polar cographs, Algorithmic aspects of certified domination in graphs, Polar cographs, Algorithmic aspects of total Roman ${2}$-domination in graphs, On double bound graphs and forbidden subposets, Unnamed Item, On double bound graphs and forbidden subposets, Algorithmic Aspects of Quasi-Total Roman Domination in Graphs, Independent roman $\{3\}$-domination, Partitioning a graph into complementary subgraphs, Unnamed Item, The lexicographic method for the threshold cover problem, Residual reliability of P-threshold graphs, A Graph Theoretic Approach to Solve Special Knapsack Problems in Polynomial Time, Recognition of Unigraphs through Superposition of Graphs (Extended Abstract), Letter graphs and geometric grid classes of permutations: characterization and recognition, Extremal graphs for homomorphisms, Exploring Symmetries to Decompose Matrices and Graphs Preserving the Spectrum, Inference using noisy degrees: differentially private \(\beta\)-model and synthetic graphs, Algorithmic complexity of secure connected domination in graphs, NP-completeness results for partitioning a graph into total dominating sets, Fully Dynamically Maintaining Minimal Integral Separator for Threshold and Difference Graphs, Linear Algebraic Techniques for Spanning Tree Enumeration, Vertex deletion on split graphs: beyond 4-hitting set, Spectral properties of cographs andP₅-free graphs, Oriented Threshold Graphs, Linear separation of connected dominating sets in graphs, Simplicial matrix-tree theorems, Weak Unit Disk and Interval Representation of Graphs, Recognizing k-equistable Graphs in FPT Time, Exploring the Subexponential Complexity of Completion Problems, Rank‐tolerance graph classes, Unnamed Item, Vertex types in some lexicographic products of graphs, Recognizing Graphs Close to Bipartite Graphs, Flow Polytopes and the Space of Diagonal Harmonics, The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial, Efficient Local Representations of Graphs, Graph Classes and Forbidden Patterns on Three Vertices, Fast Sequential Creation of Random Realizations of Degree Sequences, Note on chromatic polynomials of the threshold graphs, Eigenvalue-free intervals of distance matrices of threshold and chain graphs, Linear-time recognition of double-threshold graphs, On upper bound graphs with forbidden subposets, Operator Decomposition of Graphs and the Reconstruction Conjecture, Algorithmic complexity of weakly connected Roman domination in graphs, Upward-closed hereditary families in the dominance order, Algorithmic aspects of total Roman {3}-domination in graphs, Counting Labeled Threshold Graphs with Eulerian Numbers