We show that if the two parts of a finite bipartite graph have the same degree sequence, then there is a bipartite graph, with the same degree sequences, which is symmetric, in that it has an involutive graph automorphism that interchanges its two parts. To prove this, we study the relationship between symmetric bipartite graphs and graphs with loops.

Source : oai:HAL:hal-01196863v1

Volume: Vol. 17 no. 1

Section: Graph Theory

Published on: February 12, 2015

Submitted on: June 3, 2014

Keywords: bipartite graphs,degree sequence,symmetry,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

This page has been seen 110 times.

This article's PDF has been downloaded 578 times.