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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom