On realization graphs of degree sequences
From MaRDI portal
Publication:284753
DOI10.1016/J.DISC.2016.03.012zbMATH Open1337.05022arXiv1503.06073OpenAlexW2279289197MaRDI QIDQ284753FDOQ284753
Authors: Michael D. Barrus 
Publication date: 18 May 2016
Published in: Discrete Mathematics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1503.06073
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
- Threshold graphs and related topics
- Title not available (Why is that?)
- The interchange graphs of tournaments with minimum score vectors are exactly hypercubes
- Matrices of zeros and ones with fixed row and column sum vectors
- On the upper bound of the diameter of interchange graphs
- The realization graph of a degree sequence with majorization gap 1 is Hamiltonian
- Hamiltonicity of a type of interchange graphs
- Linear recognition of pseudo-split graphs
- On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs
- Decomposition of graphical sequences and unigraphs
- Packing 4-cycles in Eulerian and bipartite Eulerian tournaments with an application to distances in interchange graphs
- Graphs with no induced \(C_ 4\) and \(2K_ 2\)
- Disjoint cycles in Eulerian digraphs and the diameter of interchange graphs
- \(\beta\)-perfect graphs
- Hamiltonicity of a class of interchange graphs of \((0,1)\) matrices.
- The \(A_4\)-structure of a graph
- Graphs with Given Group and Given Graph-Theoretical Properties
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Rao's degree sequence conjecture
- Some properties for a class of interchange graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Some Properties of Graphs with Multiple Edges
- Transposition Graphs
- Partitions and Their Representative Graphs
- Prime interchange graphs of classes of matrices of zeros and ones
- Degree sequences of matrogenic graphs
- Once more on matrogenic graphs
Cited In (19)
- Realizing degree sequences as \(Z_3\)-connected graphs
- On fractional realizations of graph degree sequences
- Title not available (Why is that?)
- Degree polynomial for vertices in a graph and its behavior under graph operations
- New classes of degree sequences with fast mixing swap Markov chain sampling
- Degree sequences of matrogenic graphs
- A property of adjacency matrices of realizations of pair sequences
- Adjacency relationships forced by a degree sequence
- On triangular biregular degree sequences
- Switches in Eulerian graphs
- Finding structure in sequences of real numbers via graph theory: a problem list
- On realizations of a joint degree matrix
- Title not available (Why is that?)
- Vertex-weighted realizations of graphs
- Fully graphic degree sequences and P-stable degree sequences
- On (1, 2)-realizable graphs
- Constrained switchings in cubic graphs.
- Connected realizations of joint-degree matrices
- Cliques in realization 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)
