Multi-decomposition of graphs into paths and $Y$-trees of order five

A, Chaadhanaa; P, Hemalatha

doi:10.61091/jcmcc123-09

Abstract

1. Introduction
2. Multi-decomposition of complete graphs into P5 and Y5
3. Multi-decomposition of complete bipartite graphs into P5 and Y5
4. Conclusion

References

Journal of Combinatorial Mathematics and Combinatorial Computing

Volume 123
Pages: 123-134

Research article

Multi-decomposition of graphs into paths and $Y$ -trees of order five

^¹, ^¹

¹Department of Mathematics, Vellalar College For Women, Tamil Nadu, India

Received: 19/11/2024
Accepted: 05/12/2024
Published: 31/12/2024

Copyright Link
License

Abstract

Let $K_{n}$ , $P_{n}$ , and $Y_{n}$ respectively denote a complete graph, a path, and a $Y$ -tree on $n$ vertices, and let $K_{m, n}$ denote a complete bipartite graph with $m$ and $n$ vertices in its parts. Graph decomposition is the process of breaking down a graph into a collection of edge-disjoint subgraphs. A graph $G$ has a $(H_{1}, H_{2})$ -multi-decomposition if it can be decomposed into $α \geq 0$ copies of $H_{1}$ and $β \geq 0$ copies of $H_{2}$ , where $H_{1}$ and $H_{2}$ are subgraphs of $G$ . In this paper, we derive the necessary and sufficient conditions for the $(P_{5}, Y_{5})$ -multi-decomposition of $K_{n}$ and $K_{m, n}$ .

Keywords: Path,

Y

-Tree, Multi-decomposition, Complete graph, Complete bipartite graph, Conjoined Twins

1. Introduction

All graphs considered in this paper are finite, simple, and undirected. Let $K_{n}$ denote a complete graph on $n$ vertices, $K_{m, n}$ a complete bipartite graph with vertex partite sets of cardinality $m$ and $n$ , and $P_{k}$ a path on $k$ vertices. A $Y$ -tree on $k$ vertices, denoted by $Y_{k}$ , is a tree in which one edge is attached to a vertex $v$ of the path $P_{k - 1}$ such that at least one of the adjacent vertices of $v$ has degree 1.

A decomposition of a graph $G$ is a set of edge-disjoint subgraphs $H_{1}, H_{2}, \dots, H_{r}$ of $G$ such that every edge of $G$ belongs to exactly one $H_{i}$ , $1 \leq i \leq r$ . If all the subgraphs in the decomposition of $G$ are isomorphic to a graph $H$ , then $G$ is said to be $H$ -decomposable. If $G$ can be decomposed into $α$ copies of $H_{1}$ and $β$ copies of $H_{2}$ , then $G$ is said to have an $(H_{1}, H_{2})$ -multi-decomposition or an ${H_{1}^{α}, H_{2}^{β}}$ -decomposition. The pair $(α, β)$ is called admissible if it satisfies the necessary conditions for the existence of an ${H_{1}^{α}, H_{2}^{β}}$ -decomposition. If $G$ has an $(H_{1}, H_{2})$ -multi-decomposition for all admissible pairs $(α, β)$ , it is said to have an $(H_{1}, H_{2})_{{α, β}}$ -decomposition.

The necessary and sufficient condition for the existence of a $P_{5}$ -decomposition of complete graphs was studied in [5], and for complete bipartite graphs in [1]. The path decomposition of various graphs was explored in [15,11]. The graph $Y_{5}$ is one of the three non-isomorphic trees of order five, excluding paths and stars. Caterina and Antonio [3] named $Y_{5}$ as the chair and studied the stability number of chair-free graphs.

The $Y_{5}$ -decomposition of complete graphs was obtained by C. Huang and A. Rosa [5]. J. Paulraj Joseph and A. Samuel Issacraj [8] referred to $Y_{5}$ as the fork and studied its decomposition in complete bipartite graphs. S. Gomathi and A. Tamil Elakkiya [4] defined this graph as a $Y_{5}$ -tree and investigated its decomposition in the tensor product of complete graphs. The $Y_{5}$ -decomposition of various graphs was further analyzed in [9,10]. The concept of multi-decomposition was introduced by A. Abueida and M. Daven [2]. In recent years, multi-decomposition of graphs has emerged as a prominent research area in graph theory. T.-W. Shyu studied the multi-decomposition of complete graphs into paths with cycles and stars [12,13]. S. Jeevadoss and A. Muthusamy established necessary and sufficient conditions for the multi-decomposition of complete bipartite graphs into paths and cycles [6]. Multi-decomposition of complete bipartite graphs into paths and stars was considered in [14].

In this paper, we establish the necessary and sufficient conditions for the existence of a $(P_{5}, Y_{5})$ -multi-decomposition of $K_{n}$ and $K_{m, n}$ . To prove our results, we recall the following theorems:

Theorem 1.1. [5] The complete graph

K_{n}

Y_{5}

-decomposable if and only if

n \equiv 0 (\mod 8)

Theorem 1.2. [1] Let

k, m,

and

n

be positive integers. The necessary conditions for a

P_{k + 1}

-decomposition of

K_{m, n}

are listed in Table 1, and these conditions are also sufficient.

Table 1 Necessary and sufficient conditions for a $P_{k + 1}$ -decomposition of $K_{m, n}$
Case	$k$	$m$	$n$	Characterization
1.	even	even	even	$k \leq 2 m, k \leq 2 n,$ not both equal
2.	odd	even	even	Equalities hold when $k$ is even
3.	even	even	odd	$k \leq 2 m - 2, k \leq 2 n$
4.	even	odd	even	$k \leq 2 m, k \leq 2 n - 2$
5.	even	odd	odd	Decomposition impossible
6.	odd	even	odd	$k \leq 2 m - 1, k \leq n$
7.	odd	odd	even	$k \leq m, k \leq 2 n - 1$
8.	odd	odd	odd	$k \leq m, k \leq n$

