TY - JOUR

T1 - On certain trees with the same degree sequence

AU - Fernandes, Rosário

N1 - Funding Information:
This work was partially supported by the Fundação para a Ciência e a Tecnologia through the project UIBD/00297/2020 .
Publisher Copyright:
© 2022 Elsevier B.V.

PY - 2022/11/15

Y1 - 2022/11/15

N2 - 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.

AB - 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.

KW - Degree sequence

KW - Non-isomorphic graphs

KW - Switch

KW - Trees

UR - http://www.scopus.com/inward/record.url?scp=85133489173&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2022.06.043

DO - 10.1016/j.dam.2022.06.043

M3 - Article

AN - SCOPUS:85133489173

SN - 0166-218X

VL - 321

SP - 138

EP - 146

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -