On certain trees with the same degree sequence

Research output: Contribution to journalArticlepeer-review

Abstract

Let G be a simple graph and x,y,z,w be 4 vertices of G. A switch in G is the replacement of the edges {x,y} and {z,w} of G by the edges {x,z} and {y,w}, given that {x,z} and {y,w} were not present in G originally. Two simple graphs have the same degree sequence if and only if there is a sequence of switches that transforms one into another. In this paper we define the number S(G) as the number of non-isomorphic graphs that have the same degree sequence as G, in other words, that are obtained from G by switches. We also define the S(G)-switch-graph class whose elements, the S(G)-switch-graphs, are the simple graphs H with S(H)=S(G). Bounds on S(G) when G is a path with n vertices are given. The characterization of the trees that are k-switch-graphs, for 2≤k≤5, are described.

Original languageEnglish
Pages (from-to)138-146
Number of pages9
JournalDiscrete Applied Mathematics
Volume321
DOIs
Publication statusPublished - 15 Nov 2022

Keywords

  • Degree sequence
  • Non-isomorphic graphs
  • Switch
  • Trees

Fingerprint

Dive into the research topics of 'On certain trees with the same degree sequence'. Together they form a unique fingerprint.

Cite this