Theorem 1.3. [8] The complete bipartite graph

K_{m, n}

is fork-decomposable if and only if

m n \equiv 0 (\mod 4)

, except for

K_{2, 4 i + 2}

(i = 1, 2, \dots)

2. Multi-decomposition of complete graphs into $P_{5}$ and $Y_{5}$

2.1. Preliminaries

Definition 2.1. [7] For a graph

G

, two disjoint subsets of vertices are called twins if they have the same order and induce subgraphs with the same number of edges.

Next, we introduce a new graph structure called Conjoined Twins in the following remark.

Remark 2.2. Consider the graph

T

with vertex set

{v_{i} : 1 \leq i \leq 8}

The subgraphs induced by $A$ and $B$ are isomorphic to $P_{5}$ when $A = {v_{1}, v_{2}, v_{6}, v_{7}, v_{8}}$ and $B = {v_{2}, v_{3}, v_{4}, v_{5}, v_{6}}$ . Similarly, if $A = {v_{1}, v_{2}, v_{3}, v_{4}, v_{8}}$ and $B = {v_{4}, v_{5}, v_{6}, v_{7}, v_{8}}$ , the corresponding induced subgraphs are isomorphic to $Y_{5}$ . We call these subsets of vertices Conjoined Twins $(T)$ because the subsets $A$ and $B$ are not disjoint (there are two common vertices), but the induced subgraphs are isomorphic.

It is interesting to note that the subgraph induced by $A$ is isomorphic to $P_{5}$ when $A = {v_{1}, v_{2}, v_{3}, v_{8}, v_{6}}$ , and if $B = {v_{3}, v_{4}, v_{5}, v_{6}, v_{7}}$ , the corresponding induced subgraph is isomorphic to $Y_{5}$ .

Thus, decomposing the graph $G$ into a structure whose vertices are Conjoined Twins as in Figure 1 can be viewed as consisting of $2$ copies of $P_{5}$ , $2$ copies of $Y_{5}$ , or $1$ copy each of $P_{5}$ and $Y_{5}$ , which significantly simplifies the $(P_{5}, Y_{5})$ -multi-decomposition.

2.2. Notations

For a subgraph $H$ of $G$ , $G ∖ H$ denotes a graph where $V (G ∖ H) = V (G)$ and $E (G ∖ H) = E (G) - E (H)$ .
$r G$ denotes $r$ disjoint copies of the graph $G$ .
$G = H_{1} \oplus H_{2}$ means $G$ can be decomposed into $H_{1}$ and $H_{2}$ .
Let $v_{i}$ , $1 \leq i \leq n$ , be the vertices of the complete graph $K_{n}$ .
In the complete bipartite graph $K_{m, n}$ , the vertices of the first partite set with $m$ vertices are denoted by $v_{1 i}$ , $1 \leq i \leq m$ , and the second partite set with $n$ vertices by $v_{2 j}$ , $1 \leq j \leq n$ .
A path $P_{5}$ with $5$ vertices $v_{i}$ , $1 \leq i \leq 5$ , having $v_{1}$ and $v_{5}$ as pendant vertices is denoted by $P_{5} (v_{1}, v_{2}, v_{3}, v_{4}, v_{5})$ .
The $Y_{5}$ graph with $5$ vertices $v_{i}$ , $1 \leq i \leq 5$ , is denoted by $Y_{5} (v_{1}, v_{2}, \underline{v_{3}}, v_{4}; \underline{v_{5}})$ , where $v_{i}$ , $1 \leq i \leq 4$ , form a path of length three, and the underlined vertices denote an edge $v_{3} v_{5}$ .
Suppose we have a graph whose vertices are Conjoined Twins $(T)$ as in Figure 1. We denote it by $T (v_{1}, \underline{v_{2}}, v_{3}, v_{4}, v_{5}, \underline{v_{6}}, v_{7}; \underline{v_{8}})$ , where $v_{i}$ , $1 \leq i \leq 7$ , form a path of length six, and the underlined vertices denote edges $v_{2} v_{8}$ and $v_{6} v_{8}$ .

Remark 2.3. If two graphs

G_{1}

and

G_{2}

have an

(H_{1}, H_{2})

-multi-decomposition, then

G_{1} \oplus G_{2}

also has such a decomposition.

2.3. Necessary condition

The following theorem gives the necessary condition for the existence of a multi-decomposition of the complete graph $K_{n}$ into paths and $Y$ -trees with 5 vertices.

Theorem 2.4. If

K_{n}

has a

(P_{5}, Y_{5})

– multi-decomposition, then

n \equiv 0 o r 1 (m o d 8)

Proof. Proof follows from the edge divisibility condition.

2.4. Sufficient conditions

In this section, we show that the necessary condition obtained in Theorem 2.4 is also sufficient for the existence of a multi-decomposition of $K_{n}$ , ( $n \geq 8$ ) into $P_{5}$ and $Y_{5}$ .

Lemma 2.5. The Complete graphs

K_{8}

and

K_{9}

have

(P_{5}, Y_{5})

– multi-decomposition.

Proof. $K_{8} = 3 T \oplus 1 P_{5}$ , where the $3 T$ ’s and $1 P_{5}$ are given by, $\begin{aligned} T (v_{6}, \underline{v_{7}}, v_{5}, v_{1}, v_{4}, \underline{v_{8}}, v_{2}; \underline{v_{3}}), T (v_{3}, \underline{v_{6}}, v_{4}, v_{2}, v_{5}, \underline{v_{8}}, v_{7}; \underline{v_{1}}), \\ T (v_{8}, \underline{v_{6}}, v_{5}, v_{3}, v_{1}, \underline{v_{7}}, v_{4}; \underline{v_{2}}), P_{5} (v_{1}, v_{2}, v_{3}, v_{4}, v_{5}) . \end{aligned}$

