On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
From MaRDI portal
Publication:3845889
DOI10.1137/0110037zbMath0109.16501OpenAlexW2018480107WikidataQ89358751 ScholiaQ89358751MaRDI QIDQ3845889
Publication date: 1962
Published in: Journal of the Society for Industrial and Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0110037
Related Items
Some NP-complete problems for hypergraph degree sequences, A note on a theorem of Erdős and Gallai, Graphic sequences with a realization containing intersecting cliques, Forman-Ricci curvature and persistent homology of unweighted complex networks, Exactly scale-free scale-free networks, Improving the characterization of P-stability for applications in network privacy, An extremal problem on bigraphic pairs with an \(A\)-connected realization, On degree sequences and eccentricities in pseudoline arrangement graphs, Colour degree matrices of graphs with at most one cycle, Realizability and uniqueness in graphs, Graphical sequences of some family of induced subgraphs, Leaf realization problem, caterpillar graphs and prefix normal words, A topological insight into restricted Boltzmann machines, Vertex-weighted graphs: realizable and unrealizable domains, On existence of hypergraphs with prescribed edge degree profile, On the least size of a graph with a given degree set, Graphs with the strong Havel-Hakimi property, Estimation of the covariance structure from SNP allele frequencies, Some more updates on an annihilation number conjecture: pros and cons, Arranging apples in an array, Validation of community robustness, Nontraceable detour graphs, Construction of discrete structures, especially isomers, A short proof of a theorem on degree sets of graphs, Mathematical tools for the future: graph theory and graphicable algebras, Rounding in symmetric matrices and undirected graphs, A note on the characterization of digraphic sequences, On the \(k\)-residue of disjoint unions of graphs with applications to \(k\)-independence, New results on degree sequences of uniform hypergraphs, An algorithm for the construction of the graphs of organic molecules, Game theoretical modelling of a dynamically evolving network. I: General target sequences, Realizing degree sequences as \(Z_3\)-connected graphs, On fractional realizations of graph degree sequences, Length thresholds for graphic lists given fixed largest and smallest entries and bounded gaps, The complexity of degree anonymization by vertex addition, Non-separable detachments of graphs, On the minimum local-vertex-connectivity augmentation in graphs, The enumeration of graphical partitions, Spiders can be recognized by counting their legs, An extremal problem on group connectivity of graphs, Characterization of optimal key set protocols, An algorithm to generate tournament score sequences, Degree sequences and graphs with disjoint spanning trees, Synchronizability of networks of chaotic systems coupled via a graph with a prescribed degree sequence, Multigraphic degree sequences and supereulerian graphs, disjoint spanning trees, Graphs with given valences, On realizations of a joint degree matrix, Graph extensions, edit number and regular graphs, An equation-free approach to coarse-graining the dynamics of networks, Extremal problems on components and loops in graphs, A parameterized algorithmics framework for degree sequence completion problems in directed graphs, Modulo 5-orientations and degree sequences, On null 3-hypergraphs, Multigraph realizations of degree sequences: Maximization is easy, minimization is hard, On the sum necessary to ensure that a degree sequence is potentially \(H\)-graphic, On matching numbers of tree and bipartite degree sequences, Generation of networks with prescribed degree-dependent clustering, A short constructive proof of the Erdős-Gallai characterization of graphic lists, Degree realization of undirected graphs in reduced form, Pairs of sequences with a unique realization by bipartite graphs, Sequences with a unique realization by simple graphs, A note on applying a theorem of Tutte to graphical sequences, A family of switch equivalent graphs, On the realization of a (p,s)-digraph with prescribed degrees, An intermediate value theorem for the arboricities, On partial sorting in restricted rounds, Algorithm for generating graphs of a given partition, Relations between graphs and integer-pair sequences, Distance degree regular graphs and distance degree injective graphs: an overview, Independence free graphs and vertex connectivity augmentation, A new lower bound on the potential-Ramsey number of two graphs, Navigating between packings of graphic sequences, The polytope of degree sequences, A Brooks-type result for sparse critical graphs, On the discrepancy between two Zagreb indices, Graphic sequences with a realization containing a union of cliques, Degree-anonymization using edge rotations, Graphic sequences with a realization containing a generalized friendship graph, Degree sequence and supereulerian graphs, Construction of Hamiltonian graphs and bigraphs with prescribed degrees, A simple criterion on degree sequences of graphs, A degree sequence variant of graph Ramsey numbers, The edge version of Hadwiger's conjecture, A remark on degree sequences of multigraphs, Enumeration of the degree sequences of non-separable graphs and connected graphs, Properties of unique degree sequences of 3-uniform hypergraphs, Conditions for sequences to be r-graphic, Havel-Hakimi residues of unigraphs, Isomorphic factorization of r-regular graphs into r parts, An algebraic Monte-Carlo algorithm for the partition adjacency matrix realization problem, Modelling conflicting individual preference: target sequences and graph realization, Linear-time certifying algorithms for near-graphical sequences, The convex hull of degree sequences of signed graphs, Integer-pair sequences with self-complementary realizations, A lower bound on the independence number of a graph, Unidigraphic and unigraphic degree sequences through uniquely realizable integer-pair sequences, A polynomial dual of partitions, Independence and the Havel-Hakimi residue, Relaxed and approximate graph realizations, Degree sequences and majorization, Degree realization by bipartite multigraphs, The sequence of prime gaps is graphic, Unnamed Item, On degree sequences of undirected, directed, and bidirected graphs, Unnamed Item, Spectral Bounds for the Connectivity of Regular Graphs with Given Order, Directed Networks with a Differentially Private Bi-degree Sequence, Graph realizations constrained by skeleton graphs, Unnamed Item, Extremal problems for chromatic neighborhood sets, Extremal Theorems for Degree Sequence Packing and the Two-Color Discrete Tomography Problem, Transforming Graphs with the Same Degree Sequence, I/O-Efficient Generation of Massive Graphs Following the LFR Benchmark, Polytopes, graphs, and complexes, Minimum degree conditions for the strength and bandwidth of graphs, A further result on the potential-Ramsey number of G1 and G2, A note on the potential function of an arbitrary graph H, Chromatic index of dense quasirandom graphs, Solution to an extremal problem on bigraphic pairs with a \(Z_3\)-connected realization, The potential-Ramsey number of $K_n$ and $K_t^{-k}$, On certain trees with the same degree sequence, Independence number of graphs and line graphs of trees by means of omega invariant, Extremal values of the chromatic number for a given degree sequence, The set of all values of the domination number in trees with a given degree sequence, Optimization over Degree Sequences, Game theoretical modelling of a dynamically evolving network. II: Target sequences of score 1, On vertex-weighted realizations of acyclic and general graphs, Forcibly bipartite and acyclic (uni-)graphic sequences, Identifying a Set of Key Members in Social Networks Using SDP-Based Stochastic Search and Integer Programming Algorithms, S̲tochastic S̲imulation A̲lgorithm For Effective Spreading Dynamics On T̲ime-Evolving A̲daptive N̲etworX̲ (SSATAN-X), Enumerating Steiner triple systems, Group Connectivity, Strongly Z_m-Connectivity, and Edge Disjoint Spanning Trees, Sparsity of weighted networks: measures and applications, On the longest flip sequence to untangle segments in the plane, Edge coloring graphs with large minimum degree, Graph realizations: maximum degree in vertex neighborhoods, Complexity results on untangling red-blue matchings, The game-theoretical modelling of a dynamically evolving network: revisiting the target sequence 111, Characterization and reconstruction of hypergraphic pattern sequences, Fault-tolerant graph realizations in the congested clique, On signed degrees in signed graphs, Worst-case versus average-case design for estimation from partial pairwise comparisons, A survey of the maximal and the minimal nullity in terms of omega invariant on graphs, Generalized Lucas graphs, Solution to a general version of a degree sequence variant of the Erdős-Sós conjecture, Unnamed Item, Degree polynomial for vertices in a graph and its behavior under graph operations, Sparsity measure of a network graph: Gini index, On triangular biregular degree sequences, On unigraphic polyhedra with one vertex of degree \({p-2}\), On vertex-weighted graph realizations, A Characterization of the degree sequences of 2-trees, Exact and approximate results on the least size of a graph with a given degree set, Unnamed Item, A survey of discrete methods in (algebraic) statistics for networks, Algebraic characterization of graphical degree stability, On complete systems of invariants for small graphs, Optimal path and cycle decompositions of dense quasirandom graphs, Average connectivity of minimally 2-connected graphs and average edge-connectivity of minimally 2-edge-connected graphs, On the status sequences of trees, On the existence of super edge-connected graphs with prescribed degrees, Constructing and sampling directed graphs with given degree sequences, Efficiently Realizing Interval Sequences, Approximating Shortest Connected Graph Transformation for Trees, Data Graph Formulation as the Minimum-Weight Maximum-Entropy Problem, A Havel-Hakimi type procedure and a sufficient condition for a sequence to be potentially S r,s -graphic, Exact sampling of graphs with prescribed degree correlations, The mixing time of switch Markov chains: a unified approach, Configuring Random Graph Models with Fixed Degree Sequences, Multigraphic degree sequences and Hamiltonian-connected line graphs, The class of 2-multigraphs with a prescribed degree sequence, Recognition of split-graphic sequences, On the Swap-Distances of Different Realizations of a Graphical Degree Sequence, Hypergraph recovery algorithms from a given vector of vertex degrees, Graph colourings and partitions, Stability of the Potential Function, Uniform Sampling of Digraphs with a Fixed Degree Sequence, Improvements in performance and security for complex networks, Recognition of Unigraphs through Superposition of Graphs (Extended Abstract), The condition for a sequence to be potentially $A_{L, M}$- graphic, Vertex-weighted realizations of graphs, Inference using noisy degrees: differentially private \(\beta\)-model and synthetic graphs, Algebraic operations on graphs preserving the degree sequence, Graphic deviation, On zero-sum and almost zero-sum subgraphs over \(\mathbb Z\), Graphic sequences of trees and a problem of Frobenius, Signed degree sets in signed graphs, NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs, Majorization and the number of bipartite graphs for given vertex degrees, Tripartite graphs with given degree set, Realization problems on reachability sequences, On the potential function of an arbitrary graph \(H\), On the degrees of the vertices of a directed graph, Dag Realizations of Directed Degree Sequences, MAX for \(k\)-independence in multigraphs, Unnamed Item, On the planarity of regular incidence sequences, The effect of edge and vertex deletion on omega invariant, Degree Sequences in Complexes and Hypergraphs, Regular Graphs and the Spectra of Two-Variable Logic with Counting, Connectedness criteria for graphs by means of omega invariant, A multipartite Hajnal-Szemerédi theorem
