Title of article :
Edge exchanges in hamiltonian decompositions of Kronecker-product graphs
Author/Authors :
P. K. Jha، نويسنده , , N. Agnihotri، نويسنده , , R. Kumar، نويسنده ,
Issue Information :
دوهفته نامه با شماره پیاپی سال 1996
Pages :
9
From page :
11
To page :
19
Abstract :
Let G be a connected graph on n vertices, and let α, β, γ and δ be edge-disjoint cycles in G such that 1. (i) α, β (respectively, γ, δ) are vertex-disjoint and 2. (ii) Ga + β = γ + δ = n, where α denotes the length of α. We say that α, β, γ and δ yield two edge-disjoint Hamiltonian cycles by edge exchanges if the four cycles respectively contain edges e, f, g and h such that each of (α−e) g,h and (γ−g) e,f constitutes a Hamiltonian cycle in G. We show that if G is a nonbipartite, Hamiltonian decomposable graph on an even number of vertices which satisfies certain conditions, then Kronecker product of G and K2 as well as Kronecker product of G and an even cycle admits a Hamiltonian decomposition by means of appropriate edge exchanges among smaller cycles in the product graph.
Keywords :
Kronecker product , Hamiltonian decomposition , Edge exchange , Alternate four-cycle
Journal title :
Computers and Mathematics with Applications
Serial Year :
1996
Journal title :
Computers and Mathematics with Applications
Record number :
917705
Link To Document :
بازگشت