Skip to main content
MathOverflow

Return to Question

removed capitals from title
Link
YCor
YCor
  • 63.9k
  • 5
  • 187
  • 286

Characterizing graphs whose Incidence Matrixincidence matrix has the all ones vector in its row span

deleted 1 character in body; edited tags
Source Link
Tony Huynh
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Suppose we have a simple connected graph $G=(V,E)$. Then let $A$ be its $|E|\times |V|$ incidence matrix. Here I am considering the unoriented incidence matrix. I want to knownknow when the row span of $A$ contains the all ones vector in $\mathbb{R}^{|V|}$. I believe this happens if and only if $G$ has a spanning regular subgraph. One direction is of course clear. Does anyone know if this is true/ have a counterexample?

Suppose we have a simple connected graph $G=(V,E)$. Then let $A$ be its $|E|\times |V|$ incidence matrix. Here I am considering the unoriented incidence matrix. I want to known when the row span of $A$ contains the all ones vector in $\mathbb{R}^{|V|}$. I believe this happens if and only if $G$ has a spanning regular subgraph. One direction is of course clear. Does anyone know if this is true/ have a counterexample?

Suppose we have a simple connected graph $G=(V,E)$. Then let $A$ be its $|E|\times |V|$ incidence matrix. Here I am considering the unoriented incidence matrix. I want to know when the row span of $A$ contains the all ones vector in $\mathbb{R}^{|V|}$. I believe this happens if and only if $G$ has a spanning regular subgraph. One direction is of course clear. Does anyone know if this is true/ have a counterexample?

Source Link
batconjurer
batconjurer
  • 928
  • 4
  • 11

Characterizing graphs whose Incidence Matrix has the all ones vector in its row span

Suppose we have a simple connected graph $G=(V,E)$. Then let $A$ be its $|E|\times |V|$ incidence matrix. Here I am considering the unoriented incidence matrix. I want to known when the row span of $A$ contains the all ones vector in $\mathbb{R}^{|V|}$. I believe this happens if and only if $G$ has a spanning regular subgraph. One direction is of course clear. Does anyone know if this is true/ have a counterexample?