Similarly, $K_{9}$ can be written as $K_{9} = 4 T \oplus 1 P_{5}$ , where the $4 T$ ’s and $1 P_{5}$ are as follows: $\begin{aligned} T (v_{3}, \underline{v_{6}}, v_{4}, v_{1}, v_{8}, \underline{v_{7}}, v_{5}; \underline{v_{2}}), T (v_{3}, \underline{v_{9}}, v_{4}, v_{2}, v_{5}, \underline{v_{6}}, v_{1}; \underline{v_{7}}), \\ T (v_{4}, \underline{v_{8}}, v_{5}, v_{3}, v_{1}, \underline{v_{9}}, v_{2}; \underline{v_{6}}), T (v_{4}, \underline{v_{7}}, v_{1}, v_{5}, v_{9}, \underline{v_{8}}, v_{2}; \underline{v_{3}}), P_{5} (v_{1}, v_{2}, v_{3}, v_{4}, v_{5}) . \end{aligned}$

Lemma 2.6. The Complete bipartite graphs

K_{7, 8}

K_{8, 8}

and

K_{9, 8}

have

(P_{5}, Y_{5})

– multi-decomposition.

Proof. It is clear that $K_{7, 8} = 7 T$ , where $7 T$ ’s are given by, $\begin{aligned} T (v_{21}, \underline{v_{11}}, v_{23}, v_{12}, v_{24}, \underline{v_{13}}, v_{22}; \underline{v_{25}}), T (v_{25}, \underline{v_{12}}, v_{22}, v_{11}, v_{26}, \underline{v_{13}}, v_{23}; \underline{v_{21}}), \\ T (v_{24}, \underline{v_{11}}, v_{28}, v_{15}, v_{26}, \underline{v_{14}}, v_{25}; \underline{v_{27}}), T (v_{24}, \underline{v_{14}}, v_{28}, v_{13}, v_{27}, \underline{v_{15}}, v_{25}; \underline{v_{23}}), \\ T (v_{27}, \underline{v_{12}}, v_{28}, v_{17}, v_{24}, \underline{v_{16}}, v_{25}; \underline{v_{26}}), T (v_{28}, \underline{v_{16}}, v_{21}, v_{14}, v_{22}, \underline{v_{17}}, v_{26}; \underline{v_{27}}), \\ T (v_{24}, \underline{v_{15}}, v_{22}, v_{16}, v_{23}, \underline{v_{17}}, v_{25}; \underline{v_{21}}) . \end{aligned}$

Similarly $K_{8, 8} = 8 T$ , where $8 T$ ’s are identified as, $\begin{aligned} T (v_{22}, \underline{v_{13}}, v_{24}, v_{12}, v_{23}, \underline{v_{18}}, v_{21}; \underline{v_{25}}), T (v_{28}, \underline{v_{12}}, v_{25}, v_{11}, v_{26}, \underline{v_{13}}, v_{23}; \underline{v_{27}}), \\ T (v_{26}, \underline{v_{12}}, v_{21}, v_{13}, v_{28}, \underline{v_{14}}, v_{25}; \underline{v_{22}}), T (v_{28}, \underline{v_{11}}, v_{27}, v_{14}, v_{26}, \underline{v_{15}}, v_{25}; \underline{v_{24}}), \\ T (v_{24}, \underline{v_{14}}, v_{21}, v_{16}, v_{27}, \underline{v_{15}}, v_{22}; \underline{v_{23}}), T (v_{24}, \underline{v_{16}}, v_{28}, v_{15}, v_{21}, \underline{v_{17}}, v_{26}; \underline{v_{22}}), \\ T (v_{21}, \underline{v_{11}}, v_{23}, v_{17}, v_{24}, \underline{v_{18}}, v_{27}; \underline{v_{22}}), T (v_{23}, \underline{v_{16}}, v_{26}, v_{18}, v_{28}, \underline{v_{17}}, v_{27}; \underline{v_{25}}) . \end{aligned}$

Further $K_{9, 8} = 9 T$ , the following are the required $9 T$ ’s $\begin{aligned} T (v_{26}, \underline{v_{11}}, v_{23}, v_{12}, v_{24}, \underline{v_{13}}, v_{25}; \underline{v_{22}}), T (v_{25}, \underline{v_{12}}, v_{26}, v_{19}, v_{27}, \underline{v_{13}}, v_{23}; \underline{v_{28}}), \\ T (v_{22}, \underline{v_{12}}, v_{21}, v_{13}, v_{26}, \underline{v_{14}}, v_{23}; v_{27}), T (v_{28}, \underline{v_{11}}, v_{24}, v_{14}, v_{22}, \underline{v_{15}}, v_{25}; v_{27}), \\ T (v_{21}, \underline{v_{14}}, v_{25}, v_{16}, v_{23}, \underline{v_{15}}, v_{24}; \underline{v_{28}}), T (v_{27}, \underline{v_{16}}, v_{21}, v_{15}, v_{26}, \underline{v_{17}}, v_{22}; \underline{v_{24}}), \\ T (v_{21}, \underline{v_{18}}, v_{27}, v_{17}, v_{25}, \underline{v_{19}}, v_{22}; \underline{v_{24}}), T (v_{22}, \underline{v_{16}}, v_{26}, v_{18}, v_{23}, \underline{v_{17}}, v_{21}; \underline{v_{28}}), \\ T (v_{22}, \underline{v_{18}}, v_{25}, v_{11}, v_{21}, \underline{v_{19}}, v_{23}; \underline{v_{28}}) . \end{aligned}$

Lemma 2.7. The graph

K_{8}

admits

(P_{5}, Y_{5})_{{α, β}}

– decomposition when

α + β = 7

Proof. The admissible pairs satisfying $α + β = 7$ are {(0,7),(1,6),(2,5),(3,4),(4,3),(5,2),
(6,1),(7,0)}.

Case 1. $α \neq 0$ .

