Skip to main content
added 312 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

No, this is not true. Let $G$ be the bowtie graph (this is the graph obtained by gluing two triangles at a vertex $u$). Then, $G$ does not have a spanning regular subgraph, but $\mathbb{1}$ is in the row space of $G$. Just set $x_e=\frac{1}{4}$ if $e$ is adjacent to $u$ and $x_e=\frac{3}{4}$ for the other two edges.

The exact characterization of when $\mathbb{1}$ is in the row space of $G$ can be extracted from Chris Godsil's answer.

Characterization. $\mathbb{1}$ is in the row space of $G$ if and only if each bipartite component of $G$ is balanced (the left and right sides have the same number of vertices).

No, this is not true. Let $G$ be the bowtie graph (this is the graph obtained by gluing two triangles at a vertex $u$). Then, $G$ does not have a spanning regular subgraph, but $\mathbb{1}$ is in the row space of $G$. Just set $x_e=\frac{1}{4}$ if $e$ is adjacent to $u$ and $x_e=\frac{3}{4}$ for the other two edges.

No, this is not true. Let $G$ be the bowtie graph (this is the graph obtained by gluing two triangles at a vertex $u$). Then, $G$ does not have a spanning regular subgraph, but $\mathbb{1}$ is in the row space of $G$. Just set $x_e=\frac{1}{4}$ if $e$ is adjacent to $u$ and $x_e=\frac{3}{4}$ for the other two edges.

The exact characterization of when $\mathbb{1}$ is in the row space of $G$ can be extracted from Chris Godsil's answer.

Characterization. $\mathbb{1}$ is in the row space of $G$ if and only if each bipartite component of $G$ is balanced (the left and right sides have the same number of vertices).

Post Undeleted by Tony Huynh
Post Deleted by Tony Huynh
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

No, this is not true. Let $G$ be the bowtie graph (this is the graph obtained by gluing two triangles at a vertex $u$). Then, $G$ does not have a spanning regular subgraph, but $\mathbb{1}$ is in the row space of $G$. Just set $x_e=\frac{1}{4}$ if $e$ is adjacent to $u$ and $x_e=\frac{3}{4}$ for the other two edges.