On connected simple graphs and their degree sequences

2015/12/04 by McLaughlin, Jonathan
#05C40 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1512.01377

Abstract

This note describes necessary and sufficient conditions for a sequence of positive integers to be the degree sequence of a connected simple graph. Conditions are also given under which a sequence is necessarily connected i.e. the sequence can only be realised as a connected graph. A matrix is introduced whose non-empty entries partition the set of connected graphs. The note concludes with a result relating the number of edges in a simple graph to the connectedness of the graph.

Related

• On connected degree sequences
• k-connected degree sequences
• 3-connected graphs and their degree sequences
• Degree polynomial of vertices in a graph and its behavior under graph operations
• On the Degree Sequences of Multigraphs with Edge Additions and Deletions