From Lemma 2.5, $K_{8} = 3 T \oplus 1 P_{5}$ , which can be taken into any of the forms: $6 Y_{5} \oplus 1 P_{5}, 5 Y_{5} \oplus 2 P_{5}, 4 Y_{5} \oplus 3 P_{5}, 3 Y_{5} \oplus 4 P_{5}, 2 Y_{5} \oplus 5 P_{5}, 1 Y_{5} \oplus 6 P_{5}, and 7 P_{5}$ using Remark 2.2.

Thus we have $(P_{5}, Y_{5})$ – multi-decomposition for the admissible pairs $(α, β)$ $\in {(1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1), (7, 0)} .$

Case 2. $α = 0$ .

Theorem 1.1 gives the required decomposition for the admissible pair $(0, 7)$ .

Hence the proof follows from Cases 1 & 2 for all admissible pairs $(α, β)$ .

Lemma 2.8. The graph

K_{9}

admits

(P_{5}, Y_{5})_{{α, β}}

– decomposition if

α + β = 9

Proof. The admissible pairs satisfying $α + β = 9$ are {(0,9),(1,8),(2,7),(3,6),(4,5),(5,4),
(6,3),(7,2),(8,1),(9,0)}.

Case 1. $α \neq 0$ .

From Lemma 2.6, $K_{9} = 4 T \oplus 1 P_{5}$ , which can be taken into any of the forms: $8 Y_{5} \oplus 1 P_{5}, 7 Y_{5} \oplus 2 P_{5}, 6 Y_{5} \oplus 3 P_{5}, 5 Y_{5} \oplus 4 P_{5}, 4 Y_{5} \oplus 5 P_{5}, 3 Y_{5} \oplus 6 P_{5}, 2 Y_{5} \oplus 7 P_{5}, 1 Y_{5} \oplus 8 P_{5} and 9 P_{5}$ using Remark 2.2.

Thus we have $(P_{5}, Y_{5})$ – multi-decomposition for the admissible pairs $(α, β)$ $\in {(1, 8), (2, 7), (3, 6), (4, 5), (5, 4), (6, 3), (7, 2), (8, 1), (9, 0)} .$

Case 2. $α = 0$ .

Theorem 1.1 gives the required decomposition for the admissible pair $(0, 9)$ .

Thus, $K_{9}$ admits $(P_{5}, Y_{5})_{{α, β}}$ – decomposition.

Lemma 2.9. The graph

K_{7, 8}

admits

(P_{5}, Y_{5})_{{α, β}}

– decomposition if

α + β = 14

Proof. The admissible pairs satisfying $α + β = 14$ are {(0,14),(1,13),(2,12),(3,11),(4,10),(5,9),(6,8),
(7,7),(8,6),(9,5),(10,4),(11,3),(12,2),(13,1),(14,0)}.

From Lemma 2.6, $K_{7, 8} = 7 T$ , which can be taken into any of the forms: $14 Y_{5}, 13 Y_{5} \oplus 1 P_{5}, 12 Y_{5} \oplus 2 P_{5}, 11 Y_{5} \oplus 3 P_{5}, 10 Y_{5} \oplus 4 P_{5}, 9 Y_{5} \oplus 5 P_{5}, 8 Y_{5} \oplus 6 P_{5}, 7 Y_{5} \oplus 7 P_{5}, 6 Y_{5} \oplus 8 P_{5}, 5 Y_{5} \oplus 9 P_{5}, 4 Y_{5} \oplus 10 P_{5}, 3 Y_{5} \oplus 11 P_{5}, 2 Y_{5} \oplus 12 P_{5}, 1 Y_{5} \oplus 13 P_{5} and 14 P_{5}$ using Remark 2.2.

Thus we have $(P_{5}, Y_{5})$ – multi-decomposition for all the admissible pairs $(α, β)$ .

Lemma 2.10. The graph

K_{8, 8}

admits

(P_{5}, Y_{5})_{{α, β}}

– decomposition if

α + β = 16

Proof. The admissible pairs satisfying $α + β = 16$ are {(0,16),(1,15),(2,14),(3,13),(4,12),(5,11),(6,10),
(7,9),(8,8),(9,7),(10,6),(11,5),(12,4),(13,3),(14,2),(15,1),(16,0)}.

From Lemma 2.6 , $K_{8, 8} = 8 T$ . Then we have $(P_{5}, Y_{5})$ – multi-decomposition for all the admissible pairs $(α, β)$ using Remark 2.2.

Lemma 2.11. The graph

K_{9, 8}

admits

(P_{5}, Y_{5})_{{α, β}}

– decomposition when

α + β = 18

Proof. The admissible pairs satisfying $α + β = 18$ are { $(0, 18), (1, 17), (2, 16), (3, 15), (4, 14), (5, 13), (6, 12), (7, 11), (8, 10), (9, 9), (10, 8), (11, 7), (12, 6), (13, 5), (14, 4),$ $(15, 3), (16, 2), (17, 1), (18, 0)$ }.

From Lemma 2.6 , $K_{9, 8} = 9 T$ . Then we have $(P_{5}, Y_{5})$ – multi-decomposition for all the admissible pairs $(α, β)$ using Remark 2.2.

Theorem 2.12. (Sufficient conditions) For given non negative integers

α

β

and

n \geq 8

K_{n}

has

(P_{5}, Y_{5})_{{α, β}}

– decomposition whenever

4 (α + β) = (\binom{n}{2}) .

Proof. From the given (Necessary conditions) edge divisibility condition,
we have $n \equiv 0 or 1 (m o d 8)$ .

Case 1: $n \equiv 0 (m o d 8)$ .

Let $n = 4 t$ , $t$ is even. We prove this theorem using induction on $t$ . When $t = 2$ , the proof follows from Lemma 2.7. We observe that for $t \geq 4$ , $\begin{matrix} (1) & K_{4 t} = K_{4 (t - 2)} \oplus K_{9} \oplus K_{4 (t - 2) - 1, 8} . \end{matrix}$

Also for $t \geq 6$ , $\begin{matrix} (2) & K_{4 (t - 2) - 1, 8} = K_{4 (t - 4) - 1, 8} \oplus K_{8, 8} . \end{matrix}$

