Gallai's path decomposition conjecture for block graphs

1.   Introduction

Graph covering and partitioning problems are among the most classical and central subjects in graph theory. They also have extensive applications in a variety of routing problems, such as robot navigation and city snow plowing planning ^[16]. In this paper, all graphs considered are finite, undirected, and simple. We refer to ^[4] for unexplained terminology and notation.

Let $G = (V(G), E(G))$ be a graph. The order $|V(G)|$ and size $|E(G)|$ are denoted by $n(G)$ and $e(G)$, respectively. The degree and the neighborhood of a vertex $v$ are denoted by $d_G(v)$ and $N_G(v)$, respectively. A vertex is called odd or even depending on whether its degree is odd or even, respectively. A graph in which every vertex is odd or even is called an odd graph or an even graph. The number of odd vertices of $G$ is denoted by $n_o(G)$. The union of simple graphs $G$ and $H$ is the graph $G\cup H$ with vertex set $V(G) \cup V(H)$ and edge set $E(G) \cup E(H)$. Let $X$ be a set of vertices of $V(G)$. We use $G-X$ to denote the graph that arises from $G$ by deleting the set $X$. For any $u, v\in V(G)$, we use $P_{uv}$ to denote the path of $G$ with ends $u$ and $v$. As usual, we use $K_n$ to denote the complete graph of order $n$.

A path decomposition $\mathcal{P}$ of a graph $G$ is a collection of edge-disjoint paths that covers all the edges of $G$. We use $p(G)$ to denote the minimum number of paths needed for a path decomposition of $G$. Erdős asked what is the minimum number of paths into which every connected graph can be decomposed. As a response to the question of Erdős, Gallai made the following conjecture:

Conjecture 1.1 (^[19]). For any connected graph $G$ of order $n$, then $p(G)\leq \lceil\frac{n}{2}\rceil$.

Indeed, one can see that this bound is sharp by considering a graph in which every vertex has an odd degree; then in any path decomposition of $G$, each vertex must be the end vertex of some path, and so at least $\frac{n}{2}$ paths are required. In 1968, Lovász ^[19] proved the following two theorems.

Theorem 1.2 (^[19]). Every graph on $n$ vertices can be decomposed into at most $\frac{n}{2}$ paths and cycles.

Theorem 1.3 (^[19]). Every odd graph on $n$ vertices can be decomposed into $\frac{n}{2}$ paths.

In 1980, Donald ^[12] showed that if $G$ is allowed to be disconnected, then $p(G)\leq \lfloor\frac{3n}{4}\rfloor$, which was improved by Dean and Kouider ^[11], is as follows.

Theorem 1.4 (^[11]). For any graph $G$ with $n$ vertices (possibly disconnected), $p(G)\leq \frac{2n}{3}$.

Furthermore, Conjecture 1.1 was verified for several classes of graphs. Let $G_E$ denote the subgraph of $G$ induced by the vertices of even degree. In 1996, Pyber ^[21] proved the following theorem.

Theorem 1.5 (^[21]). If $G$ is a graph on $n$ vertices such that $G_E$ is a forest, then $p(G)\leq \frac{n}{2}$.

A block of a graph is a maximal 2-connected subgraph of this graph. Theorem 1.5 was strengthened by Fan ^[13], who proved the following.

Theorem 1.6 (^[13]). If $G$ is a graph on $n$ vertices such that each block of $G_E$ is a triangle-free graph of maximum degree at most $3$, then $p(G)\leq \frac{n}{2}$.

The girth of a graph is the length of the shortest cycle in $G$, denoted by $g(G)$. Harding and McGuinness^[15] investigated graphs with high girth and proved the following result.

Theorem 1.7 (^[15]). For any graph $G$ with $g(G)\geq 4$, $p(G)\leq \frac{n_o(G)}{2}+\lfloor(\frac{g(G)+1}{2g(G)})n_e(G)\rfloor$.

In 2022, Chu, Fan, and Zhou ^[10] proved the following result.

