Connectedness of friends-and-strangers graphs of complete bipartite graphs and others

Abstract: Let

X

and

Y

be any two graphs of order

n

. The friends-and-strangers graph

m a t h s f F S (X, Y)

of

X

and

Y

is a graph with vertex set consisting of all bijections

s i g m a : V (X) m a p s t o V (Y)

, in which two bijections

s i g m a

,

s i g m a^{'}

are adjacent if and only if they differ precisely on two adjacent vertices of

X

, and the corresponding mappings are adjacent in

Y

. The most fundamental question that one can ask about these friends-and-strangers graphs is whether or not they are connected. Let

K_{k, n - k}

be a complete bipartite graph of order

n

. In 1974, Wilson characterized the connectedness of

m a t h s f F S (K_{1, n - 1}, Y)

by using algebraic methods. In this paper, by using combinatorial methods, we investigate the connectedness of

m a t h s f F S (K_{k, n - k}, Y)

for any

Y

and all

k g e 2

, including

Y

being a random graph, as suggested by Defant and Kravitz, and pose some open problems.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Connectedness of friends-and-strangers graphs of complete bipartite graphs and others