Hamiltonian Decompositions and Linear Arboricity of Graphs
Abstract
Let Γ be a finite abelian group with operation “+ ”and A be a symmetric subset of Γ (if a ∈ A, then −a ∈ A). The Cayley graph Cay(A, Γ) is the graph having the elements of Γ as its vertices and, for all vertices x and y, there exists an edge joining x and y if and only if x − y ∈ A. The Cayley graph Cay(A, Γ) is connected if and only if A is a generating set of Γ.
The Cayley graph Cay(A, Γ) where A = {±a, ±b} is a generating set of Γ such that 2a /= 0, 2b /= 0 and a /= ±b is denoted by CayΓ(a, b). These conditions imply that CayΓ(a, b) is a 4-regular connected graph. We can see that every edge of CayΓ(a, b) joins vertices u and u + a, or vertices u and u + b. The sets of these edges are denoted by Ea or Eb, respectively. In 1989, Bermond et al proved that CayΓ(a, b) can be decomposed into two Hamiltonian cycles. We extend this result by showing that, for e1 ∈ Ea and e2 ∈ Eb, CayΓ(a, b) has a Hamiltonian decomposition such that e1 and e2 are contained in different Hamiltonian cycles.
A ρ-labelling of a graph with m edges is an injection from the vertices of the graph to the set {0, 1, 2, ..., 2m}, such that if the edge labels in- duced by the absolute values of the differences of the vertex labels are a1, a2, ..., am, then ai = i or ai = 2m + 1 − i for all 1 ≤ i ≤ m. A graph is called a ρ-labelled graph if it has a ρ-labelling. Let H ⊂ K2n+1 with integer n and |E(H)| = n. We show that if H is a ρ-labelled graph, then K2n+1 can be decomposed into n Hamiltonian cycles such that each edge of H belongs to different Hamiltonian cycles.
A forest is called a linear forest if every connected component is a path. The linear arboricity la(G) of a graph G is the minimum number of lin- ear forests, whose union is the set of all edges of G. The linear vertex arboricity lva(G) of G is the minimum number of subsets into which the vertex set of G can be partitioned such that each subset induces a linear forest.
We study interpolation properties for the linear arboricity la(G) and linear vertex arboricity lva(G) of graphs with order n and size m. Let G(m, n) be the class of all graphs of order n and size m. We show that
for f ∈ {la, lva}, the values of f (G) where G ∈ G(m, n) completely cover
a line segment [a, b] of positive integers where a and b are the minimum and maximum values of f (G), respectively. We also show that this holds over the class of connected graphs CG(m, n) ⊂ G(m, n). The extremal
values a and b in terms of m and n are obtained for all f ∈ {la, lva} for
most values of m and n.
Authors
Khoployklang, TeerasakCollections
- Theses [4248]