Theorem 1.8 (^[10]). For any triangle-free graph $G$ with $n$ vertices, $p(G)\leq \frac{3n}{5}$.

More results regarding Conjecture 1.1 can be found in ^{[3,5,6,7,8,9,13,14,17]}. But in general, it is still open.

A vertex $v$ is a cut vertex of $G$ if the number of components increases in $G-v$. We call a block of $G$ an end block if it exactly contains one cut vertex of $G$. Specifically, if $G$ is a maximal 2-connected graph, we also call $G$ an end block of itself. A maximal complete subgraph of $G$ is called a clique of $G$. For two blocks $A$ and $B$, we call $A$ adjacent to $B$ if $A$ and $B$ have a common vertex. A connected graph is called a block graph if each of its blocks is a clique. A non-complete block graph has at least two blocks. We refer to ^{[1,2,18,20,22]} for some recent results on block graphs. In this paper, we prove that Gallai's conjecture holds for block graphs.

2.   Path decomposition of block graph

In this section, we discuss the path decomposition of block graphs. First, we present a path decomposition of $K_n$, as shown in Lemma 2.1, in which the subscripts of vertices are taken modular $n$.

Lemma 2.1. Let $n$ be a positive integer. If $V(K_n) = \{v_1, v_2, \cdots, v_n\}$, then there exists a path decomposition $\mathcal{P}(K_n)$ of $K_n$ as follows:

(1) if $n$ is even, then $\mathcal{P}(K_n) = \{P_i: 1\leq i\leq \frac n 2\}$, where $P_i = v_iv_{i+1}v_{i+(n-1)}v_{i+2}\cdots v_{i+(\frac{n}{2}+1)}v_{i+\frac{n}{2}}$;

