Decompositions of 6-Regular Bipartite Graphs into Paths of Length Six
- PDF / 262,079 Bytes
- 7 Pages / 439.37 x 666.142 pts Page_size
- 39 Downloads / 192 Views
(0123456789().,-volV) (0123456789().,-volV)
ORIGINAL PAPER
Decompositions of 6-Regular Bipartite Graphs into Paths of Length Six Yanan Chu1 • Genghua Fan1 • Chuixiang Zhou1 Received: 18 June 2020 / Accepted: 20 October 2020 Ó Springer Japan KK, part of Springer Nature 2020
Abstract Let T be a tree with m edges. It was conjectured that every m-regular bipartite graph can be decomposed into edge-disjoint copies of T. In this paper, we prove that every 6-regular bipartite graph can be decomposed into edge-disjoint paths with 6 edges. As a consequence, every 6-regular bipartite graph on n vertices can be decomposed into n2 paths, which is related to the well-known Gallai’s Conjecture: every connected graph on n vertices can be decomposed into at most nþ1 2 paths. Keywords Path Decomposition Regular graph
Mathematics Subject Classification 05C35 05C75
1 Introduction The graphs considered in this paper are finite, undirected and simple. The set of vertices and edges of G are denoted by V(G) and E(G), respectively. The length of a path or a cycle is the number of edges it contains. The girth of a graph G is the minimum length of a cycle in G. Throughout the paper, Pk denotes the path of length k. Let H and G be graphs. We say that G can be decomposed into H if the edge set of G can be partitioned into subsets each of which forms a subgraph isomorphic to H. The graph decomposition problem is to ask for which graphs H and G such decompositions exist. This seems to be a very hard problem even if H is a tree. Let T be a tree with m edges. A well-known conjecture of Ringel [12] is that the complete This research is supported by NSFC (11971110). & Chuixiang Zhou [email protected] 1
Center for Discrete Mathematics, Fuzhou University, Fuzhou 350108, Fujian, China
123
Graphs and Combinatorics
graph on 2m þ 1 vertices can be decomposed into T, which would be implied by the Graceful Tree Conjecture. Ha¨ggkvist mentioned in [7] that he and Graham proposed the following generalization of Ringel’s conjecture. Conjecture 1.1 Let T be a tree with m edges. Then every 2m-regular graph can be decomposed into T. Botler and Talon [2] verified Conjecture 1.1 for m ¼ 4 and T ¼ P4 . Kouider and and Lonc [10] verified the conjecture for 2m-regular graphs with girth at least ðmþ3Þ 2 T ¼ Pm . For bipartite graphs, Ha¨ggkvist [7] posed the following stronger variant, which was independently proposed by Jacobson et al. [8]. Conjecture 1.2 Let T be a tree with m edges. Then every m-regular bipartite graph can be decomposed into T. In a more general setting of graph decomposition, we say that a graph G is decomposed into a set P ¼ fH1 ; H2 ; . . .; Hk g of subgraphs of G if EðGÞ ¼ Sk i¼1 EðHi Þ and EðHi Þ \ EðHj Þ ¼ ; if i 6¼ j. When each Hi is isomorphic to the same graph H for all i, 1 i k, we simply say that G is decomposed into H. We call P a path-decomposition of G if each Hi is a path, 1 i k. A path-decomposition P is called a Pk -decomposition if every path in P has length k. Equivalently, G has a Pk decomposition if it ca
Data Loading...
