1
$\begingroup$

Let $G=(V,E)$ be a graph. For $v\in V$ we set $N(v) = \{w\in V: \{v,w\}\in E\}$. Let us say that a graph is neighborly if there is an injective function $f: V\to V$ such that $f(v)\in N(v)$ for all $v\in V$. (Is there standard terminology for this? Any pointers appreciated!)

If a graph has a Hamiltonian cycle, let's call it a HC-graph. It is easy to see that HC-graphs are neighborly, as well as unions of HC-graphs, each of which has more than 1 vertex.

Is the following statement correct?

(?): If a finite graph $G=(V,E)$ is neighborly, then there is a partition of $V$ into subgraphs, each of which is a HC-graph and consists of more than 1 point.

(Remark: The nice thing about this definition is that there are neighborly graphs for any finite or infinite cardinality, but it is not obvious how to generalise Hamiltonian cycles to infinite graphs.)

$\endgroup$
1
  • $\begingroup$ Good remark, and you're right. $K_2$ is a HC-graph, and any graph that has a perfect matching can be partitioned into copies of $K_2$. My mistake was "more than 2" instead of "more than one" in the formulation of the statement. Just corrected this. $\endgroup$ Commented Mar 11, 2015 at 9:25

1 Answer 1

2
$\begingroup$

I think this is true and trivial, and not really research-level.

Since $V$ is finite and $f$ is injective, it is a permutation. Write it as a union of disjoint cycles.

Assuming the graph has no loop, $f$ has no fixed point and thus every cycle has length at least two.

The graph induced on each cycle is clearly HC, in fact the cycle of the permutation itself gives the graph cycle. Thus the orbits of the group generated by $f$ give the required partition.

All of this is clearly reversible.

In other words, being neighborly is equivalent to containing a spanning subgraph that is a union of cycle, which is equivalent to being able to partition the vertex set such that the graph induced on each part is Hamiltonian.

(Note that, in all of the above, I am assuming that we consider K2 to be a degenerate cycle, as in your comment.)

$\endgroup$
4
  • $\begingroup$ Moreover, I think Hamiltonian cycles generalise in a straightforward way to infinite graphs. After all, a HC is simply a 2-valent spanning subgraph. This works in the infinite case as well and is well-accepted I think. $\endgroup$
    – verret
    Commented Mar 11, 2015 at 10:07
  • $\begingroup$ Since the OP defined "neighborly" with an injection rather than a bijection, the components of an infinite "neighborly" graph may have vertices of degree one. $\endgroup$
    – bof
    Commented Mar 11, 2015 at 10:20
  • $\begingroup$ Sure, the equivalences don't necessarily hold for infinite graphs, I was simply answering the remark in the OP that there isn't an obvious way to generalise HC. $\endgroup$
    – verret
    Commented Mar 11, 2015 at 11:23
  • $\begingroup$ Anyway, since the OP counts $K_2$ as a cycle, there is no need for infinite cycles in the partition, unless one has qualms about the axiom of choice. $\endgroup$
    – bof
    Commented Mar 11, 2015 at 11:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .