TY - JOUR

T1 - On the switch-length of two connected graphs with the same degree sequence

AU - Fernandes, Rosário

N1 - info:eu-repo/grantAgreement/FCT/6817 - DCRRNI ID/UIDB%2F00667%2F2020/PT#

PY - 2022/6

Y1 - 2022/6

N2 - Let G be a simple graph containing distinct vertices x, y, z, w such that the edges {x, y}, {z, w} ∈ G and {x, z}, {y, w} ∉ G. The process of deleting the edges {x, y}, {z, w} from G and adding {x, z}, {y, w} to G is referred to as a switch (or 2-switch) in G. Let G1 and G2 be two connected simple graphs with the same vertex set V such that for all v ∈ V, the degree of v in G1 is the same as in G2 . It is well known that G2 can be obtained from G1 by a sequence of switches. Moreover, there is one such sequences of switches with only connected graphs. For some classes of graphs, we study the problem of finding bounds for the minimum number of switches required for transforming G1 into G2 such that all graphs in the sequence are connected.

AB - Let G be a simple graph containing distinct vertices x, y, z, w such that the edges {x, y}, {z, w} ∈ G and {x, z}, {y, w} ∉ G. The process of deleting the edges {x, y}, {z, w} from G and adding {x, z}, {y, w} to G is referred to as a switch (or 2-switch) in G. Let G1 and G2 be two connected simple graphs with the same vertex set V such that for all v ∈ V, the degree of v in G1 is the same as in G2 . It is well known that G2 can be obtained from G1 by a sequence of switches. Moreover, there is one such sequences of switches with only connected graphs. For some classes of graphs, we study the problem of finding bounds for the minimum number of switches required for transforming G1 into G2 such that all graphs in the sequence are connected.

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

M3 - Article

AN - SCOPUS:85129694411

SN - 1034-4942

VL - 83

SP - 87

EP - 100

JO - Australasian Journal of Combinatorics

JF - Australasian Journal of Combinatorics

IS - 1

ER -