(2) if $n$ is odd, then $\mathcal{P}(K_n) = \{P_{\frac{n+1}{2}}\}\cup \{P'_i: 1\leq i\leq \frac{n-1}{2}\}$, where $P'_i = P_i\setminus E(P_{\frac{n+1}{2}})$, $P_i = v_iv_{i+1}v_{i+(n-1)}v_{i+2}\cdots v_{i+(\frac{n-1}{2})}v_{i+\frac{n+1}{2}}$, and

Thus,

Proof. It is clear that $\mathcal{P}(K_n)$ given in the statement of the lemma is a path decomposition of $K_n$ of cardinality $\frac n 2$ (if $n$ is even) and $\frac {n+1} 2$ (if $n$ is odd). Thus, $p(K_n)\leq \frac n 2$ if $n$ is even, and $p(K_n)\leq \frac {n+1} 2$ if $n$ is odd. On the other hand, since $p(K_n)\geq \frac {n(n-1)} 2 /(n-1) = \frac n 2$, we have

□

Remark 1. For an illustration of the decomposition $\mathcal{P}(K_n)$ of $K_n$ given in the above lemma, one may see it in Figure 1(a) and (b), which are the examples when $n = 6$ and $n = 7$, respectively. It is worth noting that for the case when $n$ is odd, in the decomposition $\mathcal{P}(K_n)$ in the above lemma, by the transitivity of $K_n$, the $\frac{n+1}{2}$ vertices can be selected arbitrarily as the end vertices of exactly two paths, and the remaining $\frac{n-1}{2}$ vertices are not the end vertex of any path of $\mathcal{P}(K_n)$.

For convenience, in the remainder of this paper we will refer to the end vertices of the paths in $\mathcal{P}(K_n)$ simply as the end vertices of $\mathcal{P}(K_n)$. Before proving our main theorem, we tackle some of its special cases.

Lemma 2.2. Let $G$ be a block graph in which all blocks share a common vertex. If all blocks of $G$ have even order, then

where $n$ is the order of $G$ and $r$ is the number of blocks of $G$.

Proof. Let $B_1, \ldots, B_r$ be all blocks of $G$ and $x$ be their common vertex. It is easy to check that $n = \sum_{i = 1}^rn(B_i)-r+1$. If $r$ is odd, then $G$ is odd. By Theorem 1.3, $p(G) = \frac n 2$.

If $r$ is even, then $d_G(x)$ is even, and $n_o(G) = n-1$, and hence $p(G)\geq \frac{n_o(G)}{2} = \frac{n-1}{2}$. By Lemma 2.1, let $\mathcal{P}(B_i)$ be a path decomposition of $B_i$ with $|\mathcal{P}(B_i)| = \frac{n(B_i)} 2$ for each $i\in\{1, \ldots, r\}$. Furthermore, let $P_i$ be the path in $\mathcal{P}(B_i)$ with $x$ as its end. One can see that $\mathcal{P}(G) = \bigcup_{i = 1}^r(\mathcal{P}(B_i)\setminus \{P_i\})\cup \{P_i\cup P_{i+1}: i\in\{1, 3, \cdots, r-1\}\}$ is a path decomposition of $G$ with

Thus, we have $p(G) \leq \frac{n-1}{2}$. This proves $p(G) = \frac{n-1}{2}$ if $r$ is even. □

For any odd integer $t > 0$, let $\mathcal{H}_t$ be the family of graphs, each element $H$ of which is a block graph and obtained from attaching an odd number of cliques with even order to a vertex of $K_t$. We use $c(H)$ to denote the number of cut vertices of $H$. Clearly, $1\leq c(H)\leq t$. For an illustration, one may see an example in Figure 2 for the case when $t = 7$.

Lemma 2.3. Let $t > 0$ be an odd integer. If $H\in \mathcal{H}_t$ with $n$ vertices, then

Proof. Let $V(K_t) = \{v_1, v_2, \cdots, v_t\}$. For each $i\in \{1, 2, \cdots, t\}$, let $G_i$ be a subgraph of $H$ consisting of those blocks containing $v_i$ but $K_t$. In addition, let $r_i$ be the number of the blocks of $G_i$. Since $r_i$ is odd, $G_i$ is odd. By Lemma 2.2, $G_i$ has a path decomposition $\mathcal{P}(G_i)$ with $|\mathcal{P}(G_i)| = \frac{n(G_i)}{2}$. Let $Q_{v_i}\in \mathcal{P}(G_i)$ be the path with $v_i$ as its end vertex.

Let $\mathcal{P}(K_t)$ be a path decomposition of $K_t$ as described in Lemma 2.1. By Remark 1, there are $\frac{t+1}{2}$ vertices (these vertices can be selected arbitrarily) that are the end vertices of $\mathcal{P}(K_t)$ and the remaining $\frac{t-1}{2}$ vertices are not the end vertices of $\mathcal{P}(K_t)$. We use $a$ to denote the number of the cut vertices of $H_t$ that are end vertices of $\mathcal{P}(K_t)$ and $b$ to denote the number of the cut vertices of $H_t$ that are not end vertices of $\mathcal{P}(K_t)$.

Clearly, if $c(H) = 1$ or $c(H) = t$, then $a = b+1$. Now we assume that $2\leq c(H)\leq t-1$. If $c(H)\leq\frac{t+1}{2}$, we choose the all cut vertices of $H$ as the end vertices of $\mathcal{P}(K_t)$. If $c(H) > \frac{t+1}{2}$, we first choose $\frac{t+1}{2}$ cut vertices of $H$ as end vertices of $\mathcal{P}(K_t)$, then the number of remaining cut vertices is at most $\frac{t-3}{2}$. It is easy to obtain that $a\geq b+2$, since $\frac{t+1}{2}-\frac{t-3}{2} = 2$.

For $v_i\in V(K_t)$, if $v_i$ is an end vertex of $\mathcal{P}(K_t)$, then there is a path $P_{v_i}\in \mathcal{P}(K_t)$ with $v_i$ as its end. Clearly, $P_{v_i}\cup Q_{v_i}$ is a path of $H$. Let $V_1 = \{v_i: v_i\ \text{is a cut vertex of}\ H\ \text{and is an end vertex of}\ \mathcal{P}(K_t)\}$ and $V_2 = \{v_i: v_i\ \text{is a cut vertex of}\ H\ \text{and is not an end vertex of}\ \mathcal{P}(K_t)\}$. One can see that

is a path decomposition of $H$ with

On the other hand,

If $a\geq b+2$, then $|\mathcal{P}(H)|\leq \frac{n-1}{2}$, and thus $p(H)\leq \frac{n-1}{2}$. If $a = b+1$, then $|\mathcal{P}(H)|\leq \frac{n}{2}$, and thus $p(H)\leq \frac{n}{2}$. □

Now we will prove our main result.

Theorem 2.4. If $G$ is a non-complete block graph of order $n$, then $p(G)\leq \frac{n}{2}$.

Proof. Let $B_1, \ldots, B_k$ be all blocks of $G$. For each $i\in \{1, 2, \cdots, k\}$, we use $n_i$ to denote the order of $B_i$. Let $\mathcal{P}(B_i)$ be a path decomposition of $B_i$ as described in Lemma 2.1. To show $p(G)\leq \frac{n}{2}$, it is enough to show that $G$ has a path decomposition $\mathcal{P}(G)$ with $|\mathcal{P}(G)|\leq \frac{n}{2}$.

The proof is by induction on $k$. Since $G$ is a non-complete block graph, we have $k\geq 2$. If $k = 2$, then $n = n_1+n_2-1$. Let $x$ be the common vertex of $B_1$ and $B_2$. By Lemma 2.1, for each $i\in\{1, 2\}$, $B_i$ has a path decomposition $\mathcal{P}(B_i)$ in which $x$ can be chosen as an end vertex of $\mathcal{P}(B_i)$. We consider the following three cases.

Case 1. $n_1$ and $n_2$ are even.

By Lemma 2.1, we have $|\mathcal{P}(B_i)| = \frac {n_i} 2$ for each $i\in\{1, 2\}$. Let $P_x$ and $Q_x$ be the two paths of $\mathcal{P}(B_1)$ and $\mathcal{P}(B_2)$ with $x$ as their ends, respectively. Clearly, $P_x\cup Q_x$ is a path of $G$. Thus, $(\mathcal{P}(B_1)\setminus \{P_x\})\cup (\mathcal{P}(B_2)\setminus \{Q_x\})\cup \{P_x\cup Q_x\}$ is a path decomposition of $G$ with cardinality

Case 2. $n_1$ and $n_2$ have distinct parity.

Without loss of generality, assume that $n_1$ is odd and $n_2$ is even. By Lemma 2.1, $\mathcal{P}(B_1)$ is a path decomposition of $B_1$ with $|\mathcal{P}(B_1)| = \frac{n_1+1} 2$ in which $x$ is the end of a path $P_x$. Also, $\mathcal{P}(B_2)$ is a path decomposition of $B_2$ with $|\mathcal{P}(B_2)| = \frac{n_2} 2$ in which $x$ is the end of a path $Q_x$. Let $P_x\cup Q_x$ be a path of $G$. Thus, $(\mathcal{P}(B_1)\setminus \{P_x\})\cup (\mathcal{P}(B_2)\setminus \{Q_x\})\cup \{P_x\cup Q_x\}$ is a path decomposition of $G$ with cardinality

Case 3. $n_1$ and $n_2$ are odd.

By Lemma 2.1, we have $|\mathcal{P}(B_i)| = \frac {n_i+1} 2$ for each $i\in\{1, 2\}$. Let $P^1_x$ and $P^2_x$ be the two paths of $\mathcal{P}(B_1)$ with $x$ as their ends, and $Q^1_x$ and $Q^2_x$ be the two paths of $\mathcal{P}(B_2)$ with $x$ as their ends. Let $P^1_x\cup Q^1_x$ and $P^2_x\cup Q^2_x$ be two paths of $G$. Thus, $(\mathcal{P}(B_1)\setminus \{P^1_x, P^2_x\})\cup (\mathcal{P}(B_2)\setminus \{Q^1_x, Q^2_x\})\cup \{P^1_x\cup Q^1_x, P^2_x\cup Q^2_x\}$ is a path decomposition of $G$ with cardinality

Thus, $p(G)\leq \frac{n}{2}$ for $k = 2$.

Now we consider the case when $k\geq 3$. Assuming that this result is true for any block graph with the number of blocks less than $k$. We consider the following two cases.

Case 1. $G$ has an end block with odd order.

Let $B$ be a block of $G$ with odd order, and $x\in V(B)$ be a cut vertex of $G$. By Lemma 2.1, $\mathcal{P}(B)$ is a path decomposition of $B$ with $|\mathcal{P}(B)| = \frac{n(B)+1} 2$ in which $x$ can be chosen as the end vertex of $\mathcal{P}(B)$. Suppose $Q^1_x$ and $Q^2_x$ are two paths of $\mathcal{P}(B)$ with $x$ as their end vertices. Let $G' = G-(V(B)\setminus \{x\})$. Clearly, $n(G') = n-n(B)+1$. By the induction hypothesis, $G'$ has a path decomposition $\mathcal{P}(G')$ with $|\mathcal{P}(G')|\leq \frac{n-n(B)+1}{2}$. Now we consider the following subcases.

Subcase 1.1. $d_{G'}(x)$ is odd.

Since an odd vertex serves as an end vertex of at least one path in $\mathcal{P}(G')$, $P_x\in \mathcal{P}(G')$ denotes a path with $x$ as its end. Let $Q^1_x \cup P_x$ be a path of $G$. Clearly, $(\mathcal{P}(G')\setminus \{P_x\})\cup (\mathcal{P}(B)\setminus \{Q^1_x\})\cup \{Q^1_x \cup P_x\}$ is a path decomposition of $G$ with cardinality

Subcase 1.2. $d_{G'}(x)$ is even.

Since $d_{G'}(x)$ is even, there are at least two paths in $\mathcal{P}(G')$ with $x$ as their ends, or there are no such paths at all.

First assume that there are two paths $P_x^1$ and $P_x^2$ in $\mathcal{P}(G')$ with $x$ as their ends. Let $P_x^1 \cup Q^1_x$ and $P_x^2 \cup Q^2_x$ be two paths of $G$. Obviously, $(\mathcal{P}(G')\setminus \{P_x^1, P_x^2\})\cup (\mathcal{P}(B)\setminus \{Q^1_x, Q^2_x\})\cup \{P_x^1 \cup Q^1_x, P_x^2 \cup Q^2_x\}$ is a path decomposition of $G$ with cardinality

Now assume that there is no path in $\mathcal{P}(G')$ with $x$ as its end. Assuming that $P_{uv}\in\mathcal{P}(G')$ containing $x$. Let $P_{ux}$ and $P_{xv}$ be subpaths of $P_{uv}$. Clearly, $P_{ux} \cup Q^1_x$ and $P_{xv} \cup Q^2_x$ be two paths of $G$. Hence $(\mathcal{P}(G')\setminus \{P_{uv}\})\cup (\mathcal{P}(B)\setminus \{Q^1_x, Q^2_x\})\cup \{P_{ux} \cup Q^1_x, P_{xv} \cup Q^2_x\}$ is a path decomposition with cardinality

Case 2. All end blocks in $G$ have even order.

If all blocks of $G$ are end blocks, then they share the same vertex. By Lemma 2.2, $p(G)\leq \frac n 2$. So, next assume that not all blocks of $G$, are end blocks. Take an end block $B$ of $G$. Suppose $x\in V(B)$ is the cut vertex of $G$ and the end blocks containing $x$ are $B^1, B^2, \cdots, B^r$ where $B^1 = B$. Let $H = \bigcup_{i = 1}^rB^i$ and $G'' = G-(V(H)\setminus \{x\})$ (see Figure 3). Trivially, $n(G'') = n-n(H)+1$. By the induction hypothesis, $G''$ has a path decomposition $\mathcal{P}(G'')$ with $|\mathcal{P}(G'')|\leq \frac{n-n(H)+1}{2}$.

Subcase 2.1. There exists such a subgraph $H$ with $r$ being even.

By Lemma 2.2, $H$ has a path decomposition $\mathcal{P}(H)$ with $|\mathcal{P}(H)| = \frac{n(H)-1} 2$. Clearly, $\mathcal{P}(G'')\cup \mathcal{P}(H)$ is a path decomposition of $G$ with cardinality

Subcase 2.2. For each $H$, $r$ is odd.

Since $r$ is odd, $H$ is odd. By Theorem 1.3, $H$ has a path decomposition $\mathcal{P}(H)$ with $|\mathcal{P}(H)| = \frac{n(H)} 2$ in which $x$ is the end of a path $Q_x$. Let $G_0$ be the graph obtained from $G$ after deleting all end blocks. Assume that $A$ is an end block of $G_0$ containing $x$. We consider the following two subcases.

Subcase 2.2.1. The order of $A$ is even.

Since the order of $A$ is even, $d_A(x)$ is odd. Moreover, by $d_{G''}(x) = d_A(x)$, $d_{G''}(x)$ is odd. Thus, there must exist a path $P_x$ in $\mathcal{P}(G'')$ with $x$ as its end vertex. Let $P_x\cup Q_x$ be a path of $G$. One can see that $(\mathcal{P}(G'')\setminus \{P_x\})\cup (\mathcal{P}(H)\setminus \{Q_x\})\cup \{P_x \cup Q_x\}$ is a path decomposition with cardinality

Subcase 2.2.2. The order of $A$ is odd.

If $G_0$ is a complete graph, by Lemma 2.3, $p(G)\leq \frac{n}{2}$. Now we assume that $G_0$ is not a complete graph. Let $y\in V(A)$ be the cut vertex of $G_0$. Let $G''' = G-(V(H')\setminus \{y\})$, where $H'$ is the union of $A$ and the end blocks of $G$ that contain the vertices of $A$ other than $y$ (see Figure 4). By the induction hypothesis, $G'''$ has a path decomposition $\mathcal{P}(G''')$ with $|\mathcal{P}(G''')|\leq \frac{n(G''')}{2}$. Now we consider the following two cases.

(1) If there is only one cut vertex $x$ in $H'$, by Lemma 2.3, $H'$ has a path decomposition $\mathcal{P}(H')$ with $|\mathcal{P}(H')|\leq \frac{n(H')}{2}$, in which $x$ and $y$ are the end vertices of $\mathcal{P}(A)$. We denote $Q_y^1, Q_y^2\in \mathcal{P}(H')$ as two paths with $y$ as their ends. On the other hand, there must exist a path $P_{uv}\in \mathcal{P}(G''')$ pass through $y$. Let $P_{uy}$ and $P_{yv}$ be subpaths of $P_{uv}$. Clearly, $P_{uy}\cup Q_y^1$ and $P_{yv}\cup Q_y^2$ are two paths of $G$. Thus, $(\mathcal{P}(G''')\setminus \{P_{uv}\})\cup (\mathcal{P}(H')\setminus \{Q^1_y, Q^2_y\})\cup \{P_{uy} \cup Q^1_y, P_{yv} \cup Q^2_y\}$ is a path decomposition of $G$ with cardinality

(2) If there are at least two cut vertices in $H'$, by Lemma 2.3, $H'$ has a path decomposition $\mathcal{P}(H')$ with $|\mathcal{P}(H')| = \frac{n(H')-1}{2}$. Hence $\mathcal{P}(G''')\cup \mathcal{P}(H')$ is a path decomposition of $G$ with cardinality

The proof is now finished. □

Author contributions

X.C.: Conceptualization, Funding acquisition, Methodology, Validation, Visualization, Writing-original draft; B.W.: Funding acquisition, Methodology, Project administration, Supervision, Validation, Visualization, Writing-review and editing. All authors have read and agreed to the published version of the manuscript.

Use of Generative-AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This research is supported by NSFC (No.12061073) and the Research Innovation Program for Postgraduates of Xinjiang Uygur Autonomous Region under Grant No. XJ2023G020.

Conflict of interest

All authors declare no conflicts of interest in this paper.