Seating rearrangements on arbitrary graphs

DeFord, Daryl

doi:10.2140/involve.2014.7.787

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

Seating rearrangements on arbitrary graphs

Daryl DeFord

Vol. 7 (2014), No. 6, 787–805

DOI: 10.2140/involve.2014.7.787

Abstract

We exhibit a combinatorial model based on seating rearrangements, motivated by some problems proposed in the 1990s by Kennedy, Cooper, and Honsberger. We provide a simpler interpretation of their results on rectangular grids, and then generalize the model to arbitrary graphs. This generalization allows us to pose a variety of well-motivated counting problems on other frequently studied families of graphs.

Keywords

matrix permanents, cycle covers, tilings, recurrence relations

Mathematical Subject Classification 2010

Primary: 05C30

Milestones

Received: 4 November 2013

Revised: 3 January 2014

Accepted: 24 January 2014

Published: 20 October 2014

Communicated by Kenneth S. Berenhaut

Authors

Daryl DeFord
Department of Mathematics Dartmouth College 27 North Main Street Hanover, NH 03755 United States

Vol. 7, No. 6, 2014