A simple criterion on degree sequences of graphs

DOI10.1016/j.dam.2008.03.033zbMath1168.05307OpenAlexW2134970753MaRDI QIDQ1003744

Himanshu Tyagi, Amitabha Tripathi

Publication date: 4 March 2009

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.03.033

zbMATH Keywords

degree sequencegraphic sequencegraphically equivalent sequenceperfect degree sequencequasi-perfect degree sequence

Mathematics Subject Classification ID

Vertex degrees (05C07)

Related Items (20)

Unnamed Item ⋮ Vertex-weighted graphs: realizable and unrealizable domains ⋮ Independence number of graphs and line graphs of trees by means of omega invariant ⋮ Packing tree degree sequences ⋮ On vertex-weighted realizations of acyclic and general graphs ⋮ Graph realizations: maximum degree in vertex neighborhoods ⋮ Methods for the graph realization problem ⋮ Unnamed Item ⋮ Degree polynomial for vertices in a graph and its behavior under graph operations ⋮ Degree sequence of graph operator for some standard graphs ⋮ On vertex-weighted graph realizations ⋮ Recognition of split-graphic sequences ⋮ A short constructive proof of the Erdős-Gallai characterization of graphic lists ⋮ Vertex-weighted realizations of graphs ⋮ Unnamed Item ⋮ A short constructive proof of A.R. Rao's characterization of potentially \(K_{r+1}\)-graphic sequences ⋮ On the Degree Sequence of 3-Uniform Hypergraph: A New Sufficient Condition ⋮ Unnamed Item ⋮ Relaxed and approximate graph realizations ⋮ A triangle process on regular graphs

Cites Work

• A short proof of a theorem on degree sets of graphs
• A note on a theorem of Erdős and Gallai
• Algorithms for constructing graphs and digraphs with given valences and factors
• A remark on the existence of finite graphs
• A simple proof of the Erdos-Gallai theorem on graph sequences
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• Seven criteria for integer sequences being graphic
• Degree sets for graphs
• No Graph is Perfect
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A simple criterion on degree sequences of graphs