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 -