On realization graphs of degree sequences
From MaRDI portal
Abstract: Given the degree sequence of a graph, the realization graph of is the graph having as its vertices the labeled realizations of , with two vertices adjacent if one realization may be obtained from the other via an edge-switching operation. We describe a connection between Cartesian products in realization graphs and the canonical decomposition of degree sequences described by R.I. Tyshkevich and others. As applications, we characterize the degree sequences whose realization graphs are triangle-free graphs or hypercubes.
Recommendations
- Sequences realizable by maximal k‐degenerate graphs
- scientific article; zbMATH DE number 4187870
- scientific article; zbMATH DE number 713480
- On fractional realizations of graph degree sequences
- Realizing degree sequences with k-edge-connected uniform hypergraphs
- Degree sequences in graphs
- Extremal graph theory for degree sequences
- Realizing degree sequences as \(Z_3\)-connected graphs
- Degree sequences of multigraphs
- Degree sequences of multigraphs
Cites work
- -perfect graphs
- Decomposition of graphical sequences and unigraphs
- Degree sequences of matrogenic graphs
- Disjoint cycles in Eulerian digraphs and the diameter of interchange graphs
- Graphs with Given Group and Given Graph-Theoretical Properties
- Graphs with no induced \(C_ 4\) and \(2K_ 2\)
- Hamiltonicity of a class of interchange graphs of (0,1) matrices.
- Hamiltonicity of a type of interchange graphs
- scientific article; zbMATH DE number 3880741 (Why is no real title available?)
- scientific article; zbMATH DE number 4089595 (Why is no real title available?)
- scientific article; zbMATH DE number 3674138 (Why is no real title available?)
- scientific article; zbMATH DE number 3613062 (Why is no real title available?)
- scientific article; zbMATH DE number 3632548 (Why is no real title available?)
- scientific article; zbMATH DE number 1334614 (Why is no real title available?)
- scientific article; zbMATH DE number 1881001 (Why is no real title available?)
- scientific article; zbMATH DE number 772748 (Why is no real title available?)
- scientific article; zbMATH DE number 279458 (Why is no real title available?)
- Linear recognition of pseudo-split graphs
- Matrices of zeros and ones with fixed row and column sum vectors
- On extended P₄-reducible and extended P₄-sparse graphs
- On the upper bound of the diameter of interchange graphs
- Once more on matrogenic graphs
- Packing 4-cycles in Eulerian and bipartite Eulerian tournaments with an application to distances in interchange graphs
- Partitions and Their Representative Graphs
- Prime interchange graphs of classes of matrices of zeros and ones
- Rao's degree sequence conjecture
- Some properties for a class of interchange graphs
- Some Properties of Graphs with Multiple Edges
- The A₄-structure of a graph
- The interchange graphs of tournaments with minimum score vectors are exactly hypercubes
- The realization graph of a degree sequence with majorization gap 1 is Hamiltonian
- Threshold graphs and related topics
- Transposition Graphs
Cited in
(23)- The realization graph of a degree sequence with majorization gap 1 is Hamiltonian
- Decomposition of graphical sequences and unigraphs
- Adjacency relationships forced by a degree sequence
- Connected realizations of joint-degree matrices
- On (1, 2)-realizable graphs
- Cliques in realization graphs
- Finding structure in sequences of real numbers via graph theory: a problem list
- Vertex-weighted realizations of graphs
- scientific article; zbMATH DE number 4019109 (Why is no real title available?)
- A property of adjacency matrices of realizations of pair sequences
- scientific article; zbMATH DE number 3910445 (Why is no real title available?)
- Realizing degree sequences as \(Z_3\)-connected graphs
- On fractional realizations of graph degree sequences
- scientific article; zbMATH DE number 1161322 (Why is no real title available?)
- New classes of degree sequences with fast mixing swap Markov chain sampling
- On realizations of a joint degree matrix
- Constrained switchings in cubic graphs.
- Degree polynomial for vertices in a graph and its behavior under graph operations
- On triangular biregular degree sequences
- Switches in Eulerian graphs
- Fully graphic degree sequences and P-stable degree sequences
- Degree realization with maximum matching
- Degree sequences of matrogenic graphs
This page was built for publication: On realization graphs of degree sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q284753)
