Split graphs

DOI10.1016/S0195-6698(03)00030-1zbMath1020.05021DBLPjournals/ejc/Merris03OpenAlexW2911479728WikidataQ29040734 ScholiaQ29040734MaRDI QIDQ1873776

Russell Merris

Publication date: 27 May 2003

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0195-6698(03)00030-1

zbMATH Keywords

independent setcliquemajorizationthreshold graphHasse diagramgraph realizationpartition latticestrict partitiongraphic partitionMuirhead's lemmaRuch-Gutman criterionRyser switchshifted shapethreshold partition

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Combinatorial aspects of partitions of integers (05A17) Eigenvalues, singular values, and eigenvectors (15A18) Logical aspects of lattices and related structures (03G10) Structural characterization of families of graphs (05C75) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Vertex degrees (05C07)

Related Items (29)

The Hamiltonian properties in \(K_{1,r}\)-free split graphs ⋮ On degree sequences and eccentricities in pseudoline arrangement graphs ⋮ Neighborhood degree lists of graphs ⋮ On Hamiltonian properties of \(K_{1, r}\)-free split graphs ⋮ Broadcasting in split graphs ⋮ On the complexity of coloring ‐graphs ⋮ Complete characterization of the bidegreed split graphs with three or four distinct \(A_{\alpha}\)-eigenvalues ⋮ Nonsplit Graphs with Split Maximal Induced Subgraphs ⋮ Connected graphs of fixed order and size with maximal \(A_\alpha \)-index: the one-dominating-vertex case ⋮ On split graphs with three or four distinct (normalized) Laplacian eigenvalues ⋮ Split graphs and block representations ⋮ A Characterization of the degree sequences of 2-trees ⋮ Unnamed Item ⋮ Kernelization of Two Path Searching Problems on Split Graphs ⋮ The Grone-Merris Conjecture ⋮ Adjacency relationships forced by a degree sequence ⋮ Operator decomposition of graphs and the reconstruction conjecture ⋮ D-optimal (0,1)-weighing designs for 10 objects ⋮ Split non-threshold Laplacian integral graphs ⋮ On split graphs with four distinct eigenvalues ⋮ Dynamically maintaining split graphs ⋮ Reconstructing Cactus Graphs from Shortest Path Information ⋮ Split digraphs ⋮ The principal Erdős-Gallai differences of a degree sequence ⋮ Degree Sequence of Tight Distance Graphs ⋮ P-antiregular graphs ⋮ On maximum independent set of categorical product and ultimate categorical ratios of graphs ⋮ Upward-closed hereditary families in the dominance order ⋮ On the chromatic number of the power graph of a finite group

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• Hamiltonian threshold graphs
• Strict 2-threshold graphs
• The splittance of a graph
• Graphic sequences with unique realization
• The realization graph of a degree sequence with majorization gap 1 is Hamiltonian
• Degree sequences and majorization
• Degree maximal graphs are Laplacian integral
• Free hyperplane arrangements between \(A_{n-1}\) and \(B_ n\)
• The Erdős-Gallai criterion and symmetric functions
• Decomposition of graphical sequences and unigraphs
• Threshold graphs and related topics
• Extreme degree sequences of simple graphs
• Sufficient Conditions for Graphs to Have Threshold Number 2
• Threshold Sequences
• Seven criteria for integer sequences being graphic
• A Note on Unigraphic Sequences
• A Graph-Theoretic Characterization of the $\text{PV}_{\text{chunk}}$ Class of Synchronizing Primitives
• Switching Distance Between Graphs with the Same Degrees
• Enumeration of Graphs with Given Partition
• Inequalities: theory of majorization and its applications
• On homotopy of connected graphs having the same degree function

This page was built for publication: Split graphs