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

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

This page was built for publication: Threshold graphs and related topics