Kragujevac J. Math. 22 (2000) 57-66.
|
ON PERMUTATIONS IN BIPARTITE GRAPHS
|
|
Ivan Gutman
|
|
Faculty of Science, P. O. Box 60, 34000 Kragujevac,
Yugoslavia
|
|
(Received July 19, 2000)
|
ABSTRACT. Let G be a graph whose vertices are labeled by 1, 2, ¼, n . A permutation P : [1, 2, ¼, n] ® [P(1), P(2), ¼, P(n)] is said to be a graphic permutation of G if the vertices i and P(i) of G are adjacent for all i=1, 2, ¼, n . It is shown that a bipartite graph with m perfect matchings has m2 graphic permutations. Some consequences of this result on the determinant of the adjacency matrix of a bipartite graph are pointed out.