Realizability and uniqueness in graphs

DOI10.1016/0012-365X(94)00104-QzbMath0817.05048OpenAlexW2004402862WikidataQ60326851 ScholiaQ60326851MaRDI QIDQ1344609

Eberhard Triesch, Martin Aigner

Publication date: 11 July 1995

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

Full work available at URL: https://doi.org/10.1016/0012-365x(94)00104-q

zbMATH Keywords

complexityinvariantsdecision problemsreconstruction conjecturedegree sequencefinite graphsearch problemdegree realization problemsize sequence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

New sufficient conditions on the degree sequences of uniform hypergraphs ⋮ Unnamed Item ⋮ On the complexity of reconstructing H-free graphs from their Star Systems ⋮ A parallel algorithm for nearly optimal edge search ⋮ Edge search in hypergraphs ⋮ Vertex-weighted graphs: realizable and unrealizable domains ⋮ Reconstructing graphs from size and degree properties of their induced \(k\)-subgraphs ⋮ Independence number of graphs and line graphs of trees by means of omega invariant ⋮ Property Testing for Bounded Degree Databases ⋮ On vertex-weighted realizations of acyclic and general graphs ⋮ New results on degree sequences of uniform hypergraphs ⋮ Graph realizations: maximum degree in vertex neighborhoods ⋮ Unnamed Item ⋮ Degree polynomial for vertices in a graph and its behavior under graph operations ⋮ On vertex-weighted graph realizations ⋮ Graph exponentiation and neighborhood reconstruction ⋮ Efficiently Realizing Interval Sequences ⋮ Extremal problems on components and loops in graphs ⋮ Toughness and Vertex Degrees ⋮ Neighborhood reconstruction and cancellation of graphs ⋮ A short constructive proof of the Erdős-Gallai characterization of graphic lists ⋮ Majorization and the number of bipartite graphs for given vertex degrees ⋮ On the Complexity of Reconstructing H-free Graphs from Their Star Systems ⋮ Realization problems on reachability sequences ⋮ A short constructive proof of A.R. Rao's characterization of potentially \(K_{r+1}\)-graphic sequences ⋮ The effect of edge and vertex deletion on omega invariant ⋮ Some Ulam’s reconstruction problems for quantum states ⋮ Fast Sequential Creation of Random Realizations of Degree Sequences ⋮ Combinatorial properties of degree sequences of 3-uniform hypergraphs arising from Saind arrays ⋮ Upward-closed hereditary families in the dominance order ⋮ Relaxed and approximate graph realizations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The polytope of degree sequences
• A theorem on flows in networks
• Zero-one matrices with zero trace
• Search problems on graphs
• Group testing with two defectives
• A search problem on graphs which generalizes some group testing problems with two defectives
• A tight upper bound for group testing in graphs
• Edge search in graphs and hypergraphs of bounded rank
• A remark on the existence of finite graphs
• Combinatorial Properties of Matrices of Zeros and Ones
• Multiplicities and Minimal Widths for (0, 1)-Matrices
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• Some NP-Complete Problems Similar to Graph Isomorphism
• A Group Testing Problem on Two Disjoint Sets
• Threshold Sequences
• On the residue of a graph
• Reconstructing a Graph from its Neighborhood Lists
• Degree sequences of graphs and dominance order
• Graph isomorphism is low for PP