Threshold Dimension of Graphs

DOI10.1137/0605055zbMath0717.05069MaRDI QIDQ3204506

Rochelle Leibowitz, Margaret B. Cozzens

Publication date: 1984

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0605055

zbMATH Keywords

decision problem; threshold dimension

Mathematics Subject Classification ID

91B06: Decision theory

05C99: Graph theory

Related Items

The lexicographic method for the threshold cover problem, Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs, An \(O(n^3)\) time algorithm for recognizing threshold dimension 2 graphs, An \(O(n^ 3)\) recognition algorithm for bithreshold graphs, Bipartite bithreshold graphs, The relationship between the threshold dimension of split graphs and various dimensional parameters, The induced matching and chain subgraph cover problems for convex bipartite graphs, Cubicity of threshold graphs, Multidimensional scaling and threshold graphs, On dimensional properties of graphs, A min-max property of chordal bipartite graphs with applications, Representing graphs as the intersection of cographs and threshold graphs, Double-threshold permutation graphs, Some results on multithreshold graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Ferrers digraphs and threshold graphs
• On the Ferrers dimension of a digraph
• Matroidal graphs
• On an extension of Dijkstra's semaphore primitives
• Class of graphs with restricted neighborhoods
• Box-threshold graphs
• The Complexity of the Partial Order Dimension Problem
• Sufficient Conditions for Graphs to Have Threshold Number 2
• Threshold Sequences
• A Graph-Theoretic Characterization of the $\text{PV}_{\text{chunk}}$ Class of Synchronizing Primitives
• Linear Separation of Dominating Sets in Graphs
• Threshold Numbers and Threshold Completions