Graph Theory » Directed Graphs

Cyclic spanning subdigraph with small cyclomatic number ★★

Author(s): Bondy

Conjecture   Let $ D $ be a digraph all of whose strong components are nontrivial. Then $ D $ contains a cyclic spanning subdigraph with cyclomatic number at most $ \alpha(D) $.

Keywords:

Posted by fhavet
updated June 2nd, 2013
add new comment
Algebra

inverse of an integer matrix ★★

Author(s): Gregory

Question   I've been working on this for a long time and I'm getting nowhere. Could you help me or at least tell me where to look for help. Suppose D is an m-by-m diagonal matrix with integer elements all $ \ge 2 $. Suppose X is an m-by-n integer matrix $ (m \le n) $. Consider the partitioned matrix M = [D X]. Obviously M has full row rank so it has a right inverse of rational numbers. The question is, under what conditions does it have an integer right inverse? My guess, which I can't prove, is that the integers in each row need to be relatively prime.

Keywords: invertable matrices, integer matrices

Posted by lvoyster
updated May 27th, 2013
add new comment