From (1) and (2), $\begin{matrix} (3) & K_{4 t} = K_{4 (t - 2)} \oplus K_{9} \oplus K_{4 (t - 4) - 1, 8} \oplus K_{8, 8}, t \geq 6 . \end{matrix}$

Assume that the theorem is true for all even $k$ $<$ $t$ . We have to prove for $t = k + 2$ . From (3), we can write, $K_{4 (k + 2)} = K_{4 k} \oplus K_{9} \oplus K_{4 (k - 2) - 1, 8} \oplus K_{8, 8} .$

By induction hypothesis and from Lemmas 2.7, 2.8, 2.9 and 2.10 the proof follows.

Case 2: $n \equiv 1 (m o d 8)$ .

Let $n = 4 t + 1$ , $t$ is even. When $t = 2$ , the proof follows from Lemma 2.8. We observe that for $t \geq 4$ , $\begin{matrix} (4) & K_{4 t + 1} = K_{4 (t - 2)} \oplus K_{9} \oplus K_{4 (t - 2) + \frac{1}{2} (t - 2), 8} \end{matrix}$ Also for $t \geq 6$ , $\begin{matrix} (5) & K_{4 (t - 2) + \frac{1}{2} (t - 2), 8} = K_{4 (t - 4) + \frac{1}{2} (t - 2), 8} \oplus K_{9, 8} . \end{matrix}$

From (4) and (5), $\begin{matrix} (6) & K_{4 t + 1} = K_{4 (t - 2)} \oplus K_{9} \oplus K_{4 (t - 4) + \frac{1}{2} (t - 2), 8} \oplus K_{9, 8}, t \geq 6 . \end{matrix}$

Assume that the theorem is true for all even $k$ $<$ $t$ . We have to prove for $t = k + 2$ . From (6), we can write, $K_{4 (k + 2) + 1} = K_{4 k} \oplus K_{9} \oplus K_{4 (k - 2) + \frac{1}{2} k, 8} \oplus K_{9, 8} .$

By induction hypothesis and from Lemmas 2.7, 2.8 and 2.11 the proof follows.

Theorem 2.13. (Main Theorem) For non-negative integers

α

β

and

n \geq 8

K_{n} = α P_{5} \oplus β Y_{5}

if and only if

4 (α + β) = (\binom{n}{2})

Proof. The proof follows from Theorems 2.4 and 2.12.

3. Multi-decomposition of complete bipartite graphs into $P_{5}$ and $Y_{5}$

3.1. Necessary conditions

In this section, we derive the necessary conditions for the existence of multi-decomposition of $K_{m, n}$ , ( $m > 2, n \geq 2$ ) into paths and $Y$ -trees with 5 vertices.

Lemma 3.1. Let

k

be even. If

K_{2 k, 2}

has a

(P_{5}, Y_{5})

– multi-decomposition for the admissible pair

(α, β)

, then

α

is even.

