ON HAMILTONIAN DECOMPOSITIONS OF TENSOR PRODUCTS OF GRAPHS

被引：0

作者：

Paulraja, P. ^{[1
]}

Kumar, S. Sampath ^{[2
]}

机构：

[1] Annamalai Univ, Dept Math, Annamalainagar 608002, Tamil Nadu, India

[2] SSN Coll Engn, Dept Math, Kalavakkam 603110, India

来源：

APPLICABLE ANALYSIS AND DISCRETE MATHEMATICS | 2019年 / 13卷 / 01期

关键词：

Hamiltonian Decomposition; Tensor Product; Cayley Graphs; CYCLE DECOMPOSITIONS;

D O I：

10.2298/AADM170803003P

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Finding a hamiltonian decomposition of G is one of the challenging problems in graph theory. We do not know for what classes of graphs G and H, their tensor product G x H is hamiltonian decomposable. In this paper, we have proved that, if G is a hamiltonian decomposable circulant graph with certain properties and H is a hamiltonian decomposable multigraph, then G x H is hamiltonian decomposable. In particular, tensor products of certain sparse hamiltonian decomposable circulant graphs are hamiltonian decomposable.

引用

页码：178 / 202

页数：25

共 18 条

[1]

Alspach B., 1990, Cycles and Rays, P9, DOI [10.1007/978-94-009-0517-72, DOI 10.1007/978-94-009-0517-72]

[2]

[Anonymous], 2007, Graph Theory

[3] On Hamilton cycle decompositions of the tensor product of complete graphs [J].

Balakrishnan, R ;

Bermond, JC ;

Paulraja, P ;

Yu, ML .

DISCRETE MATHEMATICS, 2003, 268 (1-3) :49-58

[4] Hamilton cycles in tensor product of graphs [J].

Balakrishnan, R ;

Paulraja, P .

DISCRETE MATHEMATICS, 1998, 186 (1-3) :1-13

[5]

BALAKRISHNAN R, 2012, TXB GRAPH THEORY

[6] HAMILTONIAN DECOMPOSITION OF LEXICOGRAPHIC PRODUCT [J].

BARANYAI, Z ;

SZASZ, GR .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1981, 31 (03) :253-261

[7]

Bermond J.-C., 1978, Advances in graph theory, P21

[8] HAMILTONIAN DECOMPOSITION OF CAYLEY-GRAPHS OF DEGREE-4 [J].

BERMOND, JC ;

FAVARON, O ;

MAHEO, M .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1989, 46 (02) :142-153

[9]

Bosak J., 1990, DECOMPOSITIONS GRAPH

[10] Edge exchanges in Hamiltonian decompositions of Kronecker-product graphs [J].

Jha, PK ;

Agnihotri, N ;

Kumar, R .

COMPUTERS & MATHEMATICS WITH APPLICATIONS, 1996, 31 (02) :11-19

← 1 2 →