Premium
On a leverage problem in the hypercube
Author(s) -
Hamburger Peter,
Pippert Raymond E.,
Douglas Weakley W.
Publication year - 1992
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230220502
Subject(s) - hypercube , combinatorics , leverage (statistics) , mathematics , constructive , hypercube graph , matching (statistics) , graph , discrete mathematics , computer science , line graph , graph power , statistics , process (computing) , operating system
The leverage of a set S of elements (vertices and edges) of a graph G , with respect to a graphical parameter P , is the change induced in P by the removal of S . We consider the case in which G is a hypercube and P is the sum of the distances between vertices. The determination of the minimum leverage of any set of k edges leads to the question of the existence of a perfect matching in which no two edges lie on a 4‐cycle. We give a constructive proof of the existence of such a matching and note additional interesting problems.