Proof. Let $V (K_{2 k, 2}) = V_{1} \cup V_{2}$ , where $| V_{1} | = 2 k$ , $| V_{2} | = 2$ and $| E (K_{2 k, 2}) | = 4 k$ . $P_{5}$ has a degree sequence $(2, 2, 2, 1, 1)$ . While decomposing $K_{2 k, 2}$ into $P_{5}$ ’s and $Y_{5}$ ’s, the two vertices of $P_{5}$ with degree 2 which are incident with a vertex of degree 1, should be formed using the vertex set $V_{2} =$ { $v_{21}, v_{22}$ }. $Y_{5}$ has a degree sequence $(3, 2, 1, 1, 1)$ . Here, the vertex with degree 3 and the vertex with degree 1 which is incident with a vertex of degree 2, should be formed using the vertex set $V_{2}$ . Since each vertex in $V_{2}$ has degree $2 k$ , after decomposing $K_{2 k, 2}$ into $α$ number of $P_{5}$ , each vertex $v_{2 i}$ , $i = 1, 2$ has degree $2 k - 2 α$ and $| E (K_{2 k, 2} ∖ α P_{5}) | = 4 k - 4 α$ . Since $k$ is even, it is clear that $\begin{aligned} 2 (k - α) \equiv {\begin{aligned} 0 (m o d 4), i f α i s e v e n, \\ 2 (m o d 4), i f α i s o d d . \end{aligned} \end{aligned}$ Therefore, partitioning the remaining $4 (k - α)$ edges into $k - α$ number of $Y_{5}$ is possible only when $α$ is even.

Lemma 3.2. Let

k \geq 3

be odd. If

K_{2 k, 2}

has a

(P_{5}, Y_{5})

– multi-decomposition for the admissible pair

(α, β)

, then

α

is odd.

Proof. The proof is same as Lemma 3.1 with the same argument. Since $k \geq 3$ is odd, $\begin{aligned} 2 (k - α) \equiv {\begin{aligned} 2 (m o d 4), i f α i s e v e n, \\ 0 (m o d 4), i f α i s o d d . \end{aligned} \end{aligned}$ Hence the proof follows.

Theorem 3.3. (Necessary conditions) If

K_{m, n}

has

(P_{5}, Y_{5})_{{α, β}}

– decomposition, then

m n = 4 (α + β)

with

m > 2

and

n > 1

except

$m = 2 k$ , $k$ even; $n = 2$ and $α$ is odd
$m = 2 k$ , $k \geq 3$ odd; $n = 2$ and $α$ is even

Proof. The proof follows from edge divisibility condition and by Lemmas 3.1 and 3.2.

3.2. Sufficient conditions

In the following lemmas we prove that the above necessary conditions are also sufficient.

Lemma 3.4.

\begin{aligned} K_{4, 2} = {\begin{aligned} 2 P_{5}, \\ or, \\ 2 Y_{5} . \end{aligned} \end{aligned}

Proof. By Theorem 3.3, $α + β = 2$ . Hence the admissible pairs $(α, β)$ are $(0, 2)$ , $(1, 1)$ and $(2, 0)$ . By Theorem 1.2, $K_{4, 2}$ can be decomposed into $2 P_{5}$ and by Theorem 1.3, $K_{4, 2}$ can be decomposed into $2 Y_{5}$ . Hence there exists a $(P_{5}, Y_{5})$ – multi-decomposition for the admissible pairs $(0, 2)$ and $(2, 0)$ . By Lemma 3.1, it is clear that there does not exist a $(P_{5}, Y_{5})$ – multi-decomposition for the admissible pair $(1, 1)$ . Hence the proof.

Lemma 3.5. The graph

K_{6, 2}

has

(P_{5}, Y_{5})

– multi-decomposition for some of the admissible pairs (

α, β

) where

α

is odd.

Proof. The admissible pairs for which the decomposition exists are ( $α, β$ ) $\in$ {(3,0), (1,2)}. For $(3, 0)$ , Theorem 1.2 gives the required decomposition. For $(1, 2)$ , we have the necessary breakdown is as follows:

$P_{5} (v_{11}, v_{21}, v_{12}, v_{22}, v_{13}), Y_{5} (v_{21}, v_{15}, \underline{v_{22}}, v_{14}; \underline{v_{11}}), Y_{5} (v_{22}, v_{16}, \underline{v_{21}}, v_{14}; \underline{v_{13}}) .$

The desired decomposition does not exist for the admissible pairs $(2, 1)$ and $(0, 3)$ by Lemma 3.2.

Lemma 3.6. Let

k

be even. If

α

is even in the admissible pair

(α, β)

, then

K_{2 k, 2}

has a

(P_{5}, Y_{5})

– multi-decomposition.

Proof. Since $k$ is even, $k = 2 k_{1}$ for $k_{1}$ $\in$ $N$ . we write, $K_{2 k, 2} = k_{1} K_{4, 2}$ .

Therefore, by Lemma 3.4, for any even $α$ such that $α + β = k$ , there exists a $(P_{5}, Y_{5})$ – multi-decomposition for the admissible pairs $(α, β)$ with $α$ , $β$ are even. This completes the proof.

Lemma 3.7. Let

k \geq 3

be odd. If

α

is odd, then

K_{2 k, 2}

has

(P_{5}, Y_{5})

– multi-decomposition.

Proof. Since $k \neq 1$ is odd, $k = 2 q + 1$ for $q$ $\in$ $N$ . we write, $K_{2 k, 2} = (q - 1) K_{4, 2} \oplus K_{6, 2}$ .

Therefore, by Lemmas 3.4 and 3.5, for any odd $α$ such that $α + β = k$ , there exists a $(P_{5}, Y_{5})$ – multi-decomposition for the admissible pairs $(α, β)$ with $α$ is odd and $β$ is even. This completes the proof.

Lemma 3.8. The graph

K_{4, 3}

admits

(P_{5}, Y_{5})_{{α, β}}

– decomposition whenever

α + β = 3

Proof. Case 1: (3,0).

Theorem 1.2 gives required 3 $P_{5}$ ’s.

Case 2: (2,1).

$P_{5} (v_{21}, v_{12}, v_{22}, v_{11}, v_{23}), P_{5} (v_{11}, v_{21}, v_{13}, v_{22}, v_{14}), Y_{5} (v_{21}, v_{14}, \underline{v_{23}}, v_{13}; \underline{v_{12}}) .$

Case 3: (1,2).

$P_{5} (v_{21}, v_{14}, v_{22}, v_{11}, v_{23}), Y_{5} (v_{22}, v_{12}, \underline{v_{23}}, v_{13}; \underline{v_{14}}), Y_{5} (v_{22}, v_{13}, \underline{v_{21}}, v_{12}; \underline{v_{11})} .$

Case 4: (0,3).

Theorem 1.3 gives the required decomposition.

Lemma 3.9. The graph

K_{4, 4}

admits

(P_{5}, Y_{5})_{{α, β}}

– decomposition whenever

α + β = 4

Proof. Case 1: $α$ is even i.e., $(α, β)$ $\in$ {(4,0), (2,2), (0,4)}.

Since $K_{4, 4} = 2 K_{4, 2}$ , Theorems 1.2 and 1.3 give the required decomposition.

Case 2: $α$ is odd.

Subcase 1: (3,1). $P_{5} (v_{11}, v_{22}, v_{14}, v_{23}, v_{13}), P_{5} (v_{21}, v_{14}, v_{24}, v_{12}, v_{22}), P_{5} (v_{12}, v_{23}, v_{11}, v_{24}, v_{13}), Y_{5} (v_{22}, v_{13}, \underline{v_{21}}, v_{12}; \underline{v_{11}})$

Subcase 2: (1,3). $P_{5} (v_{12}, v_{22}, v_{13}, v_{21}, v_{14}), Y_{5} (v_{13}, v_{23}, \underline{v_{14}}, v_{24}; \underline{v_{22}}), Y_{5} (v_{13}, v_{24}, \underline{v_{11}}, v_{23}; \underline{v_{22}}), Y_{5} (v_{11}, v_{21}, \underline{v_{12}}, v_{24}; \underline{v_{23}})$

Lemma 3.10. The graphs

K_{4, 5}

and

K_{4, 6}

admits

(P_{5}, Y_{5})_{{α, β}}

– decomposition whenever

α + β = 5

and

α + β = 6

respectively.

Proof. We can write $K_{4, 5} = K_{4, 2} \oplus K_{4, 3}$ , $K_{4, 6} = 2 K_{4, 3}$ . Then the proof follows from Lemmas 3.4 and 3.8.

Lemma 3.11. The graph

K_{6, 6}

admits

(P_{5}, Y_{5})_{{α, β}}

– decomposition whenever

α + β = 9

Proof. We can write $K_{6, 6} = K_{4, 6} \oplus K_{2, 6}$ . Since $K_{m, n} ≅ K_{n, m}$ , the proof follows from Lemmas 3.5 and 3.10.

Lemma 3.12. If

k, n \in N

n \geq 3

, then

K_{4 k, n}

can be decomposed into admissible pairs of

P_{5}

and

Y_{5}

Proof. Let $n = 4 q + r$ for $q > 0$ and $r \in {0, 1, 2, 3}$ .

If $r = 0$ , $K_{4 k, n} = K_{4 k, 4 q} = k q K_{4, 4}$ .

For $r = 1$ , $K_{4 k, n} = K_{4 k, 4 q + 1} = K_{4 k, 4 (q - 1) + 5} = k (q - 1) K_{4, 4} \oplus K_{4, 5}$ .

When $r = 2$ , $K_{4 k, n} = K_{4 k, 4 q + 2} = K_{4 k, 4 (q - 1) + 6} = k (q - 1) K_{4, 4} \oplus K_{4, 6}$ .

When $r = 3$ , $K_{4 k, n} = K_{4 k, 4 q + 3} = k q K_{4, 4} \oplus K_{4, 3}$ .

Then the proof follows from Lemmas 3.8, 3.9, 3.10 and by mathematical induction on $k$ , $n$ .

Lemma 3.13. If

k_{1}, k_{2} \geq 3

be odd, then

K_{2 k_{1}, 2 k_{2}}

can be decomposed into admissible pairs of

P_{5}

and

Y_{5}

Proof. Since $k_{1} \neq 1$ , $k_{2} \neq 1$ are odd, $k_{1} = 2 q_{1} + 1$ and $k_{2} = 2 q_{2} + 1$ for $q_{1}, q_{2} \in N$ and we write, $K_{2 k_{1}, 2 k_{2}} = (q_{1} - 1) (q_{2} - 1) K_{4, 4} \oplus (q_{1} - 1) K_{4, 6} \oplus (q_{2} - 1) K_{6, 4} \oplus K_{6, 6}$ .

Then the proof follows from Lemmas 3.9, 3.10, 3.11 and by mathematical induction on $k_{1}$ , $k_{2}$ .

Theorem 3.14. (Sufficient Conditions) If

m, n, α

and

β

satisfy the necessary condition given in Theorem 3.3, then

K_{m, n}

has

(P_{5}, Y_{5})_{{α, β}}

– decomposition.

Proof. Case 1: $m \equiv 0 (m o d 4)$ or $n \equiv 0 (m o d 4)$ , w.l.o.g, let $m = 4 k$ for $k \in N$ .

Subcase 1.1. $n = 2$ .

Lemma 3.6 gives the required decomposition.

Subcase 1.2. $n \geq 3$ .

Lemma 3.12 gives the required decomposition.

Case 2: $m \equiv 0 (m o d 2)$ and $n \equiv 0 (m o d 2)$ , i.e., $m = 2 k_{1}$ , $n = 2 k_{2}$ for $k_{1}$ , $k_{2}$ $\in N$ .

Subcase 2.1. When one of them is $2$ , w.l.o.g, let $n = 2$ .

When $k_{1}$ is even, this falls in Subcase 1.1. If $k_{1} \neq 1$ is odd, Lemma 3.7 gives the required decomposition.

Subcase 2.2. $m, n > 2$ .

When one of $k_{1}$ and $k_{2}$ or both of them are even, then the proof follows from Subcase 1.2. If both of them are odd, Lemma 3.13 gives the required decomposition.

Theorem 3.15. (Main Theorem) There exists

(P_{5}, Y_{5})_{{α, β}}

– decomposition of

K_{m, n}

if and only if any one of the following holds:

$m = 2 k, k$ is even, $n = 2$ and $α$ is even.
$m = 2 k, k \geq 3$ is odd, $n = 2$ and $α$ is odd.
$m = 4 k$ and $n \geq 3$ .
$m = 2 k_{1}$ and $n = 2 k_{2}$ ; where $k_{1}, k_{2} \geq 3$ are odd.

Proof. Proof follows from Theorems 3.3 and 3.14.

4. Conclusion

In this paper, it is proved that the necessary and sufficient condition for the existence of the $(P_{5}, Y_{5})_{{α, β}}$ – decomposition of the complete graph $K_{n}$ ( $n \geq 8$ ) is $n \equiv 0 o r 1 (m o d 8)$ . Also we have obtained the necessary and sufficient conditions for the $(P_{5}, Y_{5})_{{α, β}}$ – decomposition of the complete bipartite graph $K_{m, n}$ ( $m > 2$ , $n \geq 2$ ) as $m n = 4 (α + β)$ whenever

$m = 2 k$ , $k$ even; $n = 2$ then $α$ is even.
$m = 2 k$ , $k \geq 3$ odd; $n = 2$ then $α$ is odd.

References:

C. A. Parker. Complete bipartite graph path decompositions. Ph.D. Dissertation, Auburn University, Auburn, Alabama, 1998.
A. Abueida and M. Daven. Multi-designs for graph-pairs of order 4 and 5. Graphs and Combinatorics, 19(4):433–447, 2003. https://doi.org/10.1007/s00373-003-0530-3.
S. Caterina De and S. Antonio. Stability number of bull and chair-free graphs. Discrete Applied Mathematics, 41(2):121–129, 1993. https://doi.org/10.1016/0166-218X(93)90032-J.
S. Gomathi and A. Tamil Elakkiya. Gregarious Y5-tree decompositions of tensor product of complete graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 117:185–194, 2023. https://doi.org/10.61091/jcmcc117-17.
C. Huang and A. Rosa. Decomposition of complete graphs into trees. Ars Combinatoria, 5:23–63, 1978.
S. Jeevadoss and A. Muthusamy. Decomposition of complete bipartite graphs into paths and cycles. Discrete Mathematics, 331:98–108, 2014. https://doi.org/10.1016/j.disc.2014.05.009.
A. Maria, M. Ryan, and U. Torsten. Twins in graphs. European Journal of Combinatorics, 39:188–197, 2014. https://doi.org/10.1016/j.ejc.2014.01.007.
J. Paulraj Joseph and A. Samuel Issacraj. Fork-decomposition of graphs. Pre-Conference Proceedings of the International Conference on Discrete Mathematics, ISBN:978-93-91077-53-2:426–431, 2022.
A. Samuel Issacraj and J. Paulraj Joseph. Fork-decomposition of some total graphs. Palestine Journal of Mathematics, 12(Special Issue II):65–72, 2023.
A. Samuel Issacraj and J. Paulraj Joseph. Fork-decomposition of the Cartesian product of graphs. Mapana Journal of Sciences, 22(Special Issue 1):163–178, 2023. https://doi.org/10.12723/mjs.sp1.13.
G. Sethuraman and V. Murugan. Decomposition of complete graphs into arbitrary trees. Graphs and Combinatorics, 37(4):1191–1203, 2021. https://doi.org/10.1007/s00373-021-02299-5.
T.-W. Shyu. Decomposition of complete graphs into paths and cycles. Ars Combinatoria, 97:257–270, 2010.
T.-W. Shyu. Decomposition of complete graphs into paths and stars. Discrete Mathematics, 310:2164–2169, 2010. https://doi.org/10.1016/j.disc.2010.04.009.
T.-W. Shyu. Decomposition of complete bipartite graphs into paths and stars with the same number of edges. Discrete Mathematics, 313:865–871, 2013. https://doi.org/10.1016/j.disc.2012.12.020.
M. Truszczyński. Note on the decomposition of λKm,n(λK∗m,n) into paths. Discrete Mathematics, 55(1):89–96, 1985. https://doi.org/10.1016/S0012-365X(85)80023-6.

[1] C. A. Parker. Complete bipartite graph path decompositions. Ph.D. Dissertation, Auburn University, Auburn, Alabama, 1998.

[2] A. Abueida and M. Daven. Multi-designs for graph-pairs of order 4 and 5. Graphs and Combinatorics, 19(4):433–447, 2003. https://doi.org/10.1007/s00373-003-0530-3.

[3] S. Caterina De and S. Antonio. Stability number of bull and chair-free graphs. Discrete Applied Mathematics, 41(2):121–129, 1993. https://doi.org/10.1016/0166-218X(93)90032-J.

[4] S. Gomathi and A. Tamil Elakkiya. Gregarious Y5-tree decompositions of tensor product of complete graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 117:185–194, 2023. https://doi.org/10.61091/jcmcc117-17.

[5] C. Huang and A. Rosa. Decomposition of complete graphs into trees. Ars Combinatoria, 5:23–63, 1978.

[6] S. Jeevadoss and A. Muthusamy. Decomposition of complete bipartite graphs into paths and cycles. Discrete Mathematics, 331:98–108, 2014. https://doi.org/10.1016/j.disc.2014.05.009.

[7] A. Maria, M. Ryan, and U. Torsten. Twins in graphs. European Journal of Combinatorics, 39:188–197, 2014. https://doi.org/10.1016/j.ejc.2014.01.007.

[8] J. Paulraj Joseph and A. Samuel Issacraj. Fork-decomposition of graphs. Pre-Conference Proceedings of the International Conference on Discrete Mathematics, ISBN:978-93-91077-53-2:426–431, 2022.

[9] A. Samuel Issacraj and J. Paulraj Joseph. Fork-decomposition of some total graphs. Palestine Journal of Mathematics, 12(Special Issue II):65–72, 2023.

[10] A. Samuel Issacraj and J. Paulraj Joseph. Fork-decomposition of the Cartesian product of graphs. Mapana Journal of Sciences, 22(Special Issue 1):163–178, 2023. https://doi.org/10.12723/mjs.sp1.13.

[11] G. Sethuraman and V. Murugan. Decomposition of complete graphs into arbitrary trees. Graphs and Combinatorics, 37(4):1191–1203, 2021. https://doi.org/10.1007/s00373-021-02299-5.

[12] T.-W. Shyu. Decomposition of complete graphs into paths and cycles. Ars Combinatoria, 97:257–270, 2010.

[13] T.-W. Shyu. Decomposition of complete graphs into paths and stars. Discrete Mathematics, 310:2164–2169, 2010. https://doi.org/10.1016/j.disc.2010.04.009.

[14] T.-W. Shyu. Decomposition of complete bipartite graphs into paths and stars with the same number of edges. Discrete Mathematics, 313:865–871, 2013. https://doi.org/10.1016/j.disc.2012.12.020.

[15] M. Truszczyński. Note on the decomposition of λKm,n(λK∗m,n) into paths. Discrete Mathematics, 55(1):89–96, 1985. https://doi.org/10.1016/S0012-365X(85)80023-6.

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

Multi-decomposition of graphs into paths and $Y$ -trees of order five

Abstract

1. Introduction

2. Multi-decomposition of complete graphs into $P_{5}$ and $Y_{5}$

2.1. Preliminaries

2.2. Notations

2.3. Necessary condition

2.4. Sufficient conditions

3. Multi-decomposition of complete bipartite graphs into $P_{5}$ and $Y_{5}$

3.1. Necessary conditions

3.2. Sufficient conditions

4. Conclusion

References:

Information

Guidelines

CP Initiatives

Follow CP

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

Multi-decomposition of graphs into paths and Y-trees of order five

Abstract

1. Introduction

2. Multi-decomposition of complete graphs into P5 and Y5

2.1. Preliminaries

2.2. Notations

2.3. Necessary condition

2.4. Sufficient conditions

3. Multi-decomposition of complete bipartite graphs into P5 and Y5

3.1. Necessary conditions

3.2. Sufficient conditions

4. Conclusion

References:

Information

Guidelines

CP Initiatives

Follow CP

Multi-decomposition of graphs into paths and $Y$ -trees of order five

2. Multi-decomposition of complete graphs into $P_{5}$ and $Y_{5}$

3. Multi-decomposition of complete bipartite graphs into $P_{5}$ and $Y_{5}$