0
$\begingroup$

A well-known Theorem of Tutte gives a sufficient and necessary condition for a graph to have a perfect matching (i.e., perfect $P_2$-packing):

A graph $G$ has a perfect matching if and only if, for every subset $S$ of $V(G)$, the number of odd components of $G-S$ is at most $|S|$. Symbolically, $$\forall S\subseteq V(G), |S| \geq \text{odd}(G-S)$$

My question is this: What analogues of this result are known for perfect $P_3$-packings? I know that the problem of determining whether partitioning the vertices of a graph into copies of $P_3$ is in general NP hard, so maybe a necessary and sufficient condition is a bit of a stretch. But I am interested in any result of this kind, sufficient and / or necessary, possibly for limited classes of graphs.

To be specific, I am looking for conditions of the following form:

The graph $G$ has a perfect $P_3$-packing if / only if, for every subset $S$ of $V(G)$, we have $$|S|\geq f(G-S)$$ where $f: \mathcal{G}\to \mathbb{R}$ is some function that takes a graph $H$ and returns a number that depends on the size and number of the components of $H$.


Terminology: A perfect $P_n$-packing of a graph is a partition of the vertex set of the graph so that each part of the partition induces a subgraph with a spanning path $P_n$.

A perfect matching of a graph is a set of edges that partition the vertex-set of the graph (i.e., a perfect $P_2$-packing).

$\text{odd}(H)$ is the number of components of the graph $H$ that have an odd number of vertices.

$P_3$-packings are also sometimes known as $\Lambda$-packings, and perfect $P_3$-packings are sometimes called $P_3$-factors or $\Lambda$-factors.

$\endgroup$

1 Answer 1

1
$\begingroup$

Here's one possible condition of this form; it is necessary, but not sufficient.

For a graph $G$ with connected components $G_1, G_2, \dots, G_k$, let $o_{m}(G) = \sum_{i=1}^k (|V(G_i)| \bmod m)$. This generalizes the function in Tutte's theorem: $o_2(G)$ just counts the number of odd components in $G$.

If $G$ has a perfect $P_3$-packing, then we must have $$|S| \ge \frac12 o_3(G-S)$$ for all $S \subseteq V(G)$. The reasoning is: the best $P_3$-packing in $G-S$ must leave at least $o_3(G-S)$ vertices uncovered, because it leaves at least $|V(G_i)| \bmod 3$ vertices of $G_i$ uncovered for each $i$. Therefore in a perfect $P_3$-packing of $G$, the uncovered vertices must be covered by copies of $P_3$ that overlap $S$. We need a vertex of $S$ for every two uncovered vertices of $G-S$: a copy of $P_3$ split between $S$ and $G-S$ can, at best, have one vertex from $S$ and two from $G-S$. The inequality follows.

The smallest graph for which this condition is not sufficient is the net graph:

enter image description here

This has no perfect $P_3$-packing, but satisfies the $o_3$ condition:

  • When $|S|=0$, the condition is satisfied because the number of vertices is divisible by $3$.
  • When $|S|=1$, $G-S$ can either have one component of size $5$ or two of size $1$ and $4$. Both give $o_3(G-S)=2$, which is fine.
  • When $|S| \ge 2$, then $|V(G-S)| \le 4$, so $o_3(G-S) \le 4$ and the condition can't fail.

Experimentally, though, the condition is not too weak. Mathematica's GraphData database knows $7$ connected $6$-vertex graphs with no perfect $P_3$-packing, $44$ connected $9$-vertex graphs with no perfect $P_3$-packing, and $11$ connected $12$-vertex graphs with no perfect $P_3$-packing. Of these, only two satisfy the $o_3$ condition for all sets $S$: the net graph, and a graph obtained from this one by adding leaves to the four degree-$3$ vertices. (I should point out that for large numbers of vertices, Mathematica's graph database is not necessarily representative, but it's what I had lying around.)


As a matter of complexity theory, we shouldn't hope very hard for a necessary and sufficient condition like this; let me summarize why. If we had one, and if the function $f(G-S)$ were efficiently computable, it would put the $P_3$-packing problem in co-NP: it would give a short, efficiently checkable proof that a graph has no $P_3$-packing. We do not expect NP-complete problems to be in co-NP: though this does not imply P=NP, it still makes the polynomial hierarchy sad.

$\endgroup$
1
  • $\begingroup$ Thanks for the detailed answer! The function you found is what I had in mind so far, and was rather hopeful that there was some refinement of it known / some good class of graphs for which it was sufficient, but alas. (It is sufficient for graphs that are both claw and net-free, but for silly reasons). $\endgroup$ Commented May 24, 2022 at 17:32

You must log in to answer this question.

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