https://www.mdu.se/

mdu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Making multigraphs simple by a sequence of double edge swaps
Mälardalen University, School of Education, Culture and Communication, Educational Sciences and Mathematics. (MAM)
2021 (English)In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 344, no 5, article id 112328Article in journal (Refereed) Published
Abstract [en]

We show that any loopy multigraph with a graphical degree sequence can be transformed into a simple graph by a finite sequence of double edge swaps with each swap involving at least one loop or multiple edge. Our result answers a question of Janson motivated by random graph theory, and it adds to the rich literature on reachability of double edge swaps with applications in Markov chain Monte Carlo sampling from the uniform distribution of graphs with prescribed degrees. 

Place, publisher, year, edition, pages
Elsevier B.V. , 2021. Vol. 344, no 5, article id 112328
Keywords [en]
Alternating rectangle, Checkerboard swap, Degree-preserving rewiring, Double edge swap, Graphical degree sequence, Tetrad
National Category
Mathematics
Identifiers
URN: urn:nbn:se:mdh:diva-53576DOI: 10.1016/j.disc.2021.112328ISI: 000633365200019Scopus ID: 2-s2.0-85100896427OAI: oai:DiVA.org:mdh-53576DiVA, id: diva2:1534444
Available from: 2021-03-05 Created: 2021-03-05 Last updated: 2021-04-22Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Sjöstrand, Jonas

Search in DiVA

By author/editor
Sjöstrand, Jonas
By organisation
Educational Sciences and Mathematics
In the same journal
Discrete Mathematics
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 71 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf