Forced Edges and Graph Structure
1National Institute of Standards and Technology, Gaithersburg, MD 20899, USA.
Abstract:
For a degree sequence, we define the set of edges that appear in every labeled realization of that sequence as forced, while the edges that appear in none are define as forbidden. We examine the structure of graphs in which the degree sequences contain either forced or forbidden edges. The results include the determination of the structure of the forced or forbidden edge sets, the relationship between the sizes of forced and forbidden sets for a sequence, and the structural consequences to their realizations. This includes showing that the diameter of every realization of a degree sequence containing forced or forbidden edges is no greater than 3, and that these graphs are maximally edge-connected.
More Related Videos
10:36High Resolution Quantitative Synaptic Proteome Profiling of Mouse Brain Regions After Auditory Discrimination Learning
Published on: December 15, 2016
07:08Optimization of Synthetic Proteins: Identification of Interpositional Dependencies Indicating Structurally and/or Functionally Linked Residues
Published on: July 14, 2015
Related Concept Videos
Ogive Graph
Vector Algebra: Graphical Method
We use the laws of geometry to construct resultant vectors, followed by trigonometry to find vector magnitudes and directions. For a geometric construction of the sum of two vectors in a plane, we follow the parallelogram rule. Suppose two vectors are at arbitrary positions. Translate either one of...
Stability of structures
Graphing the Wave Function
Elevation of Intermediate Points on Vertical Curves
pV-Diagrams
